集合与图论学习笔记04

定理

抽屉原理

简单形式

将 $n$ 个物品放入 $m$ 个抽屉，如果 $n > m$，则至少有一个抽屉包含至少两个物品。

数学表述：如果 $n > m$，则存在一个抽屉至少有 $\lceil \frac{n}{m} \rceil=\lfloor \frac{n-1}{m} \rfloor + 1$ 个物品。

推广形式

将 $n$ 个物品放入 $m$ 个抽屉，则至少有一个抽屉包含至少 $\lceil \frac{n}{m} \rceil$ 个物品，且至少有一个抽屉包含至多 $\lfloor \frac{n}{m} \rfloor$ 个物品。

应用例子

1.映射个数

从 $m$ 元集到 $n$ 元集的映射个数为：

$\lfloor \frac{n-1}{m} \rfloor + 1$

2.序列选取

$a_1,...,a_{n^{2}+1}$ 是由 $n^{2}+1$ 个不同实数选取的一个序列，则一定可以选取 $n+1$ 个数的严格单调递增或者单调递减的子序列

容斥原理

两个集合的情况

对于有限集 $A$ 和 $B$： $|A \cup B| = |A| + |B| - |A \cap B|$

三个集合的情况

对于有限集 $A$, $B$, $C$： $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

一般形式（n个集合）

对于有限集 $A_1, A_2, \dots, A_n$： \[ \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}| \]

等价地： \[ \left| \bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \ne S \subseteq \{1,2,\dots,n\}} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right| \]

补集形式（计数都不在其中的元素）

设全集为 $U$，则： \[ \left| \bigcap_{i=1}^n A_i^c \right| = |U| - \sum_{i=1}^n |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + \dots + (-1)^n |A_1 \cap A_2 \cap \dots \cap A_n| \]

应用例子

错位排列

$n$ 个元素的排列，没有元素在原始位置的方案数： $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

欧拉函数

小于 $n$ 且与 $n$ 互质的正整数个数： $\varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$ 其中 $p$ 取遍 $n$ 的所有质因数。

包含排斥问题

从 $1$ 到 $1000$ 中不被 $2,3,5$ 整除的整数个数： $1000 - \lfloor 1000/2 \rfloor - \lfloor 1000/3 \rfloor - \lfloor 1000/5 \rfloor + \lfloor 1000/6 \rfloor + \lfloor 1000/10 \rfloor + \lfloor 1000/15 \rfloor - \lfloor 1000/30 \rfloor$

满射函数计数

从 $m$ 元集到 $n$ 元集的满射函数个数： $\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^m$

递推与生成函数

母函数（生成函数）定义与分类

母函数基本思想

母函数是一种形式幂级数，其系数编码某个数列的信息，通过代数运算处理数列间的组合关系

母函数作为形式幂级数时，不考虑收敛性，只进行代数运算。在解析应用中需要考虑收敛半径

普通生成函数（OGF）

对于数列 $\{a_n\}_{n\ge 0}$，其普通生成函数为： $A(x) = \sum_{n=0}^{\infty} a_n x^n$

用于无标记对象的组合计数，系数 $a_n$ 通常表示大小为 $n$ 的对象的个数

常见OGF

常数序列 $1,1,1,\dots$：$\frac{1}{1-x}$
二项式系数 $\binom{m}{n}$：$(1+x)^m$
斐波那契数列 $F_n$：$\frac{x}{1-x-x^2}$

指数生成函数（EGF）

对于数列 $\{a_n\}_{n\ge 0}$，其指数生成函数为： $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$

用于有标记对象的组合计数，系数 $a_n$ 表示大小为 $n$ 的有标记结构的个数

常见EGF

常数序列 $1,1,1,\dots$：$e^x$
排列数 $n!$：$\frac{1}{1-x}$
圆排列数 $(n-1)!$：$-\ln(1-x)$

狄利克雷生成函数（DGF）

