多重排列的几道习题
今日心得: 个人天资有限, 比较认可学一门课一定要做习题,如果对某本书,某个领域想立体把握,深入探讨,个人归纳: 1 读相关书 2 精读论文 3 和适合的人交流。4 做问题。
读专业基础书会遇到的问题, 书难,读书太慢,很难进入状态,一般读着读着就容易懈怠,甚至不知所以然,这时候做习题看起来最痛苦但是最有效的。而且必须做笔记。 这和编程学习很像,光看着书本介绍基本功,而不去找一些问题,很难有兴奋点去继续下去。还有一个办法是在同一个点上多集中阅读大量资料。只有自己做起来,手脑动起来,学的效果才最好。 这一点上我很认同B站的李博士的观点。
今天的习题来自一个群里交流的问题,涉及到多重排列。我们适当地多选几道题去分析.
先回答几个基础性的问题。 参考内容源自科大版的组合数学引论。
1 什么是多重集合
正式的多重集的概念大约出现在1970年代。
多重集合同一般集合一样,是一组对象的整体,只不过不像一般集合那样必须要求集合中每个元素互不相同 , 例如
是一个10个元索的多重集合,其中有 3个 ,1 个 , 2个 , 4个 .
注: 我们一般说集合,其中三要素就是元素具有互异性。这里多重集合我们拓宽了集合的概念。
2 多重集合的一般表示
多重集合表示为 其中是互异元素。
3 多重集合的排列
多重集合 的 排列数为.
应用: 用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串?
4 多重集合全排列
5 应用 Leetcode 第62题:
可以参考此链接: https://leetcode.com/problems/unique-paths/
网友给出的思路和解法
参考:https://leetcode-cn.com/problems/unique-paths/solution/dong-tai-gui-hua-by-powcai-2/
其中的思路一就是我们的数学的方法: 类似我们书本下面的习题。
6 预留的思考: 不过需要注意即使是这种数学方法,在计算机代码中也是需要考虑复杂性的。那么这样的复杂性是多少呢? 这是我暂时留下的疑问。