2.2排列与组合的概念与计算公式

《2.2排列与组合的概念与计算公式》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、排列与组合的概念与计算公式1.排列(在乎顺序)全排列：n个人全部来排队，队均no第一个位置可以选n个，第二位置可以选n-1个，以此类推得:P(n,n)=n(n-1)(n-2)……3*2*1=n!(规碓二1).部分排列：n个人选m个来排队(mv二n)。第一个位置可以选n个，第二位置可以选n-1个，以此类推，第m个(最后一个)可以选(rvm+1)个，得:P(n,m)=n(n-1)(n-2)(n-m+1)=n!/(n-m)!(«=1).2.组合(不在乎顺序)n个人m(m<=n)个出来，不排队，不在乎顺序C(n,m)0如果在乎排列那么就是P(n,m

2、),如果不在乎那么就要除掉重复，那么重复了多少？同样选出的来的m个人，他们还要全排”得到P(n,m),所以得：C(n,m)*m!=P(n,m)C(n,m)==P(n,m)/m!=n!/((n-m)!*m!)m组合零的性质CC,(m=nn)n+—

3、)»>Q(n)=P(n,n)/n=(n-1)!由此可知，部分圆排Q(n,r)=P(n,r)/r=n!/(r*(n-r)!).(1)重复排列(有限)：k种不一样的球，每种球的个数分别是a1,a2,...ak,设n=a1+a2+…+ak,这n个球的全排列数，r^(a1!*a2!*...*ak!).(2)重复组合(无限)：n种不一样的球，每种球的个数是无限的，从中选k个出来，不用排列，是组合，拔n+kjk).证明：假设选出来的数(排好序)1<=b1<=b2<=b3.<=bk<=n这题的难就是二号，现在去掉二号，所以有:1<=b1

4、2

5、这7种不同的划分方法依次为{(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)},{(14),(23)}。当n=6,r=3时，S(6,3)=。(提示：先固定一个数，对于其余的5个数考題5,3)与S(5,2),再分这两种情况对原固定的数进行分析。)题解：90.递推的解法近几年很重要。S(6,3)=3*S(5,3)+S(5,2)S(5,3)=3*S(4,3)+S(4,2)S(5,2)=2*S(4,2)+S(4,1)第二Erling数，显然拥有这样的性质：①S

6、(n,m)=m*S(n-1,m)+S(n-1,m-1)②S(n,1)=1,S(n,0)=0,S(n,n)=1而这些性质就：▲S(n,3)=1/2*(3A(n-1)+1)-2A(n-1)(1)错位排列(糠错排)先做一个小问题：5本书，编号分别是1,2,3,4,5,现在要勰5本书是放在编号1,2,3,4,5的书架上，要求书的编号和书架的编号不一样，请问有多种不一样的放置方法？例：胸口贴着编号为1,2,....n的n个球员分别住在编号为的n个房间里面。现规定每个人住一个房间，自己的编号不能和房间的编号一样。这就是错排问题。当n=3时，只能为312

7、或231这两种。题解：递推。刚开始所有球员都住在和自己编号一样的房间里面。然后错排开始了，第n个球员从第出来。第一种情况：n想和i（1<4=v钟书）其中任何一个球员换房间，其他m2个人换房间的事情，他们就不管了。其他n-2个球员的的错排数为d[n-2],n可以和前面1〜（n-1）对换，所以有（甘）个d[n-2]o第二种情况：n想和i（1v*v如书）其中任何一个球员换房间，但是n只想i住在第N个房间，而n不想住第I个房间。可能你会这样想：那么n可以让j住在第I号房间里面，然后n住在房间J。抱歉，j（1<=jv=（n—4）,j工i准气n为什么一

8、开始就去找i不直接来找j,~~（丿一匸）~~没办法，n把自己胸口的编码N换成了I,他假装自己是i,然后错排1〜n—1（也就是d[n-2]）o的时候参与进去，这样自己就不会呆在第I