对于数列 $\{a_n\}_{n\ge 1}$，其狄利克雷生成函数为： $A(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$

用于数论函数的乘法卷积，在解析数论中应用广泛

常见DGF

常数函数 $1$：$\zeta(s)$（黎曼ζ函数）
莫比乌斯函数 $\mu(n)$：$\frac{1}{\zeta(s)}$
欧拉函数 $\varphi(n)$：$\frac{\zeta(s-1)}{\zeta(s)}$

母函数运算与组合结构

加法运算

$C(x) = A(x) + B(x)$

有 $c_n=a_n+b_n$

乘法运算
- OGF乘法：$C(x) = A(x)B(x)$ 对应有序对或笛卡尔积即 $c_n=\Sigma_{i=0}^{n}a_ib_{n-i}$
- EGF乘法：$C(x) = A(x)B(x)$ 对应有标记对象的乘积结构即 $c_n=\Sigma_{i=0}^{n}C(n,i)a_ib_{n-i}$
复合运算

$C(x) = A(B(x))$ 对应结构的复合，如： - - OGF复合：序列的替换

设 $A(x) = \sum_{n\ge 0} a_n x^n$, $B(x) = \sum_{n\ge 0} b_n x^n$，且 $b_0 = 0$

复合生成函数为： $C(x) = A(B(x)) = \sum_{k\ge 0} a_k [B(x)]^k$

- EGF复合：结构的组合（如集合的划分）

设 $A(x) = \sum_{n\ge 0} a_n \frac{x^n}{n!}$, $B(x) = \sum_{n\ge 1} b_n \frac{x^n}{n!}$（$b_0=0$）

复合生成函数为： $C(x) = A(B(x)) = \sum_{k\ge 0} a_k \frac{[B(x)]^k}{k!}$

母函数运算的性质

递推关系的求解

线性常系数齐次递推关系

对递推关系 $a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k} = 0$

其中给出初值 $a_0=d_0,...,a_{k-1}=d_{k-1}$

有递推关系对应的特征多项式 $C(x)=x^k+c_1x^{k-1}+...+c_k$

母函数 $G(x)=a_0+a_1x+...$

$x^{k}:a_{k}+c_1a_{k-1}+c_{2}a_{k-2}+...+c_{k-1}a_1+c_ka_0=0$

$x^{k+2}:a_{k+1}+c_1a_{k}+c_{2}a_{k-1}+...+c_{k-1}a_2+c_ka_1=0$

$x^{k+2}:a_{k+2}+c_1a_{k+1}+c_{2}a_{k}+...+c_{k-1}a_3+c_ka_2=0$

$...$

对齐，把每一列乘上对应冒号左边的数可以得到母函数减去一个多项式 \[ \begin{align*} & [G(x)-(a_0+a_1x+...+a_{k-1}x^{k-1})] \\ +& c_1x[G(x)-(a_0+a_1x+...+a_{k-2}x^{k-2})]\\ +&c_2x^2[G(x)-(a_0+a_1x+...+a_{k-3}x^{k-3})]\\ +&...\\ +&c_{k-1}x^{k-1}[G(x)-a_0] \\ +&c_kx^kG(x) \\ =&0 \end{align*} \] 把母函数放在一起，整理即：

$(1+c_1x+c_2x^2+...+c_kx^k)G(x)=\sum_{i=0}^{k-1}[c_ix^i(\sum_{j=0}^{k-1-i}a_jx_j)]$

我们定义 $c_0=1$ ，令 $P(x)=\sum_{i=0}^{k-1}[c_ix^i(\sum_{j=0}^{k-1-i}a_jx_j)]$

令 $R(x)=1+c_1x+c_2x^2+...+c_kx^k=x^kC(\frac{1}{x})$

那么有 $G(x)=\frac{P(x)}{R(x)}$

$C(x)$ 在复数域上有 $n$ 个根，设 $C(x)=(x-\alpha_1)^{k_1}(x-\alpha_2)^{k_2}...(x-\alpha_t)^{k_t}$ 其中 $\sum_{a=1}^{t}=n$

