组合数学(2)排列组合

要求10个男生10个女生相隔围圆桌就座，有多少种不同坐法？9！ 10！如果某女生与某男生不能相邻就坐，有多少种不同坐法？9！ 8 9！

从n个元素的集合S中任取r个元素且不考虑次序，称为从n中取r的组合。其不同组合的个数称为组合数，记作C(n,r)

对于r n，C(n,r) P(n,r)r! n!

r! (n r)!

C(n,n r)

__int64 c(int n,int r)

{

__int64 c=1;

for(int i=0;i<r;i++) c=c*(n-i)/(i+1); return c; }

C(n,r)具有如下性质：

n

(1)2n C(n,0) C(n,1) C(n,n) C(n,k)

k 0(2)C(n,r) C(n 1,r) C(n 1,r 1)

(3)C(n r 1,r) C(n r,r) C(n r 1,r 1) C(n 1,1) C(n,0)4）C(n,l)*C(l,r) C(n,r)*C(n r,l r)(l r)5）C(n,0) C(n,1) C(n,2) ( 1)nC(n,n) 0

利用(a b)n

n

C(n,k)an bn k,令a 1,b 1可得。

k 0(6)C(m n,r) C(m,0)*C(n,r) C(m,1)*C(n,r 1) C(m,r)*C(n,0)利用(1 x)

m n

(x 1)m (1 x)n中,xr

的系数相同，r min(m,n)

7）C(m n,m) C(m,0)*C(n,0) C(m,1)*C(n,1) C(m,m)*C(n,m)

利用(1 x)

m n

(x 1)m (1 x)n中,xm

的系数相同，m n

(8) 0 k 1 k n n 1 k k 1

利用 n 1 n n n n 1 n 1 k 1 k k 1 k k k 1

n n 1 n 2

k k k k k n k n 1 k n 2 k k k k 1 1 0 k k k

5 重集的排列组合

如果S是重集，S的r排列是S的r个元素的有序编排。当S的元素个数为n时，S的n排列称为S的排列。如，S

3 a,2 b,1 c,2 d 共有8个元素，

S的5排列可有aabcd,abbdd,baadc,

S的排列可有abcbadad,

如果S ar1, a2, , ak ,则S的r排列个数为k.1）S {n1 a1,n2 a2, ,nk ak}，且n1 n2 nk n，集合{x1 a1,x2 a2, ,xk ak}，称为S的一个r 子重集且x1 x2 xk r，0 xi min{ni,r},i 1,2, ,k

2）S的一个r 子重集{x1 a1,x2 a2, ,xk ak}的一个全排列，称为S的一个r 排列。

（（（

（（