排列组合
- 圆排列:n个中选k个组成一个圈的方案数：$\frac{A_{n}^k}{k}$
- 项链排列:${\frac{A_{n}^k}{2k}}$
- 错位排列:n个数的所有错排方案数的递推公式为${f(n)=(n-1)*(f(n-1)+f(n-2))}$,前几项为$0、1、2、9、44、265$
- 多重排列:设$S={n1*a1,n2*a2,…,nk*ak}$，则所有的方案数为$\frac{n!}{n1!*n2!*…*nk!}$
- 不相邻组合:[1,n]个中选k个组成不相邻的排列的方案数为：$C_{n-k+1}^k$
- 可重组合:设S=${n1*a1,n2*a2,…,nk*ak}$，在S中选r个，则所有的方案数为${C_{r+k-1}^{k-1}}$
方法：隔板法，捆绑法…
扩展:
- 二项式定理:$(a+b)^n=\sum_{k=0}^nC_n^ka^{n-k}b^k$
- 多项式定理:$(x1+x2+…+xk)^n=\sum_{n1+n2+…+nk=n}\frac{n!}{n1!n2!…nk!}\prod_{i=1}^kx_i^{ni}$
- 格路问题:$(0,0)$点走到$(m,n)$点的方案数为$C_{m+n}^n$
母函数
普通型母函数
主要求组合的方案数。 形如${a_0+a_1x^1+a_2x^2+…+a_nx^n}$
指数型母函数
主要求多重排列数。 形如${a_0+\frac{a_1x}{1!}+\frac{a_2x^2}{2!}+…\frac{a_nx^n}{n!}}$
特殊的数
斐波那契数
- 递推式:$f(n)=f(n-1)+f(n-2)$
- 二阶常系数递归公式:$f(n)=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]$
前几项为1、1、2、3、5、8…
卡特兰数
常见公式：
- $H_n=\frac{C_{2n}^n}{n+1}$
- $H_n=\frac{H_{n-1}(4n-2)}{n+1}$
- $H_n=1 \;\;(n=0n=1)$ $H_n=\sum_{i=1}^nH_{n-i}H_{i-1} (n\geq 2)$
- $H_n=C_{2n}^n-C_{2n}^{n-1}$
前几项为：1、1、2、5、14、42、132…
斯特林数
第一类Stirling数
- 递推式:${S_u(n,k)=S_u(n-1,k-1)+(n-1)*S_u(n-1,k)}\;\;\;S_u(0,0)=1$
第二类Stirling数
递推式:${S(n,k)=S(n-1,k-1)+k*S(n-1.k)}\;\;\;S(0,0)=1$
线性公式:${S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^iC_k^i(k-i)^n}$
贝尔数
递推式:${B_{n+1}=\sum_{k=0}^nC_n^kB_k}$
根据第二类斯特林数:${B_n=\sum_{k=0}^nS(n,k)}$
拓展：贝尔三角形求解。
前几项为：1、1、2、5、15、52、203…
伯努利数
- 等幂求和:
$S_mn=\frac{1}{m+1}\sum_{k=0}^mC_{m+1}^kn^{m-k+1}$
$\sum_{i=1}^ni^k=\frac{1}{k+1}\sum_{i=1}^{k+1}C_{k+1}^iB_{k-i+1}(n+1)^i$
递推式:${\sum_{k=0}^nB_kC_{n+1}^k=0}\;\;\;(B_0=1)$
$B_n=-\frac{1}{n+1}[C_{n+1}^0B0+C_{n+1}^1B1+…+C_{n+1}^{n-1}B_{n-1}]$
前几项为：$1、-\frac{1}{2}、\frac{1}{6}、0、\frac{1}{30}…$
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/08/19/comb/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！