组合数学

鸽巢原理#

定理#

应用#

【例题】 一位棋手要在 77天 内准备一场比赛，他每天至少下一盘棋，且总共下棋的盘数不超过132盘

1. 证明：当 $k=1,2,\dots,21$ 时，必然存在连续的几天恰好下了 $k$ 盘棋
2. 是否可能存在连续的一些天，棋手恰好下了 22 盘棋？

第一问：

1. 假设第 $i$ 天下 $b_i$ 盘棋，前 $i$ 天一共下 $a_i=\sum_{t=1}^ib_t$ 盘棋，那么可以得到 $1 \le a_1 < a_2 < a_3 < \dots < a_{77} \le 132$
2. 构造两个数列 $a_1, a_2, \dots, a_{77}$ 与 $a_1+k, a_2+k, \dots, a_{77}+k$，各 77 个数一共 154 个数字
3. 这两个数列合起来范围在 $[1, 153]$，由鸽巢原理，一定有两个数字相等。两个数列各自严格递增，所以相等的两个数必然是一个来自第一组，一个来自第二组。即存在某个 $a_j$ 和 $a_i+k$ 使得：$a_j = a_i + k \implies a_j - a_i = k$

第二问：

1. 由于 $k=22$ 时候数列范围为 $[1, 154]$ 和数字的数量相同，所以不能用鸽巢原理
2. 我们的目的是证明从 $1 \le a_1 < a_2 < a_3 < \dots < a_{77} \le 132$ 中任取 77 个数字，至少有两个差为 22
3. 所以可以把这些数字按照 22 的差值拆为 66组 $\{1, 23\}$、$\{2, 24\}$、$\{3, 25\}$ 到 $\{110, 132\}$ 。根据鸽巢原理取 77 个数字肯定有两个落在同一组，那么差值就是 22。

【例题】 从 $1,2,\dots, 200$ 中取 $100$ 个整数，其中之一小于 $16$，那么必有两个数，一个能被另一个整除。

1. 整除问题想到，任意正整数 $x$，都可以唯一地写成以下形式 $x = 2^k \cdot m$。在 $1, 2, \dots, 200$ 这 $200$ 个正整数中，奇数恰好有 $100$ 个，即 $m \in \{1, 3, 5, \dots, 199\}$
2. 现在取 100 个整数，如果存在两个整数落在同一个集合，那么肯定可以整除。所以现在讨论 $100$ 个整数分别落在不同集合的情况。
   1. 当 a 为小于 $16$ 的奇数时（比如 15），显然有数与其构成整数关系（比如抽屉 $15*11=165$）结论成立
   2. 当此数为 $1*2^n$时，显然 $n≤3$ ,考虑抽屉 $3*2^{n_1}$，$9*2^{n_2}$，显然若不存在整除关系
   3. 更一般的，当此数为非2的幂的偶数时，可写成 $b*2^n$ ，b 为奇数。。。。

【例题】 大小两个圆盘圆心重合，都被等分为 200 个扇形区域 。大圆盘可以转动，每次转动的角度都能让大小圆盘的区域完美对齐 。 已知：大圆盘上有 100 个区域被涂成蓝色，100 个被涂成红色；小圆盘上也有 100 个区域被涂成蓝色，100 个被涂成红色 。 证明：存在某个转动状态，使得大小圆盘对应区域颜色相同的数量至少有 100 个 。

1. 用 $a_i, b_j \in \{-1, +1\}$ 分别表示大圆盘第 $i$ 区域和小圆盘第 $j$ 区域的颜色。两个区域颜色相同 ⇔ $a_i \cdot b_j = +1$；颜色不同 ⇔ $a_i \cdot b_j = -1$。
2. 将大圆盘顺时针转 $k$ 格后，定义：$P_k = \sum_{i=1}^{200} a_i \cdot b_{i+k}$。若 $P_k \geq 0$，说明颜色相同的对数 $\geq$ 颜色不同的对数，即颜色相同的至少有100个。
3. 现在我们需要证明存在 $P_k\ge 0$，于是想到 命题 1.2，看看对 $P_k$ 求和是多少。
4. $\sum_{k=1}^{200} P_k = \sum_{k=1}^{200}\sum_{i=1}^{200} a_i b_{i+k} = \left(\sum_{i=1}^{200} a_i\right)\left(\sum_{j=1}^{200} b_j\right)=0$，所以 $P_k$ 求和等于 0，那么至少存在一个 $P_k \ge 0$。

【题目描述】 给定由 $mn+1$ 个实数组成的数列，则其中要么存在长为 $n+1$ 的递增子列，要么存在长为 $m+1$ 的递减子列。

1. 对每个元素 $a_i$，设 $r_i$ = 以$a_i$​ 结尾的最长递增子列的长度，设 $s_i$ = 以 $a_i$ 结尾的最长递减子列的长度
2. 反证法，假设数列中：
   • 不存在长为 $n+1$ 的递增子列 ⇒ 每个 $r_i \leq n$，即 $r_i \in \{1, 2, \ldots, n\}$
   • 不存在长为 $m+1$ 的递减子列 ⇒ 每个 $s_i \leq m$，即 $s_i \in \{1, 2, \ldots, m\}$
3. 所以有序对 $(r_i, s_i)$ 只有 $n \times m$ 种可能。但是一共 $mn+1$ 个实数，也就是有 $mn+1$ 个有序对，那么就一定存在两个实数 $a_i, a_j$ 满足 $(r_i, s_i) = (r_j, s_j)$
4. 假设 $i < j$：
   • 若 $a_i \leq a_j$：将 $a_j$ 接在以 $a_i$ 结尾的递增子列后面，得到长为 $r_i + 1$ 的递增子列，即 $r_j \geq r_i + 1 > r_i$，与 $r_i = r_j$ 矛盾。
   • 若 $a_i \geq a_j$：将 $a_j$ 接在以 $a_i$ 结尾的递减子列后面，得到长为 $s_i + 1$ 的递减子列，即 $s_j \geq s_i + 1 > s_i$，与 $s_i = s_j$ 矛盾。

Ramsey 问题#

先用一个 六人聚会问题 引入：在任意聚会的 6 个人中，要么有 3 个人彼此两两互相认识；要么有 3 个人彼此两两完全不认识。我们将这 6 个人看作完全图 $K_6$ 的 6 个顶点。如果两个人认识，就把他们之间的线染成红色，如果两个人不认识，就把他们之间的线染成蓝色。那么聚会问题就变成了证明：在任意染成红蓝两色的 $K_6$ 中，要么能找到一个纯红色的三角形（$K_3$），要么能找到一个纯蓝色的三角形（$K_3$）。

证明思路如下：

1. 我们在 6 个人里随便抓一个人出来，叫她 Alice。 因为是完全图，Alice 和剩下的 5 个人之间都连着一条线。这 5 条线要么是红色，要么是蓝色。由于只有红蓝两种颜色，跟着鸽巢原理 Alice 和其中 $\lceil\frac{5}{2}\rceil=3$ 个人连线是同一种颜色，我们假设是红色。
2. 接下啦看同色的三个人，它们组成了一个 $K_3$，根据鸽巢原理这三个人一共 3 条连线至少有 $\lceil\frac{3}{2}\rceil=2$ 条是同色的。这三条线里，哪怕有任意一条是红色的，就可以和之前 Alice 的红色连线组成一个红色 $K_3$。假如这三条线全是蓝色，那么这三个人就组成了一个蓝色 $K_3$。