则 $R(x)=(1-\alpha_1x)^{k_1}(1-\alpha_2x)^{k_2}...(1-\alpha_tx)^{k_t}$ \[ G(x) = \frac{P(x)}{(1-\alpha_1x)^{k_1}(1-\alpha_2x)^{k_2}...(1-\alpha_tx)^{k_t}} \\\\ = \frac{P_1(x)}{(1-\alpha_1x)^{k_1}}+\frac{P_2(x)}{(1-\alpha_2x)^{k_2}}+...+\frac{P_t(x)}{(1-\alpha_tx)^{k_t}} \\\\ \] 对每一项 $P_i(x)$ 都是次方不超过 $k_i-1$ 的多项式 \[ \frac{P_i(x)}{(1-\alpha_ix)^{k_i}}=\frac{A_{i1}}{1-\alpha_ix}+\frac{A_{i2}}{(1-\alpha_ix)^{2}}+...+\frac{A_{ik_i}}{(1-\alpha_ix)^{k_i}} \]

其中 $A_{ij}$ 为常数

那么再对每一个项做幂级数展开

对照 $G(x)=a_0+a_1x+...$

有 \[a_n=\sum_{i=1}^{t}\sum_{j=1}^{k_i}A_{ij}C(j+n-1,n)\alpha_i^n\]

无重根的项

这部分设有 $r_1$ 个

也就是 $k_i=0$

对应有 $a_{n1}=\sum_{i=1}^{r_1}A_i\alpha_i^n$

复数根的项

这部分设有 $r_2$ 个

也有 $k_i=0$

设必定一对共轭复根 $\alpha_1=\rho e^{i\theta},\alpha_2=\rho e^{-i\theta}$

在幂级数展开的时候$\frac{A_1}{1-\alpha_1x}+\frac{A_2}{1-\alpha_2x}$导致的$x^{n}$的系数

\[ & A_1\alpha_1^n+A_2\alpha_2^n \\ = & A_1\rho e^{i\theta}+A_2\rho e^{-i\theta}\\ = &A_1\rho^n(\cos(n\theta)+i\sin(n\theta)) + A_2\rho^n(\cos(n\theta)-i\sin(n\theta))\\ = &(A_1+A_2)\rho^n\cos(n\theta)+i(A_1-A_2)\rho^n\sin(n\theta)\\ = &A\rho^n\cos(n\theta)+B\rho^n\sin(n\theta) \]

有重根的项

展开时由二项式定理

$a_n=\sum_{j=1}^kA_jC(j+n-1,n)\alpha^n=\sum_{j=1}^kA_jC(j+n-1,j-1)\alpha^n$

这里出现了一个关于 $n$ 的 $j-1$ 次多项式

也就是 $a_n=(h_1n^{k-1}+h_2n^{k-2}+...+h_k)\alpha^n$

这里 $h_i$ 待定

然后通过把所有项加起来即可得到通项公式

求递推的时候就可以通过求特征多项式的根，按照上面的形式通过用初值待定系数求出相应的系数，最后求出通项

模型

### 模型 4.1 全排列

取 $n$ 个互不相同的元素的全体进行排列，称为 $n$ 的全排列，方案数为 \[n!\]

模型 4.2 排列

从 $n$ 个元素种选取 $r$ 个元素按顺序排成一列，称为 $r-$排列，方案数为\[P(n,r)=\frac{n!}{(n-r)!}\]

可以看作 $n$ 个球里面选取 $r$ 个球做上标记放入 $r$ 个不同的盒子中，不允许空盒，每个盒子中最多有 $1$ 个球的方法数

模型 4.3 组合

从 $n$ 个元素种选取 $r$ 个元素不考虑排列的顺序，称为 $r-$组合，方案数为\[C(n,r)=\binom{n}{r}=C^{r}_{n}=\frac{n!}{r!(n-r)!}\]

