组合数学
第 5 页:可重复组合与高级问题
🔁 可重复组合
从 n 种类型中选 k 个物品时,允许同一类型多次被选中:
\(\binom{n+k-1}{k} = \binom{n+k-1}{n-1}\)
✏️ 例子 1:选糖果
有 4 种糖果(红、蓝、绿、黄)。有多少种方法选 6 颗糖果?
n = 4 种类型,k = 6 颗,允许重复
\(\binom{4+6-1}{6} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{6} = 84\)
✏️ 例子 2:分钱
有多少种方法把 10 元(相同的)分给 3 个孩子?
n = 3 个孩子,k = 10 元
\(\binom{3+10-1}{10} = \binom{12}{10} = \binom{12}{2} = 66\)
🎱 "球与隔板"方法 (Stars and Bars)
"将 k 个相同物品分到 n 个组"类型的问题
💡 思路:
把物品标为 ★,组与组之间的隔板标为 |
★★★|★|★★★★ = (3,1,4)
8 个球分到 3 个组
📐 公式:
k 个球到 n 个组 = 从 (k+n-1) 个位置中选 (n-1) 个放隔板
\(\binom{k+n-1}{n-1} = \binom{k+n-1}{k}\)
✏️ 例子 3:有多少种方法把 12 写成 4 个非负整数之和?
(即:\(x_1 + x_2 + x_3 + x_4 = 12\) 其中 \(x_i \geq 0\))
k = 12,n = 4
\(\binom{12+4-1}{4-1} = \binom{15}{3} = \frac{15 \times 14 \times 13}{6} = 455\)
⚡ 球与隔板 - 带最小条件
✏️ 例子 4:\(x_1 + x_2 + x_3 + x_4 = 12\) 其中 \(x_i \geq 1\)
(每个变量至少为 1)
方法:代入 \(y_i = x_i - 1\),所以 \(y_i \geq 0\)
\((y_1+1) + (y_2+1) + (y_3+1) + (y_4+1) = 12\)
\(y_1 + y_2 + y_3 + y_4 = 8\)
\(\binom{8+4-1}{3} = \binom{11}{3} = 165\)
📐 通用公式:
若 \(x_1 + x_2 + ... + x_n = k\) 且 \(x_i \geq m\) 对所有 i 成立:
\(\binom{k - nm + n - 1}{n-1}\)
👥 分组
类型 1:不同大小的组(有标记)
✏️ 例子 5:10 个学生分成 5、3、2 人的组。有多少种方法?
\(\binom{10}{5} \times \binom{5}{3} \times \binom{2}{2} = 252 \times 10 \times 1 = 2520\)
类型 2:相同大小的组(无标记)
✏️ 例子 6:12 个学生分成 3 组,每组 4 人。有多少种方法?
先按有标记的方式来分:
\(\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = 34650\)
现在除以 3! 因为组是相同的(谁是"第一组"无关紧要):
\(\frac{34650}{3!} = \frac{34650}{6} = 5775\)
📐 通用公式:
n 个元素分到 k 个相同大小的组,每组 \(\frac{n}{k}\) 个元素:
\(\frac{n!}{\left(\frac{n}{k}\right)!^k \times k!}\)
🧮 方程的解的数量
✏️ 例子 7:下列方程有多少个自然数解(\(x,y,z > 0\)):
\(x + y + z = 20\)
每个变量 ≥ 1,代入 \(x' = x-1, y' = y-1, z' = z-1\)
\(x' + y' + z' = 17\) 其中 \(x',y',z' \geq 0\)
\(\binom{17+3-1}{3-1} = \binom{19}{2} = 171\)
✏️ 例子 8:下列不等式有多少个非负整数解:
\(x + y + z \leq 10\)
方法:添加"slack"变量 w,使得 \(x + y + z + w = 10\)
现在有 4 个变量 ≥ 0,和为 10:
\(\binom{10+4-1}{4-1} = \binom{13}{3} = 286\)
📋 总结表 - 何时使用哪个?
| 问题类型 | 顺序重要? | 重复? | 公式 |
|---|---|---|---|
| 排列 | ✓ | ✗ | \(n!\) |
| 部分排列 | ✓ | ✗ | \(P(n,k) = \frac{n!}{(n-k)!}\) |
| 可重复排列 | ✓ | ✓ | \(n^k\) |
| 组合 | ✗ | ✗ | \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\) |
| 可重复组合 | ✗ | ✓ | \(\binom{n+k-1}{k}\) |
💡 考试技巧
相同的球:可重复组合
最小条件:替换变量
相同大小的组:除以 k!
📝 第 5 页总结
可重复组合:\(\binom{n+k-1}{k}\)
球与隔板:k 个物品分到 n 个组