组合数
从n个物品中选m个，那么就有(frac{n!}{m!(n-m)!})种选法，即为(C^m_n)或(inom{n}{m})
有几个公式：
二项式定理：((x+y)^n=sum_iC_n^ix^iy^{n-i})
二项式反演: $$f_i=sum_jC_i^jg_jLeftrightarrow g_i=sum_j(-1){i-j}C_ijf_j$$
可重组合：
从n个物品中选m个，每个物品都可以任意选，方案数为(inom{n+m-1}{m})
容斥
简单来说，就是要求$$|Ucap ar A_1cap ar A_2cap cdots cap ar A_k|$$
这个东西就等于$$sum_{Ssubseteq A}(-1)^{|S|}|Ucap S_1cap S_2cap cdotscap S_{|S|}|$$
min-max容斥 ：
有两个显然结论：
-
(min{max{a,b},c}=max{min{a,c},min{b,c}})
-
(max{a,b}=a+b-min{a,b})
然后就有$$max_{i=1}^n{a_i}=sum_{Tsubseteq A}(-1)^{|T|+1}min{T}$$
卡特兰数
卡特兰数(C_n=sum_{i=0}C_iC_{n-i-1})，(C_0=C_1=1)。
还有一个递推式(C_n=C_{n-1}(4n-2)/(n+1))。
(C_n=frac{C_{2n}^n}{n+1}=C_{2n}^n-C_{2n}^{n+1})。
还有一个很像的数列是(F_n=F_{n-1}+sum_{i=0}^{n-1}F_iF_{n-i-1})
他的递推式是(F_n(n+1)=(6n-3)F_{n-1}-(n-2)F_{n-2})
斯特林数
第二类斯特林数
把n个物品放到m个无序集合且不允许集合为空的方案数为第二类斯特林数，记为(S(n,m))或(egin{Bmatrix}n\mend{Bmatrix})。
递推式：(S(n,m)=S(n-1,m-1)+m*S(n-1,m))考虑定义，就是枚举下一个物品单独为一个集合或和其他的元素同在一个集合(或是否是这个集合的最后一个元素)。
容斥式子：(S(n,m)=frac{1}{m!}sum_k(-1)^kC_m^k(m-k)^n)
其意义就是枚举空的集合的数量，因为集合是无序的，所以要除以(m!)。
如果把(frac{1}{m!})乘进去，可以得到(S(n,m)=sum_kfrac{(-1)^k}{k!}frac{(m-k)^n}{(m-k)!})，这样就可以直接卷积。
性质： $$nk=sum_{i=0}kS(k,i)cdot i!cdot C_n^i$$
左边就是把k个物品放到n个集合里，右边就是枚举放到哪几个集合里。
第一类斯特林数
第一类斯特林数就是把n个物品划分为m个圆排列的方案数，记为(s(n,m))或(left[egin{matrix}n\mend{matrix} ight])。
递推式：(s(n,m)=s(n-1,m-1)+(n-1)s(n-1,m))。因为这个是圆排列，所以每一个元素有n-1中插法。
还有有符号的第一类斯特林数，记为(s_s(n,m)=(-1)^{n+m}s_u(n,m))。
(s(n,m))的生成函数是(prod_{i=0}^{n-1}(x+i))，(s_s(n,m))的生成函数是(prod_{i=0}^{n-1}(x-i))。
一些性质(不带下标默认为无符号):
- (x^{underline{n}}=sum_is_s(n,i)x^i,x^{overline{n}}=sum_is(n,i)x^i)
- (sum_is(n,i)=n!)
- (sum_is_s(n,i)=[n=0])