组合数学之生成函数

1 生成函数

• $a_n$的ordinary generating function(ODF): $$G(x)=\sum_{n\ge 0}a_nx^n$$

1.1 组合

• 例1: $(x_0+x_1)^3$的展开式表示了3元集的所有子集, $(1+x)^3$的展开式的$x_k$系数表示了$k-$子集的数量
• 例2: 3红4蓝5绿球, 选$k$球的方法, 即$(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)$展开式中$x^k$的系数

1.2 斐波那契数

$$\begin{aligned} G(x)&=\sum_{n\ge 0}F_nx^n\\ &= F_0+F_1x+\sum_{n\ge 2}F_nx^n\\ &=x+ \sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n\\ \end{aligned}$$ $$xG(x)=\sum_{n\ge 0}F_nx^{n+1}=\sum_{n\ge 1}F_{n-1}x^{n}=\sum_{n\ge 2}F_{n-1}x^{n+1}$$ $$x^2G(x)=\sum_{n\ge 0}F_nx^{n+2}=\sum_{n\ge 2}F_{n-2}x^{n}$$ $$G(x)=x+(x+x^2)G(x)$$ $$\begin{aligned} G(x)&=\frac{x}{1-x-x^2}\\ &=\frac{1}{\sqrt 5}\cdot \frac{1}{1-\phi x}-\frac{1}{\sqrt 5}\cdot \frac{1}{1-\hat\phi x}\\ &= \frac{1}{\sqrt 5}\sum_{n\ge 0}(\phi x)^n-\frac{1}{\sqrt 5}\sum_{n\ge 0}(\hat\phi x)^n\\ &= \sum_{n\ge 0}\frac{1}{\sqrt 5}(\phi^n-\hat \phi^n )x^n \end{aligned}$$

其中$\phi = \frac{1+\sqrt 5}{2}$, $\phi = \frac{1-\sqrt 5}{2}$

因此

$$F_n=\frac{1}{\sqrt 5}(\phi^n - \hat\phi^n)=\frac{1}{\sqrt 5}(\frac{1+\sqrt 5}{2})^n -\frac{1}{\sqrt 5} (\frac{1-\sqrt 5}{2})^n$$

2 解递归式

• 步骤如下:
  • 给出$a_n$递归式:
  • 求$G(x)=\sum_{n\ge 0}a_nx^n$, 将右侧处理至含$G(x)$
  • 解出$G(x)$的表达式
  • 展开后, $x_n$的系数为$a_n$

2.1 生成函数的代数操作

2.2 展开生成函数

2.2.1 泰勒展开

$$G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n$$

2.2.2 几何序列

$$\frac{1}{1-x}=\sum_{n\ge 0}x^n$$

• 例如$G(x)=\sum_{i=1}^k\frac{a_i}{1-b_ix}$, 因此$a_n=\sum_{i=1}^k a_ib_i^n$

2.2.3 二项式定理

$$(1+x)^\alpha = \sum_{n\ge 0}\binom{\alpha}{n}x^n$$

例子: 多重集$S=\{x_1,x_2,\cdots, x_n\}$

$$(1+x_1+x_1^2+\cdots)(1+x_2+x_2^2+\cdots)\cdots(1+x_n+x_n^2+\cdots)=\sum_{m:S\to \mathbb N}\prod_{x_i\in S}x_i^{m(x_i)}$$

其中$m$是$S$中可能的多重集中的$x_i$的重数

$$\begin{aligned} (1+x+x^2+\cdots)^n&=\sum_{m:S\to \mathbb N}x_i^{m(x_1)+m(x_2)+\cdots+m(x_n)}\\ &=\sum_{multiset ~ M ~ on ~ S}x^{|M|}\\ &=\sum_{k\ge 0}\left(\binom{n}{k}\right)x^k \end{aligned}$$

而

$$(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}\binom{-n}{k}(-x)^k$$

因此

$$\left(\binom{n}{k}\right)=(-1)^k\binom{-n}{k}=\binom{n+k-1}{k}$$

3 卡特兰数

• $C_n$例子:
  • $n$对括号合法匹配的个数
  • $n+1$个数相乘, 不同的加括号方法
  • $n+1$叶节点的full binary tree的数量
  • $n\times n$方格中不超过对角线上方的monotonic paths的数量
  • $n+2$边凸多边形的三角形分割数
  • stack-sortable permutations of $\{1,\cdots, n\}$
  • tile a stairstep shape of height n with n rectangles

3.1 解卡特兰数

卡特兰数递归式: $C_0=1$, 对于$n\ge 1$, $C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}$

$$G(x)=\sum_{n\ge 0}C_n x^n$$ $$G(x)^2=\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^n$$ $$xG(x)^2=\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^{n+1}= \sum_{n\ge 1}\sum_{k=0}^nC_kC_{n-1-k}x^{n}$$ $$G(x)=sum_{n\ge 0}C_nx^n=C_0+\sum_{n\ge 1}\sum_{k=0}^nC_kC_{n-1-k}x^{n}=1+xG(x)^2$$ $$G(x)=\frac{1\pm(1-4x)^{1/2}}{2x}$$

因为$\lim _{x\to 0}G(x)=C_0=1$

所以

$$G(x)=\frac{1-(1-4x)^{1/2}}{2x}$$ $$\begin{aligned} (1-4x)^{1/2}&=\sum_{n\ge 0}\binom{1/2}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\binom{1/2}{n}(-4x)^n\\ &=1-4x\sum_{n\ge 0}\binom{1/2}{n+1}(-4x)^n \end{aligned}$$ $$G(x)=\frac{1-(1-4x)^{1/2}}{2x}=2\sum_{n\ge 0}\binom{1/2}{n+1}(-4x)^n$$ $$\begin{aligned} C_n&=2\binom{1/2}{n+1}(-4)^n\\ &=2\cdot (\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-1)}{2})\cdot\frac{1}{(n+1)!}(-4)^n\\ &=\frac{2^n}{(n+1)!}\prod_{k=1}^n(2k-1)\\ &=\frac{2^n}{(n+1)!}\prod_{k=1}^n\frac{(2k-1)2k}{2k}\\ &=\frac{1}{(n+1)!n!}\prod_{k=1}^n(2k-1)2k\\ &=\frac{(2n)!}{n!(n+1)!}\\ &=\frac{1}{n+1}\binom{2n}{n} \end{aligned}$$

4 快排分析

递归式

$T_0=T_1=0$, 而 $T_n = \frac{1}{n}\sum_{k=1}^n(n-1+T_{k-1}+T_{n-k})$

解OGF

• 详见讲义, 注意卷积的使用