组合数学

排列组合

• 圆排列: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=0||n=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}...\)

---