组合数学的问题

1. 从n个不同元素中允许重复地选取r个元素的组合数是C(n+r-1,r) 证明思路：采用划归转化的思想，将可重组合转化为无重组合，证明的一般思路： 1. 先设出一组有序序列 2. 对该序列进行变换 3. 将变换后的序列转化为在一个区间里求无重组合。

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. 二项式定理