关于组合数的一些总结

1，组合数的常见恒等式

　　(1) \(\dbinom{n}{m}=\dbinom{n}{n-m}\)

　　(2)\(\dbinom {n}{m}=\dbinom{n-1}m+\dbinom{n-1}{m-1}\)

　　(3)\(\sum\limits_{k=0}^{n}\dbinom{r+k}{k}=\dbinom{r+n+1}{n}\)

　　(4) \(\sum\limits_{k=0}^n\dbinom{k}{m}=\dbinom{n+1}{m+1}\)

　　(5)\((a+b)^n=\sum\limits_{i=0}^n\dbinom{n}{i}a^ib^{n-i}\)

　　(6)\(\sum\limits_{k>=-n}^m\dbinom{r}{n+k}\dbinom{s}{m-k}=\dbinom{r+s}{n+m}\)

2，卡特兰数一般公式

　　(1) \(h(n)=\dfrac{1}{n+1}\dbinom{2n}{n}=\dbinom{2n}{n}-\dbinom{2n}{n-1}\)

　　(2) \(h(n)=\dfrac{4n-2}{n+1}h(n-1)\)

　　(3) \(h(n+1)=\sum\limits_{i=0}^nh(i)h(n-i)\)

3，卡特兰数的应用

　　(1) 由\(n\)个左括号和\(n\)个右括号组成的合法的括号序列数。

　　(2) 由\(n\)个节点构成的二叉树的方案数。

　　(3) 一个大小为\(n\)的进栈序列的出栈序列数。

　　(4) 圆上\(2n\)个点，将这些点用线段成对连起来而不交的方案数。

　　(5) 从\((0,0)\)走到\((n,n)\)不穿过线\((i,i)\)的方案数。

　　(6) \(n\)层阶梯切割成\(n\)个矩形的方案数。