通过上面的聚会问题，数学家精炼出了一个概念叫 Ramsey 数，记作 $R(a,b)$。即为了保证图里要么能找到一个纯红色的 $K_a$，要么能找到一个纯蓝色的 $K_b$，所需要的最少总人数。刚刚我们证明了 $R(3,3) \le 6$，实际上只能是 6 当人数为 5 的时候不成立。

边界条件：

1. $R(a, 1) = 1$，只有一个人的话就没有认识或不认识的关系
2. $R(2, a) = a$，$a$ 个顶点，若没有蓝色 $K_a$​，则所有顶点不全蓝色连接，必有红色 $K_2$

​递推公式：

证明：

1. 设 $s = R(a, b-1)$，设 $t = R(a-1, b)$
2. 从 $s + t$ 个人里，随便抓一个人叫 $v$。 除去 $v$ 自己，他身前连着其他所有人的线一共有：$(s + t) - 1$ 条。
3. 然后根据鸽巢原理，我们假设 $v$ 连接的红线有 $a_1$ 条，连接的蓝线有 $a_2$ 条。然后 $x_1=t , x_2=s$，根据命题 1.6 可以得到 $\sum_{i=1}^n a_i = \sum_{i=1}^n x_i - n + 1=s+t-1$，所以一定存在 $a_i\ge x_i$。要么与 $v$ 相连的红线数量 $\ge t$ 条，要么与 $v$ 相连的蓝线数量 $\ge s$ 条。
4. 我们讨论第一种情况，与 $v$ 相连的红线数量 $\ge t$ 条。由于 $t = R(a-1, b)$，所以与 $v$ 连红线的这群人中要么藏着一个纯蓝色的 $K_b$，要么藏着一个纯红色的 $K_{a-1}$。而且 $v$ 和这群人里的每一个人连的本来就都是红线，就拼成了一个红色 $K_a$。
5. 同理第二种情况要么直接在里面找到红 $K_a$，要么加上 $v$ 的蓝线凑出蓝 $K_b$。

课后题#

25秋#

其他太难了

课件例题#

26春#

计数原理#

定义#

1. 加法原理：若 $A_1, A_2$ 为两个互不相交的集合，且 $|A_1|=a_1, |A_2|=a_2$，则从 $A_1$ 或 $A_2$ 中选取一个元素共有 $a_1 + a_2$ 种选法。
2. 减法原理：设有两个集合 $A \subseteq X$，记 $|A|=a, |X|=n$，则从中选取一个元素并确保其不在 $A$ 中，共有 $n - a$ 种选法。
3. 乘法原理：设 $A_1, A_2$ 为两个集合，记 $|A_1|=a_1, |A_2|=a_2$，则从 $A_1$ 与 $A_2$ 各中选取一个元素，共有 $a_1 a_2$ 种选法。
4. 排列数：对于两个自然数 $k \le n$，从 $[n]$ 中选取 $k$ 个元素排成一列（不同位置对应不同元素）的总排列方法数为 $(n)_k = \frac{n!}{(n-k)!}$，亦可记作 $P(n, k)$ 或 $P_k^n$。
5. 组合数：对于两个自然数 $k \le n$，从集合 $[n]$ 中选取一个 $k$ 元子集的总选取方法数为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$，亦记作 $C(n, k)$ 或 $C_n^k$。

不定方程的解#

【定理】： 对于正整数 $n$，不定方程 $\sum_{i=1}^{k}x_{i}=n$ 的正整数解（$x_i \ge 1$）组的个数为 $\binom{n-1}{k-1}$。

【证明】：

1. 用隔板法，我们需要计算 $x_1+x_2+\dots+x_k=n$ 有多少种可能，可以看做：将 $n$ 个相同的物品排成一列，在形成的 $n-1$ 处间隙中插入 $k-1$ 个相同的隔板，这样就分成了 $k$ 个区域，其中第 $i$ 个区域内的物品数就是 $x_i$。
2. 因此方程解的个数等于从 $n-1$ 个间隙中无序选择 $k-1$ 个的位置数，即 $\binom{n-1}{k-1}$。

【一般情况】：

1. $x_i \ge 1$：就是定理里面的正整数解，个数是 $\binom{n-1}{k-1}$
2. $x_i \ge 0$：求非负整数解个数，可以令 $y_i=x_i+1$ 那么满足 $y_i\ge 1$，等式变为 $\sum_{i=1}^ky_i=n+k$，$x$ 的非负整数解个数等于 $y$ 的正整数解个数 $\binom{n+k-1}{k-1}$
3. $x_i \ge a_i$：求整数解个数，可以令 $y_i=x_i+1-a_i$ 那么满足 $y_i\ge 1$，等式变为 $\sum_{i=1}^ky_i=n+k-\sum_{i=1}^ka_i$，$x$ 的非负整数解个数等于 $y$ 的正整数解个数 $\binom{n+k-\sum_{i=1}^ka_i-1}{k-1}$。

核心思路就是通过换元转成 $x_i$ 为正整数的标准形式。

拓展问题

1. 求不定方程 $\sum_{i=1}^{n}x_{i}=n$ 满足 $a_i \le x_i \le b_i$ 的解的个数。
2. 现有 $n$ 个球，包含 $t$ 种颜色，其中颜色 $c_i$ 的球共有 $k_i$ 个（满足 $\sum_{i=1}^{t}k_i = n$），同色球视为相同。求将这 $n$ 个球排成一列的不同排列方法数。
3. 同上条件，求从中取出 $r$ 个球的不同取法数。
4. 在凸 $n$ 边形中（$n \ge 4$），已知任意三条对角线不共点，求所有对角线总共形成的交点个数。

组合恒等式#

• $2^n = \sum_{i=0}^{n}\binom{n}{i}$

