组合数学里一些比较重要(有意思)的结论

starletkiss 2020-01-29

1.过n个有标志顶点的树的数目等于nn-2.(Cayley定理)

2.在n个不同元素中取r个作允许重复的组合,其组合数为C(n+r-1,r).

3.从A={1,2,…,n}中取r个作不相邻的组合,其组合数为C(n-r+1,r).

4.线性方程x1+x2+…+xn=b的非负整数解的个数是(n+b-1,b).

5.C(m+n,m)=C(m+n,n)=C(n,r)=C(n,n-r).

6.C(n,r)=C(n-1,r)+C(n-1,r-1)(杨辉三角、Pascal 三角)

牛顿二项式定理:

组合数学里一些比较重要(有意思)的结论

7.C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1),C(n,0).

8.C(n,l)*C(l,r)=C(n,r)*(n-r,l-r).

9..C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m.

10.C(n,0)-C(n,1)+C(n,2)+…±C(n,n)=0(由牛顿二项式定理代入可证)

11.C(m+n,r)=C(m,0)*C(n,r)+C(m,1)*C(n,r-1)+…+C(m,r)*C(n,0),r<=min(m,n).

12.(由上式可得)若m<=n,则有C(m+n,m)=C(m,m)*C(n,0)+C(m,m-1)*C(n,1)+…+C(m,0)*C(n,m)=C(m,0)*C(n,0)+C(m,1)*C(n,1)+…+C(m,m)*C(n,m).

13.C(r,r)+C(r+1,r)+…+C(n,r)=C(n+1,r+1).

 (待更新...)

相关推荐