组合数学 ¶

排列组合 ¶

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