竞赛组合：计数、抽屉与构造

初中组合题强调“分类是否完备、计数是否重复、构造是否可验证”。

一、核心知识点讲解

1. 加法与乘法原理

• 加法原理：互斥情形总数为各类相加。
• 乘法原理：分步骤独立选择时总数为各步相乘。
• 常见失误：未确认“互斥”就直接相加，或重复计数后未去重。

2. 隔板法与简单分配

• 非负整数解 $x_1+\cdots+x_k=n$ 个数为

$\binom{n+k-1}{k-1}.$

• 正整数解可先令 $y_i=x_i-1$ 转为非负情形。

3. 抽屉原理与极值存在

• $n$ 个物体放入 $m$ 个抽屉，若 $n>m$，至少一抽屉含 2 个及以上物体。
• 强化型：至少有一个抽屉含不少于 $\left\lceil\frac{n}{m}\right\rceil$ 个物体。

4. 染色与不变量

• 染色法用于判断可达性和覆盖性。
• 奇偶性、颜色数守恒、连通块结构常是关键不变量。

实战策略

遇到组合题先写出“样本空间定义 + 分类标准”，再开始计算，可显著降低漏解和重计风险。

---

二、经典例题实战

例题 1：分步计数

从数字 $1,2,3,4,5$ 中选 3 个不同数字组成三位数，能组成多少个？

点击查看解析与答案

解析过程

1. 百位有 5 种选法。
2. 十位剩 4 种选法。
3. 个位剩 3 种选法。
4. 总数 $5\times4\times3=60$。

答案

$60$ 个。

例题 2：隔板法

求非负整数解个数：$x+y+z=10$。

点击查看解析与答案

解析过程

1. 3 个变量和为 10。
2. 用隔板法：

$\binom{10+3-1}{3-1}=\binom{12}{2}=66.$

答案

$66$。

例题 3：抽屉原理

在任意 13 个整数中，证明必有两个数同余于模 12。

点击查看解析与答案

解析过程

1. 模 12 的余数只有 12 类（0 到 11）。
2. 13 个整数放入 12 个余数类。
3. 由抽屉原理，至少两数落在同一类。

答案

命题成立。

例题 4：染色法判不可覆盖

标准 $8\times8$ 棋盘去掉两个同色角格，能否被 $1\times2$ 多米诺完全覆盖？

点击查看解析与答案

解析过程

1. 棋盘黑白染色，原本黑白各 32 格。
2. 去掉两个同色角格后，黑白格数量变为 30 和 32。
3. 每块多米诺必覆盖一黑一白。
4. 黑白数量不等，故不可能完全覆盖。

答案

不能覆盖。

---

三、配套练习（点击展开答案）

练习 1

从 6 名同学中选班长、学习委员（两职不同人），有多少种选法？

点击查看过程与答案

过程

班长 6 选 1，学习委员 5 选 1，共 $6\times5=30$。

答案

$30$。

练习 2

求正整数解个数：$a+b+c=12$。

点击查看过程与答案

过程

令 $a'=a-1,b'=b-1,c'=c-1$，则

$a'+b'+c'=9,\ a',b',c'\ge0.$

解数为

$\binom{9+3-1}{3-1}=\binom{11}{2}=55.$

答案

$55$。

练习 3

任取 9 个整数，证明必有两个整数差是 8 的倍数。

点击查看过程与答案

过程

按模 8 余数分为 8 类，取 9 个整数，抽屉原理得至少两个同余模 8，差即为 8 的倍数。

答案

命题成立。

练习 4

把 8 个相同小球放入 4 个不同盒子（盒子可空），有多少种放法？

点击查看过程与答案

过程

设盒中球数为 $x_1,x_2,x_3,x_4$，满足

$x_1+x_2+x_3+x_4=8,\ x_i\ge0.$

隔板法：

$\binom{8+4-1}{4-1}=\binom{11}{3}=165.$

答案

$165$。