• 证明：二项式展开 $(x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i$，令 $x=1$ 就是 $2^n$ 的展开

• $2^{n-1} = \sum_{i \in [n], i=2k}\binom{n}{i} = \binom{n}{0} + \binom{n}{2} + \dots=\sum_{i \in [n], i=2k+1}\binom{n}{i} = \binom{n}{1} + \binom{n}{3} + \dots$

• 证明：二项式展开 $(x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i$，令 $x=-1$ 得到 $0=\sum_{i=0}^n\binom{n}{i}(-1)^i$，把正项和负项分到等号两侧就能看出来，n 元集合的偶数元子集与奇数元子集各占一半。

• $n2^{n-1} = \sum_{i=0}^{n}i\binom{n}{i}$

• 证明：对多项式函数 $(x+1)^n = \sum_{i=0}^{n}\binom{n}{i}x^i$ 两边求导，得 $n(x+1)^{n-1} = \sum_{i=1}^{n}i\binom{n}{i}x^{i-1}$，代入 $x=1$ 即得证。

格点游走#

二维格点游走#

在二维整点 $\mathbb{Z}^2$ 上从 $(0,0)$ 出发，每步只能向上或向右行走一单位，走到 $(m, n)$ 的走法数为 $\binom{m+n}{m}$。因为总共走了 $m+n$ 步，其中恰有 $m$ 步是向右。

这也恰好证明了 $\binom{m+n-1}{n-1}+\binom{m+n-1}{n}=\binom{m+n}{n}$ 这一点，因为 $(m,n)$ 这个点的步数由 $(m-1,n)$ 和 $(m,n-1)$ 贡献。

一维格点游走#

蚂蚁从 $0$ 出发，每步向左或向右走 $1$ 格，$t$ 步后恰好走到 $k$，共有多少种走法？

1. 设走了 $r$ 步向右，$l$ 步向左，则 $r + l = t, \quad r - l = k$，解得 $r = \dfrac{t+k}{2}$ 和 $l = \dfrac{t-k}{2}$。
2. 假设 $r$ 和 $l$ 都不是整数，那么无解，共 0 种走法。
3. 若 $t < |k|$，走不到，答案为 0。
4. 否则：在 $t$ 步中选 $r = \dfrac{t+k}{2}$​ 步向右，答案为 $\dbinom{t}{\frac{t+k}{2}}$。

穿过特定点#

蚂蚁从 $0$ 出发，$t$ 步后走到 $k$，且中途穿过了 $k+1$，共有多少种走法？

1. 对于每条终点为 $k+2$ 的路径，找到其第一次到达 $k+1$ 的时刻 $t_1$，将 $t_1$ 时刻之后的所有步全部反向，即可形成一条在 $t$ 时刻处于 $k$ 且中途到达过 $k+1$ 的新路径。该变换是一个双射。
2. 所以问题就变成了 “蚂蚁从 $0$ 出发，每步向左或向右走 $1$ 格，$t$ 步后恰好走到 $k+2$，共有多少种走法？”
3. 答案就是 $\binom{t}{\frac{t+k+2}{2}}$

不穿过特定点#

蚂蚁从 $0$ 出发，$t$ 步后走到 $k$，且中途从未到达 $k+1$，共有多少种走法？

1. 把所有到达 $k$ 的走法减去经过 $k+1$ 且到达 $k$ 的走法就好了
2. $\binom{t}{\frac{t+k}{2}} - \binom{t}{\frac{t+k+2}{2}}$

课后题#

25秋#

1. 首先对于凸 $n$ 变形一共有 $\binom{n}{2}-n$ 条对角线，对角线的交点一共有 $\binom{n}{4}$ 个
2. 每两条对角线相交就会得到一个交点，这个交点会把两条对角线分成四段，也就是多出来了两个线段
3. 所以总线段数为：对角线数+交点额外分出来的线段数。$\binom{n}{2}-n + 2\binom{n}{4}$

第一问：

1. 令 $y_1=x_1+1$、$y_2=x_2$ 和 $y_3=x_3-1$，满足 $y_1+y_2+y_3=17$ 且 $y_i$ 为正整数。
2. 套公式有 $\binom{17-1}{3-1}=\binom{16}{2}=120$ 个解

第二问：

1. 令 $x_2=x_1+1+u$ 和 $x_3=x_2+1+v$，满足 $u,v \ge 0$
2. 等式变成 $3x_1+2u+v=14$
3. 因为 $x_1$ 是非负整数，所以有 0-4 五种可能。
4. 当 $x_1=0$，$2u+v=14$，$u$ 可以取 0-7 八种可能
5. 总数就是各种情况加起来

类似之前的。

26春#

容斥原理#

容斥#

求两个集合的交集有：

推广到一般形式得到：

符号是 $(-1)^{t+1}$，也就是 t 重交集，所以奇数交集加，偶数交集减。

交集一般解决的是 A、B、C、D 这几个条件至少满足一种的情况，如果问的是 一个条件都不满足的情况 那么需要用补集：

如果问的是 满足条件 A 但是不满足条件 B 的情况 $A\setminus B$：

【例题】： 求 $[120]=\{1,\dots,120\}$ 中不能被 2 或 3 或 5 整除的整数个数。

1. 定义 $A$、$B$、$C$ 分别为可以被 2、3、5 整除的集合
2. 求 $|A^c\cap B^c\cap C^c|=|S| - |A\cup B \cup C|$
3. $|A\cup B \cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|$
4. $|A|=\tfrac{120}{2}=60,\quad |B|=\tfrac{120}{3}=40,\quad |C|=\tfrac{120}{5}=24$
5. $|A\cap B|=\tfrac{120}{6}=20,\quad |A\cap C|=\tfrac{120}{10}=12,\quad |B\cap C|=\tfrac{120}{15}=8$
6. $|A\cap B\cap C|=\tfrac{120}{30}=4$
7. $|A^c\cap B^c\cap C^c| = 120 - 88 = \boxed{32}$

【例题】： 求 1 到 420 之间能被 3 和 5 整除，但不能被 7 整除的整数个数。

1. 定义 $A$ 为可以被 3 和 5 整除的整数集合，$B$ 为可以被 7 整除的整数集合
2. 问题就变成了求 $|A\cap B^c|=|A|-|A\cap B|$
3. 可以被 3 和 5 整除就是可以被他们的最小公倍数整除，$|A|=\frac{420}{lcm(3,5)}=28$
4. $|A\cap B|=\frac{420}{lcm(15,7)}=4$
5. 所以答案为 $28 - 4 = \boxed{24}$

【例题】： 三个班男女生人数分别为 $(m_1,n_1),(m_2,n_2),(m_3,n_3)$，每班各取一人，求都不取男生的方法数。

1. 设 $A$、$B$、$C$ 分别为"第 1/2/3 班取到男生"的取法集合，那么问题就变成求 $|A^c \cap B^c \cap C^c|$
2. $|A^c \cap B^c \cap C^c|=|S|-|A\cup B \cup C|$
3. $|S|=(m_1+n_1)(m_2+n_2)(m_3+n_3$
4. $|A\cup B \cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|$
5. $|A^c\cap B^c\cap C^c| = (m_1+n_1)(m_2+n_2)(m_3+n_3)\prod_{i=1}^3\!\Big(1-\tfrac{m_i}{m_i+n_i}\Big) = n_1n_2n_3$

错排#

【定义】： 把 $\{1,2,\dots,n\}$ 排成 $P=(a_1,\dots,a_n)$，要求每个位置都"站错"，即 $\forall i,\ a_i\ne i$。这样的排列叫错排，个数记作 $D_n$。

1. 直接数"全错"很难，于是定义 $B_i=\{P:a_i=i\}$，错排就是 $D_n = |B_1^c\cap\cdots\cap B_n^c|$。
2. 根据补集和交集的推广表示可以得到：$D_n = |B_1^c\cap\cdots\cap B_n^c| = |S| - \sum_i|B_i| + \sum_{i<j}|B_i\cap B_j| - \cdots$
3. 现在问题就变成了 $\sum|\cap B_i|$ 该怎么表达。我们观察到 $B_{i_1}\cap\cdots\cap B_{i_t}$ 表示固定 $t$ 个位置站对，其余 $n-t$ 个位置随便排，故大小为 $(n-t)!$。这样的 $t$ 元组有 $\binom{n}{t}$ 个。所以得到 $\sum_{|I|=t}|\cap_{i\in I} B_i|=\binom{n}{t}(n-t)!=\frac{n!}{t!}$
4. 所以表达式为 $C_n^0=D_n=\sum_{t=0}^n(-1)^t \sum_{|I|=t}|\cap_{i\in I} B_i|=\sum_{t=0}^n(-1)^t\frac{n!}{t!}$

【推广】： 把 $n$ 个数排列，恰好 $t$ 个位置站对（$a_i=i$），其余全错。

1. 等同于先从 $n$ 个位置选 $t$ 个"站对"（$\binom{n}{t}$ 种） ，剩下 $n-t$ 个位置做一个规模更小的错排 $D_{n-t}$。
2. $C_n^t = \binom{n}{t}\,C_{n-t}^0 = \frac{n!}{t!}\sum_{i=0}^{n-t}\frac{(-1)^i}{i!}$

Menage 问题#

【定义】： $n$ 对夫妇围圆桌而坐，要求男女相间，且每对夫妇不相邻，求坐法数。

1. 先排男生：等价于长度 $n$ 的圆排列，有 $(n-1)!$ 种。
2. 男生固定好位置之后，需要把女生插在中间位置上。第 $i$ 号女生位（第 $i$、$i+1$ 个男生之间）放的女生编号记 $a_i$，约束是 $a_i\ne i$ 且 $a_i\ne i+1$。
3. 令 $B_i=\{a_i=i \text{ 或 } a_i=i+1\}$，所以固定好男生的情况下符合条件的坐法有 $|\cap_{i=1}^n B^c_i|$ 种。
4. 根据容斥原理可以变成 $\left|\bigcap_{i=1}^n B_i^c\right|=\sum_{k=0}^{n}(-1)^k\sum_{1\le i_1<\cdots<i_k\le n}\left|B_{i_1}\cap\cdots\cap B_{i_k}\right|$
5. 现在需要解决的问题就是 “至少有 $k$ 个男士坐了禁位“的排列数之和 $N_k=\sum_{k=0}^{n}(-1)^k\sum_{1\le i_1<\cdots<i_k\le n}\left|B_{i_1}\cap\cdots\cap B_{i_k}\right|$。
6. 由于每个男士有 2 个禁位，且禁位结构是圆形的，这 $k$ 个男士各选一个禁位，需要这些选择互不冲突（不同男士不能选同一个位置），而且其余 $n−k$ 个男士可以任意坐剩余位置（$(n-k)!$ 种）。所以 $Nk_​=c(n,k)\cdot(n−k)!$
7. 现在我们需要考虑 $c(n,k)$，也就是恰好选 $k$ 个男士，每人各选一个禁位，且这 $k$ 个禁位互不相同（不冲突） 的方案数。我们把这 $n$ 个男士的选择排成一个直线 $0,1,1,2,2,3,3,4,4,5,\dots,n-1,n-1,0$。这 $2n$ 个选项天然地排成一个圆圈，其次我们要注意不能选到同一个位置。所以现在问题就变成了，在长度为 $2n$ 的圆排列里面找到 $k$ 个不相邻的。
8. 然后 从 $2n$ 的圆排列找到 $k$ 个不相邻元素为 $\frac{2n}{2n-k} \binom{2n-k}{k}$
9. 所以可以得到 $\sum_{i_1,\dots,i_t}|B_{i_1}\cap\cdots\cap B_{i_t}| = \dfrac{2n}{2n-t}\binom{2n-t}{t}(n-t)!$
10. 所以 $(n-1)!\sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!$

Möbius#

背景#

容斥原理通常用来求：一个条件都不满足、 至少满足一个条件、满足某些条件但不满足另一些条件。但有时题目会问：恰好满足 k 个条件的对象有多少个？ 这时集合 Möbius 反演非常有用。

设全集为 $S$，其中有 $n$ 个子集 $A_1,A_2,\dots,A_n\subseteq S$，对任意元素 $x\in S$，它可能属于若干个 $A_i$。定义 $C_k=\{\text{恰好属于 }k\text{ 个 }A_i\text{ 的元素个数}\}$。例如：

• $C_0$：一个条件都不满足的元素个数；
• $C_1$：恰好满足一个条件的元素个数；
• $C_n$：同时满足全部条件的元素个数。

直接求 $C_k$ 往往不容易，但各种交集大小通常比较容易计算，定义 $\eta_k$ 是所有 $k$ 重交集大小的总和：

假设某个元素 $x$ 恰好属于 $r$ 个集合，也就是说它被计入 $C_r$。那么在计算 $\eta_k$ 时，因为它属于 $r$ 个集合，从这 $r$ 个集合中任取 $k$ 个，就会形成一个包含它的 $k$ 重交集。因此它会被计算 $\binom rk$ 次，所以：

然后对于这个式子我们就可以通过 Möbius 反演 得到 $C_r$ 关于 $\eta_k$ 的表达式了。

集合 Möbius 反演#

集合 Möbius 反演公式为：

证明如下：

【例题】： 求 $[30]=\{1,2,\dots,30\}$ 中恰好被 $2,3,5$ 中一个数整除的整数个数。

令

要求的是 $C_1$，先算交集和：

由公式得到：

Möbius 函数#

莫比乌斯函数满足以下性质：

证明如下：

1. 当 $m=1$ 时，$\sum_{d\mid m}\mu(d)=\mu(1)=1$ 成立
2. 当 $m>1$ 时，$m$ 可以表示为 $m = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}$，这里 $p$ 是质数。式子可以改写为

这个式子可以看做 $(1+(-1))^k$ 的二项式展开，结果就是 $0$。

为什么式子展开之后不会出现 $0$ 的项，不是有可能 $\mu(d)=0$ 吗？ 因为 $\sum\mu(\frac{m}{p_i})$ 就相对于在 $k$ 个不同质因子中选 $k-1$ 个组成 $p_1p_2\dots p_{k-1}$，保证了都是一次项。

数论 Möbius 反演#

已知 $F(n)=\sum_{d\mid n}f(d)$，那么有：

证明如下：

1. 由于 $F(n)=\sum_{d\mid n}f(d)$ 可知 $F(\frac{n}{d})=\sum_{e\mid \frac{n}{d}}f(e)$。
2. 代入之后有 $\sum_{d\mid n}\mu(d)F\left(\frac nd\right)=\sum_{d\mid n}\mu(d)\sum_{e\mid \frac{n}{d}}f(e)$
3. 这里求和的对象是满足 $d\mid n,\qquad e\mid \frac nd$ 的二元组 $(d,e)$，所以等价于 $de\mid n$
4. 原式可以改写为 $\sum_{de\mid n}\mu(d)f(e)$ 然后按 $e$ 分类，得到 $\sum_{de\mid n}\mu(d)f(e)=\sum_{e\mid n}f(e)\sum_{d\mid n/e}\mu(d)$
5. 现在就是先对莫比乌斯函数求和，当 $n=e$ 时， $\sum_{d\mid n/e}\mu(d)=1$。所以式子等于 $f(n)$。

课后题#

1. 令 $A_i$ 为所有字符串位置 $i$ 恒为 $0$ 或 $1$ 的子集。
2. 所以我们要求的好子集个数就是 $|A_1^c\cap A_2^c\cap\dots A_n^c|$
3. 按照容斥我们可以得到 $\sum_{k=0}^{n}(-1)^k\sum\left|\bigcap_{i\in I}A_i\right|$
4. $\bigcap_{i\in I}A_i$ 就是位置 $I$ 上恒定的字符串的子集。若 $|I|=k$个位置都被固定，则对于每个被固定的位置有两种选择，共有 $2^k$ 种方式。固定之后剩下位置可以组成 $2^{n-k}$ 种字符串，就有 $2^{2^{n-k}}-1$ 个子集，这里要减去全都不选的空子集。所以 $|\bigcap_{i\in I}A_i|=2^k\cdot(2^{2^{n-k}}-1)$。
5. 然后前面求和符号还需要在 $n$ 个位置里面取 $k$ 个就是 $\binom{n}{k}$
6. 所以结果为 $\sum_{k=0}^{n}(-1)^k\binom{n}{k}(2^k\cdot2^{2^{n-k}}-1)$

和上一题同理，答案是 $\sum_{k=0}^{n}(-1)^k\binom{n}{k}(3^k\cdot2^{3^{n-k}}-1)$

设 $A_i$ 是第 $i$ 对夫妻相邻的情况，所以要求 $|\cap A_i^c|$。答案是 $\sum_{k=0}^{n}(-1)^k\binom{n}{k}2^k(2n-k)!$，过程见前面。

第一问：

1. 根据之前的公式可以得到 $\sum_{d|n}|\mu(d)|=\sum_{t=0}^k|\binom{k}{t}(-1)^t|$
2. 那么进一步推导可以得到 $\sum_{d|n}|\mu(d)|=\sum_{t=0}^k\binom{k}{t}1^t$
3. 这就是 $(1+1)^k$ 的二项式展开的形式，所以答案是 $2^k$。

第二问：

1. 连续 4 个整数 $n,n+1,n+2,n+3$ 模 $4$ 恰好覆盖余数 $0,1,2,3$，故其中必有一个是 $4$ 的倍数。设它为 $a$，则 $4=2^2\mid a$，$a$ 含平方因子，$\mu(a)=0$。乘积中有 $0$ 因子，故 $\mu(n)\mu(n+1)\mu(n+2)\mu(n+3)=0$

1. 任取一个长度为 $n$ 的字符串，它的最小周期为 $d$，那么一定满足 $d|n$。
2. 长度为 $n$ 的 $m$ 元字符串总数为 $m^n$，可以得到 $m^n=\sum_{d|n}f(d)$，这里 $f(d)$ 指的是最小循环周期为 $d$ 的字符串数
3. 我们令 $F(n)=m^n$ 就变成 $F(n)=\sum_{d|n}f(d)$ 的标准形式了，通过莫比乌斯反演可以得到 $f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d\mid n}\mu(d)\,m^{\frac{n}{d}}$

Burnside 引理/Polya 计数#

群论#

给定集合 $S$ 和一个二元运算 $\times$，若满足以下四条，则 $S$ 关于该运算构成一个群：

1. 封闭性：$\forall a,b\in S,\ a\times b\in S$；
2. 结合律：$\forall a,b,c\in S,\ (a\times b)\times c=a\times(b\times c)$；
3. 单位元：存在 $e\in S$，使得 $\forall a\in S,\ a\times e=e\times a=a$；
4. 逆元：对每个 $a\in S$，存在 $a^{-1}\in S$，使得 $a\times a^{-1}=a^{-1}\times a=e$。

群的性质：

1. $e^{-1}=e$：由于任何数乘单位元等于自己，所以 $e\cdot e= e$，所以 $e$ 的逆元就是自己。
2. 单位元唯一：假设存在单位元 $e_1 \ne e_2$ 那么 $e_1=e_1\cdot e_2=e_2$，矛盾
3. 逆元唯一：假设元素 $a$ 有两个逆元 $a_1\ne a_2$。$a_1=a_1\cdot e=a_1\cdot(a\cdot a_2)=(a_1\cdot a) \cdot a_2=e\cdot a_2=a_2$，矛盾。

【定义】： 如果 $H\subseteq G$ 那么 $<H, \cdot>$ 是 $<G, \cdot>$ 的子集。【性质】： 若 $H$ 是 $G$ 的子群且 $G$ 是有限群，那么满足 $|H| \, | \, |G|$

置换群#

置换的本质就是把一堆元素进行 “重新排列”或者“位置变换”的动作，使得 $[n]=\{1,2,3,4,\dots,n\}$ 变成 $[n]=\{\delta(1),\delta(2),\delta(3),\dots,\delta(n)\}$。例如，正方形有 4 个顶点，我们分别标号为 $1,2,3,4$（顺时针排列）。如果我们把这个正方形顺时针旋转 90°，顶点的位置就会发生变化，标号变成 $2,3,4,1$，这个“旋转 90°”的动作就是一个置换。如果把所有可能保持正方形形状不变的旋转动作收集起来：

• $g_0$：旋转 0°（什么都不做，即单位元）
• $g_1$：顺时针旋转 90°
• $g_2$：顺时针旋转 180°
• $g_3$：顺时针旋转 270°

这四个动作构成了一个集合 $G = \{g_0, g_1, g_2, g_3\}$，它组成的置换群就是 $<G,\circ>$。因为它们满足封闭性（任意两个旋转连续做，还是这四个之一）、结合律、有单位元和逆元（旋转 90° 的逆元就是旋转 270° 拨回来），所以这个集合构成了一个群。

$\circ$ 是置换操作。

轨道定理#

这里需要引申出两个概念：轨道 $O_a$ 和稳定子 $G_a$。举个例子还是刚刚的正方形涂色，假如我们已经有了红蓝交替的涂色方案 $a = (R, B, R, B)$，现在不同置换操作的影响如下：

• $g_0$（不转）：显然还是 $(R, B, R, B)$。
• $g_1$（转90°）：1号位的红跑到了2号位，原方案变成 $(B, R, B, R)$，变样了。
• $g_2$（转180°）：正方形对角颠倒，1和3对调（都是红），2和4对调（都是蓝），结果还是 $(R, B, R, B)$
• $g_3$（转270°）：原方案变成 $(B, R, B, R)$，变样了。

稳定子 $G_a$ 也就是能使它保持原样的动作为 $G_a = \{g_0, g_2\}$。轨道 $O_a$ 代表它通过各种动作能变成几种样子，不管怎么转，它要么保持 $(R, B, R, B)$，要么变成 $(B, R, B, R)$ 。 所以，方案 $a$ 的轨道集合 $O_a = \{(R, B, R, B), (B, R, B, R)\}$。

第二个例子只有1个顶点是蓝色的方案 $b = (R, R, R, B)$。因为只有 4 号位是孤零零的蓝色，只要你一旋转，蓝色肯定会跑到别的位置去，所以方案 $b$ 的稳定子 $G_b = \{g_0\}$，它的轨道为 $O_b = \{(R, R, R, B), (B, R, R, R), (R, B, R, R), (R, R, B, R)\}$。

【定理】： $|G| = |O_a| \cdot |G_a|$。注意这里的 $|G|$ 是动作总数。

【例题】： 正方体有多少种保持位置不变的旋转？

1. 可以把正方体看成黑顶白身
2. 先找稳定子，需要让正方体保持不动并且黑色在顶上，只能插一根轴穿过顶面和底面，像转陀螺一样转动它。能让正方体和自身重合的旋转只有：0°、90°、180°、270° 这 4 种动作，所以稳定子大小 $|G_x| = 4$。
3. 然后正方体不管怎么转，黑色面可以跑到前面、后面、左面、右面、顶面、底面。也就是说，这个正方体在空间中一共有 6 种 位置，轨道大小 $|O_x| = 6$。
4. $|G| = |O_x| \cdot |G_x| = 6 \times 4 = 24$

Burnside#

Burnside 引理和 Pólya 计数定理是解决在某种对称性下，有多少种本质不同的方案。想像一个简单的场景：我们要用红、蓝两种颜色的珠子，穿成一串含有 4 颗珠子的圆形项链。如果不考虑旋转对称性，单纯把它们排成一排，根据乘法原理，总共有 $2^4 = 16$ 种不同的涂色方案 。 但是，因为项链是一个圆环，我们在现实中可以旋转它 。例如：涂色方案“红蓝蓝蓝”（RBBB）顺时针旋转 $90^\circ$ 后变成了“蓝红蓝蓝”（BRBB） 。虽然 4 颗珠子可以通过手动枚举去重，但如果是 12 颗珠子、3 种颜色，甚至是对正方体的 6 个面进行旋转涂色呢 ？手动枚举几乎是不可能的。这就需要引入群论的工具。

设 $G$ 是作用在方案集合 $X$ 上的置换群 ，则本质不同的方案数（轨道数）等于所有置换操作下“不动点”数量的平均值 ：

其中：

• $|G|$ 是群的大小（即对称操作的总数） 。
• $C(\delta)$ 是在置换操作 $\delta$ 作用下，保持一模一样、没有发生改变的方案数量。

【例题】： 4 颗珠子、2 种颜色的项链，有多少种排列方案。

1. 置换操作一共有四种（0°，90°，180°，270°），所以 $|G|=4$
2. 对于操作 $\delta_1$ 也就是旋转 0°，$2^4=16$ 的每种方案都不变，所以 $C(\delta_1)=16$
3. 对于操作 $\delta_2$ 也就是旋转 90°，$(R,R,R,R),(B,B,B,B)$ 不变，所以 $C(\delta_2)=2$
4. 对于操作 $\delta_3$ 也就是旋转 180°，$(R,B,R,B),(B,R,B,R),(R,R,R,R),(B,B,B,B)$不变，所以 $C(\delta_3)=4$
5. 对于操作 $\delta_4$ 也就是旋转 270°，$C(\delta_4)=C(\delta_2)=2$
6. $\text{轨道数} = \frac{1}{4} \times (16 + 2 + 4 + 2) = \frac{24}{4} = 6 \text{ 种}$

Polya#

直接举个例子，还是刚刚的 4 颗珠子、2 种颜色的项链，有多少种排列方案。

1. 对于操作 $\delta_1$ 也就是旋转 0°，每个珠子位置都不动，所以轮换为 $(1)(2)(3)(4)$，$k(\delta)=4$
2. 对于操作 $\delta_2$ 也就是旋转 90°，珠子位置变化为 $1 \to 2 \to 3 \to 4 \to 1$，所以轮换为 $(1, 2, 3, 4)$，$k(\delta)=1$
3. 对于操作 $\delta_3$ 也就是旋转 180°，珠子位置变化为 $1 \leftrightarrow 3$ 互换，$2 \leftrightarrow 4$ 互换，轮换为 $(1, 3)(2, 4)$，$k(\delta)=2$
4. 对于操作 $\delta_4$ 也就是旋转 270°，珠子位置变化为 $1 \to 4 \to 3 \to 2 \to 1$，所以轮换为 $(1, 4, 3, 2)$，$k(\delta)=1$
5. $\text{轨道数} = \frac{1}{4} \times (2^4+2^1+2^2+2^1) = \frac{24}{4} = 6 \text{ 种}$

课后题#

1. 考虑 Polya 定理 $\text{本质不同的方案数} = \frac{1}{|G|} \sum_{\delta \in G} m^{k(\delta)}$
2. 一共 $2n$ 种动作，旋转 $n$ 种，翻转 $n$ 种
3. 对于旋转动作可以发现一个规律，把 $n$ 颗宝石移动 $k$ 格的轮转数为 $gcd(n,k)$。（记下来就好）
4. 对于翻转动作要分为奇数偶数考虑：
   1. 如果 $n$ 为奇数，那么 $n$ 种翻转都会出现 $\frac{n+1}{2}$ 个轮转
   2. 如果 $n$ 为偶数，那么有沿点切翻转和沿线翻转两种，每种都是 $\frac{n}{2}$ 个动作。沿着点翻转的轮转数是 $\frac{n}{2}+1$，沿着线翻转是 $\frac{n}{2}$，所以一共出现。
5. 所以偶数情况是 $\frac{1}{2n}(\sum^{n-1}_{t=0}2^{gcd(n,t)} + \frac{n}{2}*(2^{\frac{n}{2}+1} + 2^{\frac{n}{2}}))$，奇数是 $\frac{1}{2n}(\sum^{n-1}_{t=0}2^{gcd(n,t)}+n*2^{\frac{n+1}{2}})$

放弃

放弃

生成函数#

定义#

对于一个数列 $\{a_0, a_1, a_2, \dots\}$，定义它的普通生成函数为：

直观记忆法：这里的 $x$ 只是一个“占位符”，它的指数 $n$ 代表“问题的规模”（比如取了 $n$ 个球），而前面的系数 $a_n$ 则代表该规模下的“组合方法数”。

多重组合问题#

基本原理：如果有 $m$ 种不同类型的小球，每种小球可选的数量范围为集合 $S_i$。从这些小球中总共取 $k$ 个的方法数为 $a_k$，那么数列 $\{a_k\}$ 的生成函数就是每种小球独立选择多项式的乘积：

因为多项式相乘时，指数相加（$x^{k_1} \cdot x^{k_2} = x^{k_1+k_2}$）正好对应了“总球数相加”；而系数相乘再相加，正好契合了计数中的“加法原理与乘法原理”。

例：有 3 种水果：苹果、香蕉、橘子。现要选出 $n$ 个水果，我想知道买 $n$ 个水果有多少种买法，要求：

1. 苹果的数量必须是偶数；
2. 香蕉的数量没有限制；
3. 橘子最多只能选2个。

根据上面的规则我们可以写出三种水果的多项式。苹果的多项式为 $1+x^2+x^4+\cdots$，$x$ 的指数代表我们拿了多少个，$x$ 前面的系数代表达成这个数量，有多少种方法数。如果我们选择 $k$ 个苹果不管怎么选都只有一种做法，所以系数都为 1。同理我们能写出香蕉的多项式为 $1+x+x^2+x^3+\cdots$，橘子的多项式为 $1+x+x^2$。

根据几何级数求和公式我们可以得到：

1. $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots = \sum_{n=0}^{\infty} x^n$
2. $\frac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \dots = \sum_{n=0}^{\infty} x^{2n}$

然后我们把每种水果的多项式相乘，就能得到水果买法的生成函数：

我们把生成函数展开成 $a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$ 的形式，$x^n$ 前面的系数 $a_n$ 就是买 $n$ 个水果有多少种买法。

【例题】： 考虑方程 $x_1+x_2+\dots+x_k=n$，其中 $n\ge0$。

1. 设 $a_n$ 为上述方程正整数解的个数，求 $a_n$ 对应的生成函数。
2. 设 $a_n$ 为上述方程非负偶数解的个数，求 $a_n$ 对应的生成函数。
3. 设 $a_n$ 为上述方程满足 $x_1+x_2\le10$ 且 $x_3, \dots,x_k\le5$ 的非负整数解的个数，求 $a_n$ 对应的生成函数。

和上一题一个思路，我们先计算每一个变量 $x_i$ 的多项式。由于要求正整数，所以 $x_i$ 的取值范围在 1 到 正无穷，也就是它的指数可以取 $1,2,3,4,\dots$，因此 $x_i$ 的多项式即为 $x+x^2+x^3+\dots$。 第一问没有约束，所以生成函数就是 $k$ 个多项式的乘积：

第二问要求非负偶数解，因此多项式为 $1+x^2+x^4+\dots$，生成函数为：

第三问把 $x_1$ 和 $x_2$ 捆绑在一起了，可以把他们当一个整体考虑，也就是 $x_1+x_2$ 一共可以取 $[0,1,2,3,\dots,10]$ 这几个数字，那么他们的方法数就不再固定为 $1$ 了。假如如果它们的和为 $2$，一共可以取 $(2,0), (1,1), (0,2)$ 这 3 种组合，也就是 $3 \cdot x^2 = 3x^2$，因此 $x_1+x_2$ 的多项式为：

而 $x_3$ 到 $x_k$ 限制了非负整数解且 $\le5$，多项式为：$1+x+x^2+\dots + x^5$，所以生成函数为：

对于 $1+x+x^2+\dots + x^5$ 这样的有限等比数列，可以用等比数列求和公式进行化简：

$$ 1+x+x^2+\dots+x^k = \frac{1-x^{k+1}}{1-x} $$

非负整数的拆分#

【例题】： 你手里有面值为 1, 2, 3, 4, 5, … 一直到无穷大 的硬币，每种硬币都有无限多个。现在你要凑出总面值为 $n$ 的钱，一共有多少种凑法？

这个问题可以把它转换为求方程 $x_1+2x_2+3x_3+\dots$ 有多少种非负整数解。我们回想上一章节的做法，给每个面值的硬币写一个多项式，然后乘积就是凑法的生成函数，我们看 $x^n$ 前面的系数 $a_n$ 就知道凑出总面值为 $n$ 的钱有多少种凑法。一个 1 元硬币可以凑出 0 个 1 元、1 个 1 元、2 个 1 元、3 个 1 元，所以表达式为 $(1 + x^1 + x^2 + x^3 + x^4 + \dots) = \frac{1}{1-x}$。同理 2 元硬币的表达式为 $(1 + x^2 + x^4 + x^6 + x^8 + \dots) = \frac{1}{1-x^2}$。然后把所有面值硬币的括号全部乘起来，就得到了无限制整数拆分的生成函数 $P(x)$：

按照之前的思路，指数代表的不是 物品的个数 吗？所以 2 元硬币的多项式不应该也是 $(1 + x^1 + x^2 + x^3 + x^4 + \dots) = \frac{1}{1-x}$ 吗？实际上指数代表的是 对最终总和 $n$ 的贡献值。比如正整数解那题 $n$ 代表正整数解的数量，所以我们每选择一个正整数贡献就会加一。这题 $n$ 代表的是总面值，所以我们每选择一个 2 元硬币对 $n$ 的贡献是 2。

1. 假如要求 拆分出来的数互不相同，那么就是每种面值的硬币最多只能拿 1 枚：$Q(x) = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots = \prod_{i=1}^{\infty} (1+x^i)$
2. 假如要求 只能拆分成奇数，那么只有面值为奇数（1元、3元、5元…）的硬币：$O(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^7} \cdots = \prod_{i=1}^{\infty} \frac{1}{1-x^{2i-1}}$

现在来看下非负整数拆分的问题：将非负整数 $n$ 分成 $k$ 个非负整数的和，即 $x_1 + x_2 + \dots + x_k = n$，有多少种分法，即满足 $x1 \le x2 \le \dots \le x_k$ 非负整数解的个数有多少种?

加上 $x1 \le x2 \le \dots \le x_k$ 这个限制之后题目就变成了求无序的解，数字 4 只能被拆为 $0,0,4$ 不能拆成 $4, 0,0$。其次变量之间被 $x_1 \le x_2 \le \dots \le x_k$ 锁死它们就不独立了，我们没办法直接为每个 $x_i$ 写括号。我们可以利用作差法，令：

• $y_1 = x_1 \ge 0$
• $y_2 = x_2 - x_1 \ge 0$
• $y_3 = x_3 - x_2 \ge 0$
• $\dots$
• $y_k = x_k - x_{k-1} \ge 0$

现在把 $x$ 反过来用 $y$ 表示：

• $x_1 = y_1$
• $x_2 = y_1 + y_2$
• $x_3 = y_1 + y_2 + y_3$
• $\dots$
• $x_k = y_1 + y_2 + \dots + y_k$

把这些代入原方程 $x_1 + x_2 + \dots + x_k = n$ 里面去，把相同的 $y$ 合并同类项：

这就回到了之前的凑硬币问题，$y_k$ 就是面值为 $1$ 的硬币，它对总面值的贡献是 $1$。按照刚才学会的方法，直接为每种面值的硬币写括号并乘起来，得到对应的生成函数：

由于 $x$ 和 $y$ 是一一映射的关系，所以他们两个的生成函数是同一个。$G(x)$ 里面的 $x$ 只是一个记号，而不是原来的未知数。

除了代数公式，整数拆分还有一个强力的形象化武器叫 Ferrers 图。Ferrers 图的本质价值是：把两类看起来完全不同的拆分之间的对应关系，变成一个简单的几何操作，让"它们数量相等"这件事变得一目了然。

比如，把 $7$ 拆分成 $4 + 2 + 1$，我们可以用圆点画成格子：

● ● ● ●   (4)
● ●       (2)
●         (1)

如果我们把这个图形沿着对角线翻转（转置矩阵），它会变成一个新图形：

● ● ●
● ●
●
●

读出每行的数量，它变成了：$3 + 2 + 1 + 1 = 7$。这就叫做它的共轭拆分（Conjugate Partition）。

【例题】： 已知 $a_{k,m}^n$ 表示方程 $x_1 + x_2 + \dots + x_k = n \quad (n \ge 0)$ 在满足以下条件时的非负整数解的个数 $1≤x_1​≤x_2​≤ \dots ≤x_k​≤m$，需要解决以下三个问题：

1. 证明对称性：$a_{k,m}^n = a_{m,k}^n$。
2. 证明递推关系：当 $n \ge m > 1$ 且 $n \ge k > 1$ 时，有 $a_{k,m}^n = a_{k,m-1}^n + a_{k-1,m}^{n-m}$。
3. 求生成函数：令 $b_m^n = \sum_{k=1}^n a_{k,m}^n$（将 $m$ 视为常数），求序列 $\{b_m^n\}_{n \ge 1}$ 的普通生成函数 $B_m(x) = \sum_{n \ge 1} b_m^n x^n$。

指数型生成函数#

前面的普通生成函数解决了 组合问题，这里指数型生成函数解决的是 排列问题。对于数列 $\{a_k\}$，其指数型生成函数（EGF）定义为：

这里的系数 $a_k$ 与指数 $k$ 与之前的含义相同，$a_k$ 指方案数，$k$ 指的是贡献。

例：用红、蓝、绿三种颜色的球拼成一个长度为 $k$ 的序列。要求：红色球必须取偶数个，蓝色和绿色球的数量没有限制。问有多少种不同的排列方法 $a_k$？

写出每种颜色对应的指数型选择多项式：

1. 红（偶数个）：$1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots = \frac{e^x + e^{-x}}{2}$
2. 蓝（无限制）：$1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x$
3. 绿（无限制）：$1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x$

将它们相乘，得到总的指数型生成函数 $f(x)$：

例：有 $m$ 种颜色的球，每种颜色可以重复使用。当限定每种颜色取 $k_1, k_2, \dots , k_m$ 个时 $k_1 + k_2 + \dots + k_m = k$, 问有多少种排列方法？

这题与之前的题有所不同，之前我们不管是选球 or 非负整数选一个值都是有一个范围，但是这题限定了第 $i$ 个球取 $k_i$ 个，所以：

我们得到的生成函数就是：

然后 $\frac{x^k}{k!}$ 的系数就是排列方法数量，作一下变形：

$\frac{k!}{k_1!k_2!\dots k_m!}$ 就是所求的排列数了。

课后题#

25秋#

$a^k_n$ 和 $b^k_{n+k}$ 的生成函数都能得到，但是我们没办法展开得到系数，所以不能知道$a^k_n$ 和 $b^k_{n+k}$ 的显式解。

求数列生成函数的通法就是：把 $G(x) = \sum{a_nx^n}$ 凑成 $\sum x^n=\frac{1}{1-x}$ 的标准形式，然后就可以对 $\frac{1}{1-x}$ 积分求导还原。

课件习题#

26春#

例题讲过。

一二问是例题，第三问放弃。

递推关系#

定义#

递推关系就是根据前几项定义当前项的规律，找到通项公式。

例如 Hanoi 塔这个经典例子，我们假设将 $n$ 个圆盘从 A 移到 C，设最少需要 $T_n$ 步。

• 那么将上面 $n-1$ 个圆盘从 A 移到 B 需要 $T_{n-1}$ 步
• 将最大盘从 A 移到 C 需要 $1$ 步
• 将 B 上 $n-1$ 个圆盘移到 C 需要 $T_{n-1}$ 步

就能得到递推关系 $T_n = 2T_{n-1} + 1$，根据这个递推关系我们就能找到通项公式：$T_n=2^n-1$。接下来研究的就是：如何根据递推关系得到通项公式。

常系数线性齐次#

• 一般形式：$a_n + c_1a_{n-1} + c_2a_{n-2} + \dots + c_ka_{n-k} = 0$
• 解法：令 $a_n = x^n$ 代入，即可导出它的特征方程：$x^k + c_1x^{k-1} + c_2x^{k-2} + \dots + c_k = 0$
• 通解：
  • 特征方程有 $k$ 个互不相同的根 $q_1, q_2, \dots, q_k$，那么通解可以直接写为 $a_n = \lambda_1 q_1^n + \lambda_2 q_2^n + \dots + \lambda_k q_k^n$
  • 若某个根 $q_1$ 是 $m$ 重根，它贡献的项为 $(\lambda_0 + \lambda_1 n + \lambda_2 n^2 + \dots + \lambda_{m-1} n^{m-1}) q_1^n$

例：求解 $a_n = a_{n-1} + a_{n-2}$，初始条件 $a_0 = 0, a_1 = 1$。

1. 写出特征方程 $x^2-x-1=0$
2. 计算特征根 $q_1 = \frac{1 + \sqrt{5}}{2}, \quad q_2 = \frac{1 - \sqrt{5}}{2}$
3. 通解写为 $a_n = \lambda_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + \lambda_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n$
4. 代入初始条件解得 $\lambda_1 = \frac{1}{\sqrt{5}}, \lambda_2 = -\frac{1}{\sqrt{5}}$
5. 通项公式为 $a_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right]$

