排列有重复计算的吗
2023-01-11阅读(486)
问：重复排列的证明
- 答：理解就可以了~
原命题等价于从1，2，3，。。。n中选出m个数的重复排列
对于这样每一种组合a1，a2，a3，。。。am，我们要求：a1<=a2<=a3<=...<=am
求出满足上述不等式的a(i)组数就是题设的重复排列数
这里我们构造b1=a1，b2= a2+1，。。。b(i)= a(i)+(i-1)。。。b(m)= a(m)+(m-1)
于是b(i)和a(i)一一对应，即所求a(i)组数对应于b(i)组数
又：b1<b2<b3<...<bm 且b(i)取值于1~ n+(m-1)
亦即原命题等价于从1~ n+m-1中取得的不重复排列数
显然：C(n,m+n-1)
证毕 - 答：其实证明的思想很简单，为了叙述方便，将问题转化为：
向m个杯子中放入n个球（球完全相同，从而可以忽略先后顺序），问总共有多少种放法？
设1表示球，0表示杯子
从而，问题相当于在（m+n）个空（总共有m+n个东西）中插入n个球，m个杯子，但是答案并不是C（m+n,n）,
因为，若以杯子（0）为分界点，则m个0将（m+n）分为（m+1）段，（注意：当0位于两端时，会产生端点一侧为空的情况，表示端点侧杯中的球数为0个），也即该答案相当于将n个球，放入（m+1）个杯子；
为了更好理解，我们不妨规定将球（1）和杯子（0）作以下规定：
a) 相连1属于同一个杯子；
b) 相连1属于其右侧的杯子（0）；
c) 相连0表示不同的杯子；
d) 当第一个位置为0，表示第一个杯子中无球，同理，最后位置为0，表示最后一杯子中无球
从而，0011010011100，相当于6个球放入7个杯子，个杯子中的球分别为
（0/ 0/ 110/ 10/ 0/ 1110/ 0）>>>>(0, 0, 2, 1, 0, 3, 0)
由于按照上述规则，则最后一个位置始终为0，从而，原问题可转化为，在前（m+n-1）个空中抽取（m-1）个杯子的问题，总共有C（m+n-1, m-1）=C（m+n-1, n）种
证毕 - 答：n个排列，第一个有n种可能，之后第二个有n-1可能，然后第三个n-2可能，最后一个只有1种可能。
于是得到n个排列种数n!
对于每一种排列，都存在m个选中的排列m!， n-m个没有选中的排列(n-m)!种重复的计算。
所以组合数量就是 (总数/重复计算的次数)= n! / m!(n-m)!
问：排列中能否有重复数字
- 答：排列中有重复数字排列的问题。重复排列是排列组合的最基本类型了，是对乘法原理的最直接应用。最简单的例子是电话号码。例如：某城市的电话号码是8位数，每一个数位上的数码都无非是0,1,2,3,4,5,6,7,8,9；而且不同数位上的数码可能是相同的，例如：35577100,33001156,22335567等。如果我们把00000000也算成一个号码的话，那么该城市目前最多可容纳多少部电话机（不包括分机）呢？这个问题由乘法原来是不难解决的，因为我们只要算出这个城市可以列出多少个不同的号码就行了。由于每个电话号码都是一个8位数，而每一个数位上的数码又都有10种不同可能，所以一共有10×10×10×10×10×10×10×10=10^8即10000万个不同的电话号码。
从上述的例子可以看出，一个重复排列问题无非就是一个依次进行的多重选取过程，并且每一重选取都在同一个集合中进行，已经选过的元素还可以再选。
问：排列三每期和每期会有重复吗
- 答：会有重复的。大约相隔15期左右就会发生一次斜没有出现过的数字的情况，一般相隔七八期没有数字的情况。
