36.组合数学入门

组合数学入门

鸽巢原理

基本鸽巢原理

定理：将 \(n+1\) 个物体放入 \(n\) 个盒子中，至少有一个盒子包含不少于两个物体。

证明（反证法）：

假设每个盒子最多只有一个物体，那么 \(n\) 个盒子最多只能装 \(n\) 个物体，与有 \(n+1\) 个物体矛盾。因此至少有一个盒子有两个或更多物体。

经典应用：

1. 13个人中至少有两个人生日在同一个月
2. 从\(n\)对夫妇中选\(n+1\)人时，必选到一对夫妻

连续和整除问题

问题：给定\(m\)个整数\(a_1,a_2,...,a_m\)，必存在连续若干数之和能被\(m\)整除。

证明思路：

1. 考虑前\(k\)项和\(S_k = a_1+...+a_k\)（\(m\)个数共\(m\)种前缀和）
2. 如果某个\(S_k\)能被\(m\)整除，得证
3. 否则，这些和除以\(m\)的余数只能是\(1,...,m-1\)（\(m-1\) 种余数）
4. 由鸽巢原理，必有两个和余数相同，比如\(S_i\)和\(S_j\)
5. 则\(S_j-S_i = a_{i+1}+...+a_j\)能被\(m\)整除

例子：数列2,4,6,3,5,5,6中，6+3+5=14能被7整除。

国际象棋大师问题

问题：11周（77天）内每天至少下一盘棋，每周不超过12盘。证明存在连续若干天共下21盘。

证明要点：

1. 设\(a_i\)为前\(i\)天的总盘数，形成严格递增序列
2. 总盘数\(a_{77} \leq 12×11 = 132\)
3. 考虑序列\(a_1,...,a_{77}\)和\(a_1+21,a_{2}+21,...,a_{77}+21 \leq 132+21=153\)（共154个数）
4. 这些数都在1到153之间，但有154个数，必有相等
5. 只能是某个\(a_i = a_j +21\)，即第\(j+1\)到\(i\)天共下\(a_{i}-a_{j}=21\)盘

加强版鸽巢原理

定理：将\(q_1+q_2+...+q_n -n+1\)个物体放入\(n\)个盒子，无论什么顺序放好后，盒子编号为\(1\sim n\)，则至少有一个特定的数字\(i\)，编号为 \(i\) 的盒子包含不少于\(q_i\)个物体。

证明：

1. 假设每个盒子\(i\)都含有少于\(q_i\)个物体，即最多有\(q_{i}-1\)个

2. 则所有盒子中的物体总数不超过：

   \[(q_1-1)+(q_2-1)+...+(q_n-1)=q_1+q_2+...+q_n-n\]

3. 但实际放入的物体数为\(q_1+q_2+...+q_n-n+1\)个

4. 这与假设矛盾，因此至少存在一个盒子\(i\)含有不少于\(q_i\)个物体

注：当放入\(q_1+q_2+...+q_n-n\)个物体时，可以使得每个盒子\(i\)都恰好含有\(q_i-1\)个物体，剩下一个就面对的基本窠巢原理。

推论（平均原理）：

1. 若\(n\)个非负整数\(m_1,m_2,...,m_n\)的平均数大于\(r-1\)，即
   \[\frac{m_1+m_2+...+m_n}{n} > r-1\]
   则至少有一个整数大于或等于\(r\)

2. 若\(n\)个非负整数\(m_1,m_2,...,m_n\)的平均数小于\(r+1\)，即
   \[\frac{m_1+m_2+...+m_n}{n} < r+1\]
   则至少有一个整数小于\(r+1\)

碟子着色问题

问题：两个分成200扇形的碟子，大碟子红蓝各100个，小碟子任意着色。证明存在对齐方式使至少100个扇形颜色匹配。

证明要点：

1. 固定大碟子，小碟子有\(200\)种可能位置
2. 每个扇形在\(100\)个位置上会与大碟子同色
3. 总匹配次数=\(200\times 100=20000\)
4. 平均每个位置有\(100\)次匹配（即均值 \(>99\)）
5. 由平均原理，存在位置匹配数 \(\geq 100\)

序列单调子序列

定理：任意\(n^2+1\)个数的序列必存在长度为\(n+1\)的单调（非增或非减）子序列。

证明思路：