常系数线性非齐次#

• 一般形式：$a_n + c_1a_{n-1} + \dots + c_ka_{n-k} = f(n)$
• 解法：
  • 非齐次项是常数 $f(n)=m$，左移一位就可以把常数项消掉。原式：$a_n - 3a_{n-1} = 5$ 左移一步：$a_{n+1} - 3a_n = 5$，两式相减就能得到常系数线性齐次 $a_{n+1​}−4a_n​+3a_{n−1}​=0$。
  • 非齐次项是 $P_k(n) \cdot \lambda^n$ 的形式，那么它会为最终的特征方程贡献一个额外的辅助根 $x = \lambda$，其重数为 $k + 1$。比如 $a_{n+1}-2a_n=n^2$，它可以看做 $a_{n+1}-2a_n=n^2\times 1^n$，所以辅助根为 $\lambda=1$，通解就是 $a_n=\lambda_1 2^n + (\lambda_2+\lambda_3 n)1^n$。这里需要注意，假如齐次项的根和非齐次项的根相同，那么通解的形式为 $a_n=n^m(\lambda_2+\lambda_3 n)1^n$，这里 $m$ 指的是齐次项里为 $m$ 重根。

递推关系和生成函数#

如何用生成函数求递推关系的通项公式

例：用生成函数法再次求解方程：$a_n - 2a_{n-1} = 3^n$ ($n \ge 1$)，已知 $a_0 = 1$。

1. 两侧同乘 $x^n$ 得到 $a_nx^n - 2a_{n-1}x^n=3^nx^n$
2. 两侧同时求和 $\sum_{n=1}^{\infty} a_n x^n - 2 \sum_{n=1}^{\infty} a_{n-1} x^n = \sum_{n=1}^{\infty} (3x)^n$
3. 改写成 $\sum_0^{\infty}a_nx^n=A(x)$ 的形式 $(A(x) - a_0) - 2x A(x) = \frac{3x}{1-3x}$
4. 然后代入 $a_0=1$ 就能得到 $A(x) = \frac{1}{(1-2x)(1-3x)} = \frac{3}{1-3x} - \frac{2}{1-2x}$
5. 应用几何级数展开公式得到 $A(x) = 3 \sum_{n=0}^{\infty} (3x)^n - 2 \sum_{n=0}^{\infty} (2x)^n = \sum_{n=0}^{\infty} \left( 3^{n+1} - 2^{n+1} \right) x^n$
6. 所以得到 $a_n = 3^{n+1} - 2^{n+1}$

课后题#

Q1

Q2

Q3

Q1

这个方法和前两题的方法都可以。