证明组合递推公式

证明组合的递推公式

C(n,m)=C(n-1,m-1)+C(n-1,m)

 

1.将C(n,m)理解为在n个物体中取m个物体的方案总数；

2.现在将n个物体分成一号堆n-1个物体和二号堆1个物体；

3.n个物体的二号堆只有1个物体，分为取和不取两种情况；

4.若取，则从一号堆的n-1个物体中取出m-1个物体，为C(n-1,m-1)；

5.若不取，则从一号堆的n-1个物体中取出m个物体，为C(n-1,m)；

6.因此，C(n,m)的方案总数为C(n-1,m-1)和C(n-1,m)的总和；

7.证毕。