组合数学
一些基础的
组合数
(nchoose m)=(n-1choose m)+(n-1choose m-1)
(sum{nchoose i}=2^n)
(sum_{i=0}^m{ichoose n}={m+1choose n+1})
卡特兰数
(C(n)=sum_{i=0}^{n-1}C(i)C(n-i-1))
(C(0)=1)
(C(n)={2nchoose n}-{2nchoose n-1}=frac{2nchoose n}{n+1})
其前几项为（从第0项开始） : (1, 1, 2, 5, 14, 42, 132, 429, 1430)
第一类斯特林数
([^n_k])表示将(n)个两两不同的元素，划分为(k)个非空圆排列的方案数。
([^n_k]=[^{n-1}_{k-1}]+(n-1)[^{n-1}_{ k}])
第二类斯特林数
一些恒等式
(sum{nchoose i}{ichoose j} = sum{nchoose j}{n-jchoose i-j})
(sum{nchoose i}{mchoose k-i}={n+m choose k})（范德蒙德卷积）
(sum{ichoose k}{n-ichoose m}={n+1choose k+m+1})
生成函数
概念
普通型生成函数(OGF)
(F(x)=sum_{i>=0}f_ix^i)
一些常见的(OGF):
(frac1{1-x}=1+x+x^2+...)
(frac1{1+x}=1-x+x^2-x^3+...)
指数型生成函数(EGF)
(F(x)=sum_{i>=0}frac{f_i}{i!}x^i)
当一类题卷积长成这样的时候：
(f(n)=sum{nchoose i}g(i)h(n-i))
我们推一推最后会推出(frac{f(n)}{n!}=sum{frac{g(i)}{i!}frac{h(n-i)}{(n-i)!}})
所以我们用(EGF)卷起来，最后系数乘上(n!)得到(f)。
一些常见的(EGF):
(e^x=sumfrac{x^i}{i!})（泰勒展开）
(e^{cx}=sumfrac{c^ix^i}{i!})
应用
组合生成函数：
(nchoose m)=([x^m](1+x)^n)
(n+m-1choose m-1)=([x^n]frac1{(1-x)^m})
第一、二类斯特林数：link
现在我们来证明一下上面的恒等式：(sum{nchoose i}{mchoose k-i}={n+m choose k})
({nchoose i}=[x^i](1+x)^n),({mchoose k-i}=[x^{k-i}](1+x)^m)
来，卷起来。
原式(=[x^k](1+x)^{n+m}={n+m choose k})
再来一个：(sum{ichoose k}{n-ichoose m}={n+1choose k+m+1})
我们要想卷起来，枚举的位置要是(x)的指数，那么我们用第二种。
({ichoose k}={(i-k)+(k+1)-1choose (k+1)-1}=[x^{i-k}]frac1{(1-x)^{k+1}})
同理({n-ichoose m}=[x^{n-i-m}]frac1{(1-x)^{m+1}})
卷起来，原式(=[x^{n-m-k}]frac1{(1-x)^{k+m+2}}={n+1choose k+m+1})