利用计算机实现排列组合公式 计算机算法基础 ——数学（排列组合函数）

一 排列

1.从n个元素中取r个元素排列的全体数目

Pnr=P(n,r)=n(n-1)(n-2)...(n-r+1)=n!/(n-r)! :例：n个球取r个放入r个不同盒子，每个盒子一个球，多少种放法

2. n个元素的全排列

Pnn=P(n,n)=n!

3.例：随机选n(n<365)个人，求其中至少有两人生日相同的概率。

n个人的生日的序列数：365n

n个人生日均不相同的概率:P(365,n)

故：1-P(365,n)/365n

4.圆排列

从n个元素中取r个元素沿一圆周排列

Qnr=Pnr/r (取r个元素作排列的结果与圆排列的结果比较，每个排列重复了r次)

同理：Qnn= n!/n =(n-1)!

二 组合

r:从n个元素中取r个元素排列而不考虑顺序；

如：n个球取r个放入r个盒子，r个盒子是相同的。

若在每种组合结果的基础对盒子排列，便得到n取r的排列，则：

Cnrr! =Pnr故 Cnr=Pnr/r! = n!/(n-r)!r!

2 分组

有a1,a2...a8八位成员，两两配对，分成4组，试求方案N

方法一：依次选择： a1选择同样有7种选择，余下6人中一人，选择同样有5种选择，余下4个，其中一个选择同样有3种可能； N=7*5*3

方法二：全排列与分组(组内，组间)：

将8个成员全排列，共8!种可能；若分成4组，{12}{34}{56}{78},若在组内位置互换，对于选择同样没有影响，则全排列中选择同样有重复，重复数：2n

同时，4组之间的排列也不影响同样关系，故全排列中对同样关系也有重复，重复数：4!

故得 8!/(2n*4!)

方法三：先分组，再组内

8个人分成4组，第1组有C82种选择，第2组有C62种选择，同理第3组有C42种选择； 且组的顺序无关

N= C82* C62*C42 * C22/4! =105

3 允许重复的组合

定理1：在n个不同元素中取r个进行组合，允许重复(r个元素中元素是可重复的)，组合数：Cn+r-1r

定理2：将r个无区别的球，放入n个有标志的盒子，每个盒子中可多于一个，则共有Cn+r-1r 种方案

例：(x+y+z)4共有多少项：

相当于 将4个球，放入3个盒子里，而且每个盒子中的数目不限。如 X4 可理解为将4个球都放入盒子X中。

N=C(n+r-1,r)=C(3+4-1,4)=C(6,4)=15

4 不相邻的组合

指：从序列A={1,2,....n}中取r个，其中不存在，i,i+1两个相邻数同时出现于一个组合中的组合。

定理： 从序列A={1,2,....n}中取r个作不相邻组合，其中组合数为：Cn-r-1r

三 母函数-幂级数

定义：设 a0,a1,a2...an是一个数列，定义它的母函数为幂级数 ——————————解决元素重复的组合问题

fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+

母函数与其他母函数存在的关系式：

A(x)= 1/(1-x) = 1+X+X2+X3+.....+Xn+

B(x)=1/(1-x)2=A(x)/(1-x) =1+2X+3X2+4X3+.....+nXn-1

C(x)=1/(1-x)3=B(x)/(1-x) =1+3X+6X2+10X3+.....+

应用：

例1：红球两个，白球，黄球各一个，试问有多少种不同的组合数

利用：fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+ 其中每一项 指数表示选择数，系数表示该该选择的方案数。

令r个球组合数为Cr,则 C0 ,C1,C2,C3,C4的母函数：

G(x)=( 1+x+x2)(1+x)(1+x)=1+3x+4x2+3x3+x4

1+x+x2表示第红球选0个，选一个，选两个

共有：1+3+4+3+1=12种不同组合数。

由4x2表示选2个球的组合数为4；3x表示选1个球的组合数

例2 ：若有1g,2g,3g,4g的砝码各一枚，问能称出几种可能的重量。

利用：fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1+C(a,2)X2+C(a,3)X3+.....+C(a,n)Xn+ 其中每一项 指数表示重量，系数表示该重量的方案数。

母函数为：G(x)=(1+x)( 1+x+x2)( 1+x+x2+x3)( 1+x+x2+x3+x4)

将系数相加，可得答案。

例3： 若有1g的砝码3枚，2g的砝码4枚，4g的砝码2枚，问能称出哪些重量，各有几种方案。

G(x)=(1+x+x2+x3)( 1+x2+x4+x6+x8) (1+x4+x8)

四 母函数—指数型

定义：设 a0,a1,a2...an是一个数列，定义它的母函数为指数型母函数： —— 解决元素重复的排列问题

fa(x)=(1+x)a=C(a,0)X0+C(a,1)X1/1!+C(a,2)X2/2!+C(a,3)X3/3!+.....+C(a,n)Xn/n!+

例1：

8个元素，a1重复3次，a2重复2次，a3重复3次，从中取r个组合，其组合数的母函数：

G(x)=(1+x+x2+x3)( 1+x2)(1+x+x2+x3)=1+3x+6x2+9x3+10x4+9x5+6x6+3x7+x8

可得到，若取4个元素进行组合有10种方案。 若需要取4个元素进行排列呢：问题就转化为从8个元素取4个进行排列，其排列数应是每种组合的排列。

如：x1x33表示1个a1,3个a3; 那么它对应的排列数为 4!/1!3! ;

由：

Cnr=Pnr/r!

Ge(x)=(1+x/1!+x2/2!+x3/3! )( 1+x/1!+x2/2!)(1+x/1!+x2/2!+x3/3! )=

1+ 3X/1! + 9x2/2! + 28x3/3! + 70x4/4! + 170x5/5!+ 350x6/6!+ 560x7/7!+ 560x8/8!

这里取K的排列数应该是K!.故取4个的排列数应是：70；

例： a1,a2...a7为7个有区别的球，将它们放入4个有标志的盒子，要求第1，2两个盒子必须含偶数个数，第3个盒子含有奇数个数。 有多少放法

可理解为从1，2，3，4这4个数字中取7个作允许重复的排列————元素重复的排列

例：求1,3,5,7,9 这5个数字组成的n位数的个数，要求其中3和7出现的次数为偶数，其他数字出现的次数无限制。

来源：/dan-cnblogs/p/4733721.html