可以看作 $n$ 个球里面选取 $r$ 个球做上标记放入 $r$ 个相同的盒子中，不允许空盒，每个盒子中最多有 $1$ 个球的方法数

另一方面，这两个模型的区别在于盒子是否相同， $r$ 个球放入 $r$ 个不同的盒子里面的方法数为 $r!$ ，这 $r!$ 个方法在盒子相同时是重复的，算作 $1$ 种情况，得到 $C(n,r)=\frac{P(n,r)}{r!}$ ，这里的 $r!$ 称为组合的重复度

模型 4.4 圆排列

从 $n$ 个元素种选取 $r$ 个元素按顺序排成一个圆形，称为 $r-$圆排列，方案数为\[Q(n,r)=\frac{P(n,r)}{r}\]

可以看作 $n$ 个球里面选取 $r$ 个球做上标记放入 $r$ 个不同的盒子中把盒子排成一个圈，不允许空盒，每个盒子中最多有 $1$ 个球的方法数

另一方面，对数量为 $r$ 的一个排列，不管哪一个元素为头哪一个元素为尾，这 $r$ 种排列在圆排列下均为 $1$ 种情况，得到 $Q(n,r)=\frac{P(n,r)}{r}$

模型 4.5 可重排列

最基础的可重

从 $n$ 种元素中允许重复的选取 $r$ 次得到的考虑顺序的排列，方案数为 \[n^{r}\]

如果我们限制可以选取元素的次数，若 $a_i$ 取 $n_i$ 次并且 $n=n_1+n_2+...+n_k$

根据之前重复度的理论，全排列方案数为 \[\frac{n!}{n_1!n_2!...n_k!}\]，我们记这个为多重组合数 \[\binom{n}{n_1,n_2,...,,n_k}\]

考虑相邻元素不同

从 $n$ 种元素中允许重复的选取 $r$ 次得到的考虑顺序并且相邻的元素不同，方案数为\[n(n-1)^{r-1}\]

考虑每种元素至少出现一次

采用容斥原理解决

从 $n$ 种元素中允许重复的选取 $r$ 次得到的考虑顺序并且每种元素至少出现一次，方案数为 $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{r}$

证明：点击查看证明

定义坏事件 $A_i$ 为某种元素 $i$ 没有出现

要求的即为没有任何坏事件发生的事件 $N$，即$N=\bigcap_{i=1}^{n}A^{c}_{i}$

由容斥原理，$|N|=\sum_{k=0}^n (-1)^k \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|$

接下来计算 $\sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|$

先从 $n$ 种元素中任取 $k$ 种，讨论这 $k$ 种都不存在，方法数即为 $\binom{n}{k}(n-k)^{r}$

根据容斥原理，最终方法数为 $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{r}$

考虑每种选取的元素存在上限

记为 $ {n_1a_1,n_2a_2,…,n_k,a_k}$ 表示 $a_i$ 至多取 $n_i$ 次，若所有 $n_i\ge r$，平凡的，方案数为 \[n^r\]

考虑至少存在一个 $n_i<r$，采用容斥原理解决

从 $n$ 种元素中选 $r$ 个（可重复，有序），每种元素 $i$ 最多选 $n_i$ 次，且至少存在一个 $n_i < r$，并且 $\Sigma_{i=1}^n n_i > r$，方法数为

\[\sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \binom{r}{\;n_i+1\ (i\in S),\ r - \sum_{i \in S}(n_i+1)\;} \cdot n^{\,r - \sum_{i \in S}(n_i+1)}\]

其中多组合数\[\binom{r}{a_1, a_2, \dots, a_m, r - (a_1+\dots+a_m)} = \begin{cases} \frac{r!}{a_1! \, a_2! \dots a_m! \, (r - (a_1+\dots+a_m))!}, & \text{如果 } a_1+\dots+a_m \le r \\ 0, & \text{否则} \end{cases}\]

证明：点击查看证明

定义坏事件 $A_i$ 为某种元素 $i$ 被选了超过 $n_i$ 次