1. 对每个数\(a_k\)，记\(m_k\)为从它开始的最长非减序列长度
2. 若某个\(m_k\geq n+1\)，则存在所需非减序列
3. 否则所有\(m_k\leq n\)，由鸽巢原理至少有\(n+1\)个\(m_k\)相等
4. 则这\(n+1\)个\(k_{i}\)位置的数必须非增关系 反证：如果它们不是非增关系，则存在 \(i<j, a_{i}<a_{j}\)，\(a_{i}\)放在 \(a_{j}\)前面可以构成一个比 \(m_{k}\) 更长的非减序列，与\(m_{i}=m_{j}=m_{k}\)产生矛盾

二项式系数

基本定义

二项式系数\(\binom{n}{k}\)的定义：

1. 当\(k > n\)时，\(\binom{n}{k} = 0\)
2. 当\(k = 0\)时，\(\binom{n}{0} = 1\)
3. 当\(1 \leq k \leq n\)时，\(\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}\)

二项式系数 \(\binom{n}{k}\) 等于组合数 \(C_n^k\)

性质：

• 对称性：\(\binom{n}{k} = \binom{n}{n-k}\)（当\(0 \leq k \leq n\)时）
• 帕斯卡公式：\(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)

杨辉三角/帕斯卡三角

杨辉三角中的数具有以下特点：

1. 边界上的数都是\(1\)
2. 其他数等于其上方和左上方两个数之和
3. 第\(n\)行的和为\(2^n\)，即\(\sum_{k=0}^n \binom{n}{k} = 2^n\)

特殊数列：

• 第1列：\(\binom{n}{1} = n\)（计数数）
• 第2列：\(\binom{n}{2} = \frac{n(n-1)}{2}\)（三角形数）
• 第3列：\(\binom{n}{3} = \frac{n(n-1)(n-2)}{3!}\)（四面体数）

二项式定理

定理：设\(n\)为正整数，对所有的\(x\)和\(y\)，有：

