组合基础1 组合数 二项式定理 卡特兰数 生成函数基础

组合数

( n m ) = n ! m ! ( n − m ) ! \binom{n}{m}=\frac{n!}{m!(n-m)!} (mn)=m!(nm)!n!
可用Lucas定理和扩展Lucas计算。同时也是一个 m m m次多项式,可用多项式算法计算。

插板数

n n n个无区别的人分为 m m m个无区别的可空组有 ( n + m − 1 n ) \binom{n+m-1}{n} (nn+m1)种方法。

二项式定理

( a + b ) n = ∑ i = 0 n ( n i ) a i b n − i (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i} (a+b)n=i=0n(in)aibni
考虑两种方向。

练习题

∑ i = 0 n ( n i ) 2 \sum_{i=0}^n\binom{n}{i}^2 i=0n(in)2

由二项式定理, ( x + 1 ) 2 n = ( x + 1 ) n ( x + 1 ) n (x+1)^{2n}=(x+1)^n(x+1)^n (x+1)2n=(x+1)n(x+1)n ∑ i = 0 2 n ( 2 n i ) x i = ∑ j = 0 n ∑ k = 0 n ( n j ) ( n k ) x j x k \sum_{i=0}^{2n}\binom{2n}{i}x^i=\sum_{j=0}^n\sum_{k=0}^n\binom{n}{j}\binom{n}{k}x^jx^k i=02n(i2n)xi=j=0nk=0n(jn)(kn)xjxk
比较两边的 n n n次项系数可得 ( 2 n n ) = ∑ j + k = n ( n j ) ( n k ) = ∑ j + k = n ( n j ) ( n n − k ) = ∑ j = 0 n ( n j ) 2 \binom{2n}{n}=\sum_{j+k=n}\binom nj\binom nk=\sum_{j+k=n}\binom nj\binom n{n-k}=\sum_{j=0}^n\binom{n}{j}^2 (n2n)=j+k=n(jn)(kn)=j+k=n(jn)(nkn)=j=0n(jn)2

卡特兰数

C a t n = ( 2 n n ) − ( 2 n n − 1 ) Cat_n=\binom{2n}{n}-\binom{2n}{n-1} Catn=(n2n)(n12n)
C a t n = ∑ i = 0 n − 1 C a t i ⋅ C a t n − 1 − i Cat_n=\sum_{i=0}^{n-1}Cat_i\cdot Cat_{n-1-i} Catn=i=0n1CatiCatn1i
前几项为 1 1 1 2 2 2 5 5 5 14 14 14 42 42 42,可用于打表。

由第二个式子可用生成函数的方法推得第一式,但我不会。

卡特兰数等于在非负坐标方格图上从 ( 0 , 0 ) (0,0) (0,0)走到 ( n , n ) (n,n) (n,n)而不跨越直线 y = x y=x y=x的方案数,由此可得上式的一种证明方法。答案是总方案数 ( 2 n n ) \binom{2n}{n} (n2n)减去不合法的方案数,考虑折线第一次穿越 y = x y=x y=x的时候,将这之前(含)的折线沿 y = x y=x y=x翻转,再将之后的接到上面,发现终点变为了 ( n + 1 , n − 1 ) (n+1,n-1) (n+1,n1)。于是不合法的方案数就是从 ( 0 , 0 ) (0,0) (0,0) ( n + 1 , n − 1 ) (n+1,n-1) (n+1,n1)且限制第一步往右走的方案数,即 ( 2 n n − 1 ) \binom{2n}{n-1} (n12n)
《组合基础1 组合数 二项式定理 卡特兰数 生成函数基础》
*from http://lanqi.org/skills/10939/

卡特兰数还等于合法括号序列数、合法出栈序列数、二叉树数、多边形三角剖分数等。

生成函数

https://blog.csdn.net/myjs999/article/details/81042100

    原文作者:myjs999
    原文地址: https://blog.csdn.net/myjs999/article/details/89435739
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