要求的即为没有任何坏事件发生的事件 $N$，即$N=\bigcap_{i=1}^{n}A^{c}_{i}$

由容斥原理，$|N|=\Sigma_{S\subseteq\{1,2,3,...,n\}}(-1)^{|S|}|\bigcap_{i\in S}A_i|$

接下来计算 $S$

考虑先分配 $n_i+1$ 个位置给 $i$，再分配 $n_j+1$ 个位置给 $j$ …最后剩下的元素给以下的选取方式：从 $n$ 种元素中无上限选取 $r-\sum_{i \in S} (n_i + 1)$ 个元素

方法数为 $\binom{r}{\;n_i+1\ (i\in S),\ r - \sum_{i \in S}(n_i+1)\;}n^{r-\sum_{i \in S} (n_i + 1)}$

根据容斥原理，方法数即为 $\sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \binom{r}{\;n_i+1\ (i\in S),\ r - \sum_{i \in S}(n_i+1)\;} \cdot n^{\,r - \sum_{i \in S}(n_i+1)}$

考虑相邻元素不同且每种元素至少出现一次

从 $n$ 种元素中选 $r$ 个（可重复，有序），相同元素不能相邻，且每种元素至少出现一次，方法数为

\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)(n-k-1)^{r-1}\]

证明：点击查看证明

设全集 $U$ 为相邻不同的排列数：$n(n-1)^{r-1}$。

定义坏事件 $A_i$ 表示”元素 $i$ 没有出现”

由容斥原理： \[N = \sum_{j=0}^n (-1)^j \binom{n}{j} f(n-j, r)\]

其中 $f(k, r)$ = 用 $k$ 种颜色染 $r$ 个位置且相邻不同的排列数 = $k(k-1)^{r-1}$（当 $r \ge 1$ 且 $k \ge 1$）。

因此： \[N = \sum_{j=0}^n (-1)^j \binom{n}{j} (n-j)(n-j-1)^{r-1}\]

模型 4.6 可重组合

最基础的可重

从 $n$ 种元素中允许重复的选取 $r$ 次得到的不考虑顺序的组合，方案数为 $C(n+r-1,r)$

可以看作 $r$ 个相同的球放入 $n$ 个不同的盒子中，允许空盒，允许每个盒子多于 $1$ 个球的方法数

证明：点击查看证明

我们从 $(1,2,3...,n)$ 中选可重组合 $(a_{1},a_{2},...,a_{r})$ 有序关系 $a_{1} \le a_{2} \le ...\le a_{r} \le n$

做映射 $(a_{1},a_{2},...,a_{r})\rightarrow (a_{1},a_{2}+1,...,a_{r}+r-1)$ 有序关系 $a_{1} < a_{2}+1 < ...< a_{r}+r-1 \le n-r+1$ ，得到这 $r$ 个数不同，得知

从 $(1,2,3...,n)$ 中选可重组合 $(a_{1},a_{2},...,a_{r})$ 对应从 $(1,2,3...,n,...,n+r-1)$ 中选不可重组合 $(a_{1},a_{2}+1,...,a_{r}+r-1)$

反过来从 $(1,2,3...,n,...,n+r-1)$ 中选不可重组合 $(b_{1},b_{2},...,b_{r})$ 有序关系 $b_{1} < b_{2} < ...< b_{r} \le n+r-1$

做映射 $(b_{1},b_{2},...,b_{r})\rightarrow (b_{1},b_{2}-1,...,b_{r}-r+1)$ 有序关系 $b_{1} \le b_{2}-1 \le ...\le b_{r}-r+1 \le n$，得到这 $r$ 个数可能相同，得知

从 $(1,2,3...,n,...,n+r-1)$ 中选不可重组合 $(b_{1},b_{2},...,b_{r})$ 对应从 $(1,2,3...,n)$ 中选不可重组合 $(b_{1},b_{2}-1,...,b_{r}-r+1)$

这是一个一一对应，所以它们方法数相同均为 $C(n+r-1,r)$