\[(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^{n-k}y^k\]

等价形式：

1. \((x+y)^n = \sum_{k=0}^n \binom{n}{n-k}x^{n-k}y^k\)
2. \((x+y)^n = \sum_{k=0}^n \binom{n}{n-k}x^ky^{n-k}\)
3. \((x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k}\)

特殊情况：

• \((1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k = \sum_{k=0}^n \binom{n}{n-k}x^k\)

常见展开式：

• \((x+y)^2 = x^2 + 2xy + y^2\)
• \((x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\)
• \((x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\)

多项式定理

定义：多项式\((x_1+x_2+\cdots+x_t)^n\)的系数为：

\[\binom{n}{n_1,n_2,\cdots,n_t} = \frac{n!}{n_1!n_2!\cdots n_t!}\] 其中\(n_1,n_2,\cdots,n_t\)是非负整数，且\(n_1+n_2+\cdots+n_t=n\)

性质：

1. 二项式系数可表示为：\(\binom{n}{k} = \binom{n}{k,n-k}\)

2. 帕斯卡公式：

   • 二项式：\(\binom{n}{k,n-k} = \binom{n-1}{k,n-k-1} + \binom{n-1}{k-1,n-k}\)
   • 多项式：\(\binom{n}{n_1,n_2,\cdots,n_t} = \sum_{i=1}^t \binom{n-1}{n_1,\cdots,n_i-1,\cdots,n_t}\)

设\(n\)为正整数，对所有的\(x_1,x_2,\cdots,x_t\)，有：

\[(x_1+x_2+\cdots+x_t)^n = \sum \frac{n!}{n_1!n_2!\cdots n_t!}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}\] 其中求和是对所有满足\(n_1+n_2+\cdots+n_t=n\)的非负整数解进行的。

例子：在\((x_1+x_2+x_3+x_4+x_5)^7\)的展开式中，\(x_1^2x_3x_4^3x_5\)的系数为\(\binom{7}{2,0,1,3,1} = 420\)

注：展开式中不同项的个数等于方程\(n_1+n_2+\cdots+n_t=n\)的非负整数解的个数，即\(\binom{n+t-1}{n}\)

"选板法"： \(n + t-1\) 个位置选 \(t-1\) 个位置做挡板，剩下 \(n\) 个位置是 \(1\)，就相当于分成了 \(t\) 个区间，每个区间的 \(1\) 的个数是非负整数，\(\binom{n+t-1}{n}=\binom{n+t-1}{t-1}\) 。

组合数递推

根据帕斯卡公式以及杨辉三角对称性，熟练掌握组合数递推模板

typedef long long LL;
LL cm[maxn][maxn];
void ComList() {
    for(int i = 0; i < maxn; i ++)
        for(int j = 0; j <= i; j ++) {
            if(j > i - j) cm[i][j] = cm[i][i - j];
            else if(!j) cm[i][j] = 1;
            else cm[i][j] = j == 1 ? i : cm[i - 1][j] + cm[i - 1][j - 1];
        }
}

特殊计数序列科普

卡特兰数（Catalan Numbers）

应用场景：

• 括号匹配：\(n\)对括号有多少种合法的排列方式（任意前缀中左括号不少于右括号）
• 找零问题：\(n\)个人拿50美分，\(n\)个人拿1美元，售票处总有零钱找的排队方式数
• 网格路径：在\(n×n\)网格中从\((0,0)\)走到\((n,n)\)，不越过对角线的路径数
• 三角剖分：凸多边形被在其内部不相交的对角线划分成三角形区域的方法数
• 二叉树：\(n\)个节点能构成多少种不同的二叉树。

公式：

第\(n\)个卡特兰数为：

\[ C_n = \frac{1}{n+1} \binom{2n}{n}, \quad C_0=1. \]

例：找零问题
\(2n\)个人排成一列进入剧场。入场费为50美分。其中\(n\)个人有50美分硬币，\(n\)个人有1美元纸币。有多少种排队方法使得每当有1美元的人买票时，售票处总有50美分硬币找零？

将50美分视为\(+1\)，1美元视为\(-1\)，合法序列要求任意前缀和\(\geq 0\)，等价于括号匹配问题，答案为第\(n\)个卡特兰数：

卡特兰数简要推导：

1. 考虑所有可能的排列方式，总数为\(\binom{2n}{n}\)
2. 考虑不合法的情况（前缀和为负）
   1. 对于每个不合法序列，找到第一个前缀和为-1的位置，将之前的所有数取反
   2. 这样得到“\(n+1\)个\(+1\)和\(n-1\)个\(-1\)”的序列
   3. 不合法序列与这样的序列一一对应
   4. 因此不合法序列数为\(\binom{2n}{n+1}\)，即“\(n+1\)个\(+1\)和\(n-1\)个\(-1\)”
3. 合法序列数 = 总数 - 不合法数 = \(\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}\)

第二类斯特林数（Stirling Numbers of the Second Kind）

应用场景：

• 分组问题：将\(p\)个不同的物品分成\(k\)个不可区分的非空盒子（如划分集合）。
• 等价关系：\(p\)个元素的集合划分为\(k\)个非空子集的方案数。

公式：

记作\(S(p,k)\)，满足递推关系：

\[ S(p,k) = k \cdot S(p-1,k) + S(p-1,k-1), \]
初始条件：\(S(p,p)=1\), \(S(p,0)=0\)（\(p \geq 1\)）。

例子：

• \(S(4,2)=7\)：将4个物品分成2组的方案，如\(\{1\}\{2,3,4\}\)、\(\{1,2\}\{3,4\}\)等。

贝尔数（Bell Numbers）

应用场景：

• 集合划分总数：\(p\)个元素的集合所有可能的非空子集划分方式数（不限定子集数量）。

与斯特林数的关系：

\[ B_p = \sum_{k=0}^p S(p,k). \]

递推公式：

\[ B_p = \sum_{t=0}^{p-1} \binom{p-1}{t} B_t. \]

例子：

• \(B_3=5\)：对应划分：\(\{1,2,3\}\)、\(\{1\}\{2,3\}\)、\(\{2\}\{1,3\}\)、\(\{3\}\{1,2\}\)、\(\{1\}\{2\}\{3\}\)。

第一类斯特林数（Stirling Numbers of the First Kind）

应用场景：

• 循环排列：将\(p\)个物品排成\(k\)个非空的循环排列（如圆桌座位）。

递推公式：

\[ s(p,k) = (p-1) \cdot s(p-1,k) + s(p-1,k-1). \]

例子：

• \(s(4,2)=11\)：将4个物品分成2个循环排列的方案，如\((1\,2\,3)(4)\)、\((1\,3\,4)(2)\)等。

大Schroder数与小Schroder数

应用场景：

• 格路径：从\((0,0)\)到\((n,n)\)的路径，允许水平、垂直和对角步（HVD），且不越过对角线（大Schroder数\(R_n\)）。
• 加括号问题：对序列\(a_1 a_2 \cdots a_n\)添加括号的方式数（小Schroder数\(s_n\)，允许括号包含多个元素）。

关系：

\[ R_n = 2 s_{n+1} \quad (n \geq 1). \]

例子：

• \(n=3\)时，小Schroder数\(s_3=3\)：对应加括号方式为a1(a2a3), (a1a2)a3, a1a2a3（注意与卡特兰数的区别）。

总结表格

序列	记号	应用场景	前几项（从\(n=0\)）
卡特兰数	\(C_n\)	括号匹配、路径不越对角线	1, 1, 2, 5, 14, 42
第二类斯特林	\(S(p,k)\)	集合划分到\(k\)个子集	\(S(3,2)=3\)
贝尔数	\(B_p\)	集合所有划分方式	1, 1, 2, 5, 15, 52
第一类斯特林	\(s(p,k)\)	循环排列数	\(s(4,2)=11\)
大Schroder数	\(R_n\)	HVD格路径	1, 2, 6, 22, 90
小Schroder数	\(s_n\)	广义加括号方式	1, 1, 3, 11, 45

使用技巧：准备常用数列表，遇事不决暴力打表，人工观察找规律

Nim 游戏

• 游戏设置：有 $ k $ 堆硬币，每堆分别有 $ n_1, n_2, , n_k $ 枚硬币。

• 玩家轮流取子：

  • 玩家 I（先手）和玩家 II（后手）交替进行。
  • 每次从某一堆中取走至少一枚硬币。

• 胜负判定：取走最后一枚硬币的玩家获胜。

2 堆 Nim 游戏的策略

• 关键观察：若两堆硬币数不等（$ n_1 n_2 $），玩家 I 必胜；否则玩家 II 必胜。

• 必胜策略：

  1. 玩家 I 从较多的堆中取硬币，使两堆数量相同。
  2. 之后，玩家 I 模仿玩家 II 的操作：若玩家 II 从一堆取 $ c $ 枚，玩家 I 从另一堆取 $ c $ 枚。

• 示例：

  初始状态：(8, 5)
  玩家 I 取 3 → (5, 5)      // 使两堆相同
  玩家 II 取 2 → (5, 3)
  玩家 I 取 2 → (3, 3)      // 模仿对手
  玩家 II 取 1 → (3, 2)
  玩家 I 取 1 → (2, 2)      // 继续模仿
  ...
  玩家 I 取走最后一枚硬币获胜。

---

通用 $ k $-堆 Nim 游戏的策略

• 二进制表示：将每堆硬币数 $ n_i $ 表示为二进制，例如 $ 53 = 110101_2 $。

• 平衡状态：对于所有二进制位，统计所有堆在该位上为 1 的总数。若所有位总数均为偶数，则游戏平衡。

• 胜负判定：

  • 非平衡状态：玩家 I 必胜，可通过一步操作使游戏平衡。
  • 平衡状态：玩家 II 必胜。

• 必胜策略：

  1. 找到最高不平衡位（即 1 的总数为奇数的最高位）。
  2. 选择一个该位为 1 的堆，调整其硬币数，使得各个位的总数均变为偶数。
  3. 对手的任何操作都会破坏平衡，玩家 I 可重复此策略直至获胜。

尝试：

• 堆大小：10, 20, 30, 40, 50。

• 二进制表示：

  10: 001010
  20: 010100
  30: 011110
  40: 101000
  50: 110010

• 位统计（从右到左，位 0 开始）：

  • 位 1: 总数 = 3（非平衡）
  • 位 4: 总数 = 3（非平衡）

• 玩家 I 的操作：

  1. 选择最高非平衡位（位 4），并选中该位为 1 的堆（如 50）。
  2. 将 50 调整为 $ 50 = 50 (10 ) = 40 $。
  3. 需从 50 中取走 $ 50 - 40 = 10 $ 枚，使堆变为 40。

• 验证平衡：

  调整后堆：10, 20, 30, 40, 40
  二进制统计：  
  
  
  位 0-5 的 1 总数均为偶数 → 游戏平衡。

  此后，玩家 II 的任何操作都会破坏平衡，玩家 I 可维持策略获胜。