其实是一些很基础的东西

组合数

定义

定义 (nm)\binom{n}{m} 为在将 nn 个元素中取出 mm 个元素的方案数，显然有

一些性质

基本组合恒等式

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

nn个物品选或不选有2n2^n种方案，等于选0,1,...,n0,1,...,n种方案之和

按定义展开即可

(nm)=∑i=0n−1(im−1) \binom{n}{m}=\sum_{i=0}^{n-1}\binom{i}{m-1}

考虑固定编号最大的，再在剩下的里面取m−1m-1个

(n+k+1n)=∑i=0n(i+ki) \binom{n+k+1}{n}=\sum_{i=0}^{n}\binom{i+k}{i}

杨辉三角斜行的性质，画个杨辉三角就能看出来了

(nm)=∑i=0m(mi)(n−mm−i) \binom{n}{m}=\sum_{i=0}^{m}\binom{m}{i}\binom{n-m}{m-i}

枚举前mm个物品选了几个

Lucas定理

待填坑

斯特林数

第一类斯特林数

  1. 定义： 表示将nn个物品分成mm个无序环的方案数

    考虑第nn个物品可以单独放进一个环，或者放在另外任意一个物品后面

  2. 生成函数: