组合数学中的几个结论

1. 鸽巢原理 :把 n+1 个物体放入n个盒子中，必有一个盒子包含两个或更多的物品
2. n元集合的r圆排列数为p(n,r)/r;
3.从（0，0）点沿水平和垂直道路可以走到（m，n）点，方法有c(m+n,m)种
4.多重集合M={a1,a2,a3,...,ak}的r组合数为c(k+r-1,r)
5.正整数n的有序k分拆的个数为c(n-1,k-1)
6.n的无序k分拆数为B(n,k)，满足B(n+k,k)=B(n,1)+B(n,2)+B(n,3)+...+B(n,k)
7.分配问题，将n个球放入r个盒子中，根据不同的情形，有以下几种：

其中S(n,k)为第二类Stirling数；表示n元集合的k分划的个数
8.n个数的全错排数D（n）=n！（1-1/1!+1/2!-1/3!+...+(-1)^r*1/n!)
9.一个小孩上楼梯，一次可以上一阶或两阶，则上n阶台阶的方法数是f(n);f(n)是

Fibonacci数列，f(1)=1;f(2)=2;
10.利用生成函数求解有约束的排列问题
11、Polya计数定理 求解翻转、旋转等价问题