考虑每种元素至少出现一次

从 $n$ 种元素中允许重复的选取 $r$ 次得到的不考虑顺序并且每种元素至少出现一次的组合，方案数为\[C(r-1,n-1)\]

证明：点击查看证明

我们从 $(a_{1},a_{2},...,a_{n})$ 中先选一组不重复的 $(a_{1},a_{2},...,a_{n})$ ，接着就变成了从 $n$ 个元素中选取 $r-n$ 个可重元素，根据上面的结论，应该为 $C(n+(r-n)-1,r-n)=C(r-1,r-n)=C(r-1,n-1)$

考虑每种选取的元素存在上限

此外，如果限制可以选取元素的次数并且假定 $n_1,n_2,...n_k \ge r$ 结论是相同的

如果存在一个 $n_i < r$ 则需要采用容斥原理解决

从 $n$ 种元素中选 $r$ 个（可重复，无序），每种元素 $i$ 最多选 $n_i$ 次，且至少存在一个 $n_i < r$，方法数为\[\sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} F(S)\]

其中 $F(S)$ 表示强制让 $S$ 中每个元素 $i$ 至少选 $n_i + 1$ 个时的方案数

有 \[F(S) = \begin{cases} \binom{n + r - 1 - \sum_{i \in S} (n_i + 1)}{r - \sum_{i \in S} (n_i + 1)}, & \text{如果 } r \ge \sum_{i \in S} (n_i + 1) \\ 0, & \text{否则} \end{cases}\]

即最终方法数为 \[\sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \binom{n + r - 1 - \sum_{i \in S} (n_i + 1)}{r - \sum_{i \in S} (n_i + 1)}\]

证明：点击查看证明

由上面知道，如果没有限制，设无约束的所有方案集合 $U$ ，$|U|=C(n+r-1,r)$

定义坏事件 $A_i$ 为某种元素 $i$ 被选了超过 $n_i$ 次

要求的即为没有任何坏事件发生的事件 $N$，即$N=\bigcap_{i=1}^{n}A^{c}_{i}$

由容斥原理，$|N|=\Sigma_{S\subseteq\{1,2,3,...,n\}}(-1)^{|S|}|\bigcap_{i\in S}A_i|$

这里记 $F(S)=|\bigcap_{i\in S}A_i|$

先选 $\sum_{i \in S} (n_i + 1)$ 个元素 $i$ 再从 $n$ 种元素中无上限选取 $r-\sum_{i \in S} (n_i + 1)$ 个元素即可，就有

$F(S)=\binom{n + r - 1 - \sum_{i \in S} (n_i + 1)}{r - \sum_{i \in S} (n_i + 1)}=C(n + r - 1 - \sum_{i \in S} (n_i + 1),r - \sum_{i \in S} (n_i + 1))$

考虑存在上限的同时每种元素至少出现一次

继续考虑每种元素至少出现一次，方法数为\[\sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \binom{r - 1 - \sum_{i \in S} n_i}{n-1}\]

证明：点击查看证明

前部分使用容斥原理和上一个相同，只是对 $F(S)$ 计算不同，套用的公式变为了 $\binom{r - 1 - \sum_{i \in S} n_i}{n-1}=C(r - 1 - \sum_{i \in S} n_i,n-1)$

拆分数

设正整数 $n \in \mathbb{Z}^+$。定义 $p(n)$ 为 $n$ 的拆分数，即将 $n$ 表示为若干正整数之和的不同方式的个数。我们约定拆分的顺序不计

母函数 \[ P(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}. \]

固定拆分项个数的母函数

若要求拆分 $n$ 恰含 $r$ 个拆分项，设 $p_r(n)$ 为拆分数。母函数为：

\[ P_r(x) = [y^r] \prod_{k=1}^{\infty} \frac{1}{1 - x^k y}, \]

其中 $[y^r]$ 表示取 $y^r$ 系数。该方法可进一步推广到多重限制拆分：拆分项个数属于集合 $R \subset \mathbb{Z}^+$ 时：

