组合数学排列组合基本问题总结 -一个渣渣

1. 从n个不同元素中允许重复地选取r个元素的组合数是C(n+r-1,r)

证明思路：采用划归转化的思想，将可重组合转化为无重组合，证明的一般思路：

1. 先设出一组有序序列

2. 对该序列进行变换

3. 将变换后的序列转化为在一个区间里求无重组合。

证明过程：

2. 可重排列

3. 可重组合与方程解的个数的对应关系

设n个盒子放的数量分别为 x1,x2,x3.....xn。那么满足 x1+x2+x3+x4+....xn=r(xi>=q)

为了转化为我们熟悉的x1+x2+x3...=d(xi>=1)，我们需要做一些变化

设yi=xi-q+1，那么 yi>=1,

y1+y2+y3....=r-n*q+n(yi>=1)

这样就转化成了n个数，每个数大于等于1，问最后和为 r-n*q+1的解有多少个，问题就变成了n个盒子去分r-n*q+1个球的问题，采用隔板原理即可。r-n*q+n-1个空，插n-1个隔板即可。

最后答案：C(n+(r-nq)-1,r-nq)

4. 相关组合恒等式的证明

（1） C(n, r)=C(n-1,r)+C(n-1,r-1)

证明方式：任选一个数 c,那么从n个数里面选r个数，只有两种情况，第一，包含c，第二不包含c。

包含c，那么剩下去n-1个里面选 r-1个即可

不包含c，那么去n-1个里面选r个即可。

所以，原式得证

（2） C(n,l)C(l,r)=C(n,r)C(n-r,l-r)

证明方式：左式：班级共n位同学，选出l位班委，班委中选出r位为核心；

右式：先从n个同学中选出r个核心，再从剩下的n-r中选剩下的l-r班委

（3） C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1)+… + C(n+1,1)+C(n,0).

证明方式：和第1题非常类似，考虑包含1个，2个....r个的情况

(1)组合中不含a1，从a1以外的(n+r)个元素取r个元素，组合数：C(n+r,r);

(2)组合中含a1，不含a2，从除a2外的(n+r-1)个元素取(r-1)个元素：组合数 C(n+r-1,r-1); … (i)组合数中含a1，a2，…,ai-1,但不含ai，则从(n+r+1-i)元素中取(r-(i-1))个元素，组合数:C(n+r-i+1,r-i+1);

(r)组合数中含a1，a2，…,ar, 只有这一种情形 C(n,0)。

由加法原理，得证。

（4） C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+ …+C(m,r)C(n,0)

证明思路：考虑用m个蓝色乒乓球，n个红色乒乓球来证明。

5. 二项式定理

转载自原文链接, 如需删除请联系管理员。