各种排列组合奇怪的数的公式和推导

一、排列(在乎顺序)

全排列:P(n,n)=n!

n个人都排队。第一个位置可以选n个,第二位置可以选n-1个,以此类推得: P(n,n)=n*(n-1)*…*3*2*1= n!

部分排列:P(n,m)=n!/(n-m)!

n个人,选m个出来排队,第一个位置可以选n个,…,最后一个可以选n-m+1个,以此类推得:P(n,m)=n*(n-1)*…*(n-m+1)=n!/(n-m)!。

二、组合(不在乎顺序)

n个人,选m个人出来。

因为不在乎顺序,所以按排列算的话,每个组合被选到之后还要排列,是被算了m!遍的。即C(n,m)*m!=P(n,m)

故而得:C(n,m)=n!/(m!*(n-m)!)

有两条性质:

1、C(n,m)=C(n,n-m)。就是说 从n个里面选m个 跟 从n个里面选n-m个出来不选它 是一样的。

2、C(n,m)=C(n-1,m)+C(n-1,m-1)。递推式..

从n个里面选m个出来的方案=从n-1个里面选m个的方案(即不选第n个) + 从n-1个里面选m-1个的方案(即选第n个)

三、圆排列

圆排:Q(n,n)=(n-1)!

n个人坐成一圈有多少种坐法。

想想坐成一圈后,分别以每个位置为头断开,可以排成一个序列,就是将n个人全排列中的一种。这样可以得到n个序列,但是在圆排中是视为同一种坐法的。所以:Q(n,n)*n=P(n,n),即Q(n,n)=P(n,n)/n=n!/n=(n-1)!

部分圆排:Q(n,m)=P(n,m)/m=n!/(m*(n-m)!)

推导类似

四、重复排列(有限个):n!/(a1!*a2!*…*ak!)

k种不一样的球,每种球的个数分别是a1,a2,…ak,设n=a1+a2+…+ak,求这n个球的全排列数。

把每种球重复的除掉就好了。假如第一种球有a1个,那么看成都是不一样的话就有a1!种排列方法,然而它们都是一样的,就是说重复了a1!次。其它的一样,所以重复排列的公式就是n!/(a1!*a2!*…*ak!)

五、重复组合(无限个):C(n+k-1,k)

n种不一样的球,每种球的个数是无限的,从中选k个出来的方案数。

看了几种证法,写两种吧。

证明1:这个是比较常见的。。然而我不是特别懂为什么可以。。

给这n个球编号为1~n,选出来k个。

设为1≤a1≤a2≤a3≤…≤ak≤n,因为是组合,排下序也没什么关系。

可能重复,所以有等号。但是普通的组合是没有等号的,所以要把等号想办法去掉。

于是设bi=ai+i-1。[为什么可以加,这样还表示编号吗?

这样就保证了{b}都是不一样的。

故得1<b1<b2<…<bk<n+k-1

即相当于从n+k-1个球中选k个出来,为C(n+k-1,k).

证明2:转化为隔板法啊很机智!看这个看懂了!

选出来了k个球,我们就设本来就有n+k个,而这n+k个球只有n种不同的种类,就=把这n+k个球分进不同的n个盒子里,但保证每个盒子不为空=把n+k个数分成不为空的n块=在n+k-1个间隔中放n-1个隔板(来分)。即C(n+k-1,n-1)=C(n+k-1,k),(根据性质1。

六、不相邻组合:C(n-k+1,k)

1~n这n个自然数中选k个,这k个数中任何两个数不相邻数的组合有多少种。

好像可以跟上面证明1的证法一样来证,但是我并不会= =。

所以下面的证明是来自hyc大学霸的:

一开始先假设选出来的k个数没有取到1和n,那么就相当于把n-k个数分成了k+1份(因为要求要不相邻~)。但是我们是可以选1和n的,所以给两边各补上一位(随便补啦,按顺序的话就是0跟n+1咯),这样选出来的k个数都在1~n中,就相当于把n-k+2个数分成了k+1份。即在(n-k+2)-1个间隔中放k个隔板!就是C(n-k+1,k)。

七、错排(错位排列):dn=(n-1)*(dn-1 + dn-2),n≥3

↑是个递推式。我只会递推式,,好像也只有递推式。。

(同时也有,dn=n*dn-1 + (-1)^n。没深入探讨和背过这个orz

问题相当于,有n个人编号为1~n,住在1~n号房间,要求每个人的编号与其房间号不同,问有多少种排列方法。

于是这个怎么推导的呢?先写成:dn=(n-1)*dn-1 + (n-1)*dn-2。

假如说一开始第i个人住在第i号房间。

①令n-1个人错排后,第n个人与其中的一个i互换房间,即n住在i错排后住的房间,i去住第n号房间。满足要求啊。因为n可以和n-1个人换房间,所以有(n-1)*dn-1种方法。

②n选择跟一个人换房间,即n住第i号房,i住第n号房,让剩下的n-2个人自己去搞一次错排。同样的,n可以有n-1种选择,这就有(n-1)*dn-2种方法。跟上一种方式是不一样的哦!

故递推关系就是dn=(n-1)*(dn-1 + dn-2)

错位排列数列为 0,1,2,9,44,265,……

八、stirling数(斯特林数)

第一类stirling数:S(n,m)=S(n-1,m-1)+(n-1)*S(n-1,m).

n个不同元素构成m个圆排列

①n-1个元素构成了m-1个圆排,第n个单独成一个圆排:S(n-1,m-1)。

②n-1个元素构成m个圆排,将第n个元素插在任一个元素的左边:(n-1)*S(n-1,m)。

故递推关系就是S(n,m)=S(n-1,m-1)+(n-1)*S(n-1,m)。

第二类stirling数:S(n,m)=S(n-1,m-1)+m*S(n-1,m).

n个不同元素构成m个非空的(无差别)集合

①n-1个元素构成了m-1个集合,第n个单独成一个集合:S(n-1,m-1)。

②n-1个元素构成m个集合,第n个放进任一个集合里:m*S(n-1,m)。

故递推关系就是S(n,m)=S(n-1,m-1)+m*S(n-1,m)。

有些性质啊S(n,0)、S(n,1)、S(n,n)等等为一些常数的,可以自己想到的!

九、Catalan数(卡特兰数)

通项式:Hn=C(2n,n)/(n+1)=(2n)!/( (n+1)!*n!)

组合公式:Hn=C(2n,n)-C(2n,n-1)

递归公式:

这个有很多人写我就不详细写啦~

有很多很有用的应用!而那些应用为什么可以用卡特兰数来解跟这些↑式子有很大联系。

放些感觉比较全&有点证明/推导的链接(可能他们也是转的orz):

http://www.360doc.com/content/14/1001/00/9482_413586206.shtml

http://blog.csdn.net/wuzhekai1985/article/details/6764858

http://blog.csdn.net/lidiyang1993/article/details/45191221