组合相关基础知识学习笔记

其实是一些很基础的东西

组合数

定义

定义 (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=0n1(im1)\binom{n}{m}=\sum_{i=0}^{n-1}\binom{i}{m-1}

考虑固定编号最大的,再在剩下的里面取m1m-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)(nmmi)\binom{n}{m}=\sum_{i=0}^{m}\binom{m}{i}\binom{n-m}{m-i}

枚举前mm个物品选了几个

Lucas定理

待填坑

斯特林数

第一类斯特林数

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

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

  2. 生成函数:

感谢你的赞赏!