\[ P_R(x) = \sum_{r \in R} [y^r] \prod_{k=1}^{\infty} \frac{1}{1 - x^k y}. \]

拆分项奇偶或模约束

奇数拆分：

\[ Q(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^{2k-1}} \]

偶数拆分：

\[ E(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^{2k}} \]

模 $m$ 拆分：拆分项满足 $k \equiv r \pmod m$ 的母函数：

\[ P_{r \bmod m}(x) = \prod_{k \ge 1,\, k \equiv r \, (\mathrm{mod}\, m)} \frac{1}{1-x^k}. \]

Euler 公式及不重复拆分

Euler 证明：

\[ \prod_{k=1}^{\infty} \frac{1}{1-x^{2k-1}} = \prod_{k=1}^{\infty} (1+x^k), \]

说明奇数拆分数等于不重复拆分数

拆分为最多 m 个数的母函数

设正整数 $n$，要求拆分为最多 $m$ 个正整数之和，记拆分数为 $p_{\le m}(n)$。引入变量 $y$ 记录拆分项数：

\[ P_{\le m}(x,y) = \prod_{k=1}^{\infty} \frac{1 - (x^k y)^{m+1}}{1 - x^k y}. \]

取 $y$ 的系数并对 $r=0,1,\dots,m$ 求和，即得到最多 $m$ 项的拆分数：

\[ p_{\le m}(n) = \sum_{r=0}^{m} [y^r] \prod_{k=1}^{\infty} \frac{1}{1 - x^k y}. \]

等价关系

根据母函数对称性可知：

\[ p_{\le m}(n) = \text{拆分 } n \text{ 中最大项不超过 } m \text{ 的拆分数}. \]

即 “拆分为最多 $m$ 个数” 与 “拆分中最大数不超过 $m$” 的拆分数相等：

q-系列与递推公式

引入 $q$-系列展开：

\[ P(x) = \sum_{n=0}^{\infty} p(n) x^n = \sum_{k=-\infty}^{\infty} (-1)^k x^{k(3k-1)/2} \quad (\text{Euler-Pentagonal公式}) \]

递推关系为：

\[ p(n) = \sum_{k \in \mathbb{Z} \setminus \{0\}} (-1)^{k-1} p\Big(n - \frac{k(3k-1)}{2}\Big), \]

其中$p(m) = 0$ 当 $ m<0 $。

带权拆分与加权母函数

若对拆分项赋权 $w(k)$，母函数为：

\[ P_w(x) = \prod_{k=1}^{\infty} \frac{1}{1 - w(k) x^k}. \]

特例：

$w(k) = q^k$ → q-加权拆分
$w(k) = 1$ 限制多重出现 → 不重复拆分

(´-ω-｀)

集合与图论学习笔记04

定理

抽屉原理

简单形式

推广形式

应用例子

容斥原理

两个集合的情况

三个集合的情况

一般形式（n个集合）

补集形式（计数都不在其中的元素）

应用例子

递推与生成函数

母函数（生成函数）定义与分类

母函数基本思想

普通生成函数（OGF）

指数生成函数（EGF）

狄利克雷生成函数（DGF）

母函数运算与组合结构

母函数运算的性质

递推关系的求解

无重根的项

复数根的项

有重根的项

模型

模型 4.2 排列

模型 4.3 组合

模型 4.4 圆排列

模型 4.5 可重排列

最基础的可重

考虑相邻元素不同

考虑每种元素至少出现一次

考虑每种选取的元素存在上限

考虑相邻元素不同且每种元素至少出现一次

模型 4.6 可重组合

最基础的可重

考虑每种元素至少出现一次

考虑每种选取的元素存在上限

考虑存在上限的同时每种元素至少出现一次

拆分数

固定拆分项个数的母函数

拆分项奇偶或模约束

Euler 公式及不重复拆分

拆分为最多 m 个数的母函数

q-系列与递推公式

带权拆分与加权母函数