- 推导并运用组合数公式 \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\)，说明组合数与排列数的关系；
- 依据"次序是否重要"判别一个计数问题应使用排列还是组合；
- 陈述二项式定理，并用"从 \(n\) 个因子中选 \(k\) 个"的组合论证说明各项系数的来历；
- 证明对称恒等式与帕斯卡恒等式，会用帕斯卡三角形组织二项式系数的计算；
- 解决委员会选举、按性别分组、扑克牌发牌等典型的组合计数问题。
1. 从排列到组合：不计次序地选取
1.3 节的排列回答的是"按次序安排对象"的计数问题：席位有主次、名次有先后，交换两个被选对象的位置就得到新结果。然而许多现实中的选取并不在乎次序——从 10 名候选人中选出 3 人组成委员会，谁先谁后毫无区别；发到手里的 5 张扑克牌，先拿红桃 A 再拿黑桃 K 与相反次序得到的是同一手牌。本节研究这类不计次序的选取问题，其核心概念是组合(combination)。
从 \(n\) 个不同对象中取出 \(k\) 个（\(0\le k\le n\)）所构成的无序结果称为一个组合(combination)；所有不同组合的个数记作 \(\binom{n}{k}\)，也写作 \(C(n,k)\)，读作"\(n\) 取 \(k\)"。
约定 \(\binom{n}{0}=1\)：什么都不选，恰有一种方式。两个组合只要含有的对象完全相同就被视为同一个，与取出的先后次序无关。
定义本身并没有给出计数方法。下面的定理把组合数化为阶乘运算，其证明是 1.2 节计数基本原理的典范应用——"先选后排"。
对 \(0\le k\le n\)，\(\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}\)，且组合数与排列数满足关系 \[ \binom{n}{k}\cdot k! \;=\; n(n-1)\cdots(n-k+1)\;=\;\frac{n!}{(n-k)!}\,. \]
直观地说：每个组合恰好"膨胀"为 \(k!\) 个排列，所以排列数恰是组合数的 \(k!\) 倍。做题时若担心算重，可用这层关系作检验。
从 10 名成员中选出 3 人组成委员会。(a) 有多少种组成方式？(b) 若已知成员张三必须入选并担任主席，有多少种方式？(c) 若委员会只要求设主席一名（人选不限），又有多少种方式？
2. 二项式系数与二项式定理
组合数 \(\binom{n}{k}\) 还有一个更著名的名字，它来自代数中最重要的展开式。
对整数 \(0\le k\le n\)，数 \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\) 称为二项式系数(binomial coefficient)，因为它是二项式 \((x+y)^n\) 展开式中 \(x^k y^{\,n-k}\) 项的系数（见定理 2）。
\[ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}\,x^{k}y^{\,n-k}\,. \]
在定理中令 \(x=y=1\)，立刻得到一个常被引用的推论： \[ \sum_{k=0}^{n}\binom{n}{k}=2^{\,n}\,. \] 它的组合意义同样清楚：\(n\) 个人任意组队（从一人不选到全部入选），按入选人数 \(k\) 分类计数得左边；而每个人都独立地面对"入选与否"两种选择，由乘法原理得右边 \(2^n\)。同一个量、两种数法——这正是组合恒等式证明的通用思路。
3. 两条基本恒等式与帕斯卡三角形
二项式系数之间有许多漂亮的恒等式，下面两条最常用。它们的证明都是"讲一个计数故事"：为等式两边找到同一个计数对象的两种数法。
\[ \binom{n}{k}=\binom{n}{n-k}\,. \]
对 \(1\le k\le n-1\)， \[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\,. \]
把二项式系数排成金字塔，每行由上一行生成，这个图形如今通称帕斯卡三角形(Pascal's triangle)。帕斯卡在《论算术三角形》（约 1654 年写成）中系统研究了它的性质，并在与费马关于赌金分配的通信（见 1.1 节）中用它计算组合数。中国南宋数学家杨辉在 1261 年《详解九章算法》中已记载了同一图形，并注明源于北宋贾宪（约 11 世纪），故中文文献亦称"杨辉三角"或"贾宪三角"，早于欧洲数百年。手算组合数时，沿三角形逐行递推是避免大阶乘的实用办法。
4. 排列还是组合：判别与应用
至此我们手里有了两件工具，剩下的关键一步是判断该用哪一件。口诀只有一句话：次序重要用排列，次序无关用组合。具体检验法：设想交换两个被选对象的位置——若结果随之改变（席位、名次、先后），是排列问题；若结果不变（委员会、小组、一手牌），是组合问题。凡题面出现"职位、冠军亚军季军、依次、第几位"等字样，几乎都隐含着次序。
| 项目 | 排列（次序重要） | 组合（次序无关） |
|---|---|---|
| 选取结果 | 有序序列 | 无序集合 |
| 计数公式 | \(\dfrac{n!}{(n-k)!}\) | \(\dfrac{n!}{k!(n-k)!}\) |
| \(9\) 人中选 \(3\) 人 | \(9\times 8\times 7=504\) | \(\binom{9}{3}=84\) |
| 典型情境 | 席位、名次、先后顺序 | 委员会、小组、一手牌 |
某协会有 12 名女性与 10 名男性成员，要从中选出 5 人组成委员会，且恰好 2 名女性、3 名男性。共有多少种组成方式？
一副标准扑克牌 52 张（4 种花色各 13 点）。(a) 发一手 5 张牌，共有多少种不同的手牌？(b) 其中"四条"（four of a kind，即 4 张同点数加 1 张其他点数的牌）有多少种？
5. 本节小结
- 组合是不计次序的选取：\(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\)，约定 \(\binom{n}{0}=1\)。
- 核心关系：排列数 \(=\) 组合数 \(\times\, k!\)；判别口诀——次序重要用排列，次序无关用组合。
- 二项式定理：\((x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^k y^{\,n-k}\)；令 \(x=y=1\) 得 \(\sum_{k=0}^{n}\binom{n}{k}=2^n\)。
- 对称性 \(\binom{n}{k}=\binom{n}{n-k}\)；帕斯卡恒等式 \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)，它们构成帕斯卡三角形的两条生成规则。
- 多部分选取（如恰 2 女 3 男）用乘法原理把各部分的组合数相乘；"至少……"型问题可先算总数再减补集（见练习 1）。下一节 1.5 节把组合推广为多项式系数，处理分成两组以上的分配问题。
练习
练习 1-4-1
从 12 名女性与 10 名男性中选 5 人委员会，要求至少含 1 名女性，共有多少种方式？（提示：补集法）
答案与提示用补集法(complementary counting)：总数 \(\binom{22}{5}=26{,}334\)，减去"全是男性"的 \(\binom{10}{5}=252\)，得 \(26{,}334-252=26{,}082\) 种。若按女性人数 \(k=1,\dots,5\) 直接分类求 \(\sum \binom{12}{k}\binom{10}{5-k}\)，结果相同但计算繁得多——"至少"型问题优先考虑补集。
练习 1-4-2
\(\binom{2n}{n}\) 的组合意义是什么？并借此说明 \(\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}\)。
答案与提示\(\binom{2n}{n}\) 表示从 \(2n\) 个不同对象中选取 \(n\) 个的方式数。设想对象由 \(n\) 名女性与 \(n\) 名男性组成，从这 \(2n\) 人中选出 \(n\) 人（不限性别）：按女性入选人数 \(k\) 分类，得 \(\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k}\) 种；由对称性 \(\binom{n}{n-k}=\binom{n}{k}\)，即 \(\sum_{k=0}^{n}\binom{n}{k}^{2}\)。两种数法相等，这正是范德蒙德恒等式(Vandermonde's identity)的特例。
练习 1-4-3
只用帕斯卡恒等式与边界值 \(\binom{n}{0}=\binom{n}{n}=1\)，计算 \(\binom{6}{3}\)，并与公式直接计算的结果核对。
答案与提示逐层下推：\(\binom{6}{3}=\binom{5}{2}+\binom{5}{3}\)；\(\binom{5}{2}=\binom{4}{1}+\binom{4}{2}=4+6=10\)，\(\binom{5}{3}=\binom{4}{2}+\binom{4}{3}=6+4=10\)；其中 \(\binom{4}{2}=\binom{3}{1}+\binom{3}{2}=3+3=6\)。故 \(\binom{6}{3}=10+10=20\)，与 \(\dfrac{6!}{3!\,3!}=20\) 一致（见图 1 第 6 行）。
练习 1-4-4
用两种方法证明 \(\sum_{k=0}^{n}\binom{n}{k}=2^n\)，并求 \(n=10\) 时的值。
答案与提示代数方法：在二项式定理中令 \(x=y=1\)。组合方法：\(n\) 个人的一切组队方式（含空队与全队），按入选人数分类得左边；而每人独立地"入选或不入选"，由乘法原理得 \(2^n\)。\(n=10\) 时 \(2^{10}=1024\)。