计数原理、排列组合与二项式系数

计数问题问的是“有多少种可能”。这句话看起来简单，真正难的地方不在公式本身，而在于先把“可能”说清楚：一个结果到底由哪些选择组成，两个看起来不同的记录是否算同一个结果，某个对象能不能被重复使用。

本章先建立两个基本原则：加法原理和乘法原理。接着用树状选择把计数过程画出来，再进入排列、组合、重复选择和二项式系数。学完以后，你应能在看到题目时先判断模型，而不是先搜索某个熟悉公式。

计数不是把所有结果都列出来才算严谨。好的计数方法会建立一个清楚的对应：每个合法结果被数一次，且只被数一次。

计数前先问三个问题

很多计数错误不是算术错，而是对象没有定清楚。开始套公式前，先问三个问题。

第一个问题是：这些选择是否互斥？如果一个结果只能落入某一类，通常用加法；如果一个结果由多个连续步骤组成，通常用乘法。

第二个问题是：顺序是否重要？同样选出甲、乙、丙三个人，若要安排第一名、第二名、第三名，顺序重要；若只是组成一个三人小组，顺序不重要。

第三个问题是：是否允许重复？三位数字密码通常允许同一个数字重复出现；从班级里选三名代表通常不允许同一个人被选两次。

顺序是否重要的排列组合判断图，对比座位顺序不同算不同结果，小组换顺序仍是同一结果。 — 顺序是否重要，是排列组合题的第一道分岔口。

不要把“抽出来的动作有先后”误认为“结果的顺序重要”。若题目只问“选出哪几个人”，哪怕你在草稿上一个一个选，最终结果仍然是无序集合。

下面的交互可以练习这个分类过程。先读题意，再选择顺序与重复条件，观察公式为什么随条件改变。

加法原理与乘法原理

加法原理处理“分情况选择”。如果事件可以分成互不重叠的几类，且每个结果只属于其中一类，那么总数就是各类数量相加。

若集合 $A$ 和 $B$ 不相交，则

|A\cup B|=|A|+|B|

例如，某课程作业可以选择“写证明题”或“做建模题”，两类不能同时选。若证明题有 4 道可选，建模题有 3 道可选，那么共有 $4+3=7$ 种选法。

乘法原理处理“连续步骤”。如果一个结果由第一步和第二步共同决定，第一步有 $m$ 种选择，且每一种第一步之后第二步都有 $n$ 种选择，那么总数是

m\cdot n

例如，主食有 3 种，饮品有 2 种，一份套餐由一个主食和一个饮品组成，那么共有 $3\cdot2=6$ 种套餐。

加法原理与乘法原理对比信息图，左侧展示互斥选择用加法，右侧展示连续选择用乘法 — 加法原理数互斥类别，乘法原理数连续步骤。

分情况时每一类内部也可以用乘法

实际题目常常同时使用两种原则。先按互斥情况分类，再在每一类中用乘法数清楚。

例如，一个 3 位密码由数字组成。第一位不能是 0。若密码必须是偶数，最后一位只能是 $0,2,4,6,8$ 。这里可以按最后一位是否为 0 分情况。

若最后一位是 $0$ ，第一位可以从 $1$ 到 $9$ 中选，有 $9$ 种；中间一位可以从 $0$ 到 $9$ 中选，有种。因此这一类有种。

如果几个类别有重叠，不能直接相加。比如“喜欢数学的人数”和“喜欢计算机的人数”可能包含同一批人。重叠计数会在下一章用容斥原理专门处理。

树状选择

树状选择把乘法原理画成路径。每一层表示一步选择；从根走到叶子的一条完整路径表示一个最终结果。

如果每个第一层分支下面都有同样数量的第二层分支，叶子数就是分支数相乘。如果不同分支下面的选择数不一样，可以先数每个大分支的叶子，再把它们相加。

从开始节点分出上衣红蓝黑，再分别选择裤子灰白，形成六种搭配的树状选择图。 — 树状选择把每条从根到叶的路径对应为一种结果。

树状图特别适合检查两个问题：有没有漏掉某一类分支，某个结果有没有被不同路径重复到达。只要路径和结果是一一对应的，叶子数就是结果数。

下面的交互允许你改变每一层的分支数。连续选择对应乘法；互斥选择对应加法。把树改成非均匀分支时，注意不要强行套一个单一乘积。

例题：图书馆路径码

某图书馆给阅览区编号。第一位表示楼层，有 $4$ 种；第二位表示区域，每层有 $6$ 种；第三位表示书架，每个区域有 $8$ 个书架。问这样的路径码有多少种。

一个路径码由三步选择共同决定：楼层、区域、书架。题目不是让我们在三类对象中任选一种，而是每个结果都必须包含三步。

每一步选择数分别是 $4,6,8$ 。同一楼层下区域数相同，同一区域下书架数也相同，所以可以直接使用乘法原理。

路径码总数为

排列：顺序重要且不重复

排列处理的是“给位置依次放对象”。如果从 $n$ 个不同对象中选出 $k$ 个放入 $k$ 个有序位置，且每个对象最多用一次，那么第一位有 $n$ 种选择，第二位剩 $n-1$ 种，依次类推。

这类数记作 $P(n,k)$ ：

P(n,k)=n(n-1)(n-2)\cdots(n-k+1)

也可以写成阶乘形式：

P(n,k)=\frac{n!}{(n-k)!}

当 $k=n$ 时，就是把 $n$ 个对象全部排成一列，共有

n!

种排列。

不重复排列的槽位模型，四个对象中选三个依次放入三个有序槽位，可选数依次为四、三、二。 — 排列可以看成给有序槽位依次放对象。

例题：安排发言顺序

有 8 名同学报名分享，课堂上只安排 3 个发言位置：第一位、第二位、第三位。同一名同学不能重复发言。问共有多少种安排。

先判断顺序是否重要。第一位发言和第三位发言不是同一个安排，所以顺序重要。

再判断是否允许重复。同一名同学不能重复发言，所以是不重复排列。

三个位置依次有 $8,7,6$ 种选择，因此共有

排列公式不是额外记忆出来的。它只是乘法原理在“不放回、有序槽位”场景中的简写。

组合：顺序不重要

组合处理的是“选出一个小组”。如果从 $n$ 个不同对象中选出 $k$ 个，且顺序不重要，那么每个 $k$ 人小组在排列中被数了 $k!$ 次。于是组合数为

\binom{n}{k}=\frac{P(n,k)}{k!}

也就是

\binom{n}{k}=\frac{n!}{k!(n-k)!}

读作“ $n$ 选 $k$ ”。它也常写作 $C(n,k)$ 。本章以后主要使用 $\binom{n}{k}$ ，因为它和二项式系数的写法一致。

从 5 个对象中选 3 个，同一小组的 6 种内部排列围成一圈，说明组合公式要除以 3!。 — 组合计数可先按顺序排列，再除以同一小组的重复排列数。

例题：选项目小组

一个班有 10 名同学，要选出 4 名组成项目小组，不设组长。问有多少种小组。

先判断顺序是否重要。题目只关心小组成员是谁，不关心谁先被选中，所以顺序不重要。

如果先按顺序选 4 人，会得到 $10\cdot9\cdot8\cdot7$ 种有序结果。但同一个 4 人小组内部可以排成 $4!$ 种顺序。

组合数有一个很常用的对称性：

\binom{n}{k}=\binom{n}{n-k}

它的组合解释很直接：从 $n$ 个对象中选出 $k$ 个留下，等价于选出 $n-k$ 个不留下。选中的集合确定了没选中的集合，反过来也一样。

看到 $\binom{n}{k}$ 时，不要只把它看成公式。它通常表示“从 $n$ 个位置、对象或步骤中挑出 $k$ 个”的选择。

重复与不重复

“是否允许重复”会改变每一步的选择数。最常见的四种模型可以按两个问题分类：顺序是否重要，是否允许重复。

四象限图对比允许重复和不允许重复、顺序重要和顺序不重要的计数模型 — 顺序与重复两个条件共同决定计数模型。

条件	典型问题	计数式
顺序重要，允许重复	长度为 $k$ 的密码，每位有 $n$ 种	$n^k$
顺序重要，不允许重复	从 $n$ 个对象中排 $k$ 个位置	$P(n,k)$

最后一类叫可重复组合。一个直观模型是“隔板法”：要从 $n$ 类物品中共选 $k$ 个，可以用 $k$ 个星号表示被选物品，用 $n-1$ 个隔板分开类别。于是问题变成：在 $k+n-1$ 个位置中选出 $k$ 个位置放星号。

所以可重复组合数为

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

例题：冰淇淋多球选择

冰淇淋店有 5 种口味，要选 3 球，可以重复选择同一种口味，且三球放入杯中不区分先后。问有多少种选择。

顺序不重要。草莓、巧克力、草莓和草莓、草莓、巧克力表示同一种杯中组合。

允许重复。同一种口味可以选多球，所以不能使用普通组合 $\binom{5}{3}$ 。

“可重复组合”只适用于同类物品可重复、并且最终顺序不重要的场景。若三球按第一球、第二球、第三球记录，就应使用 $5^3$ 。

二项式系数的组合解释

组合数 $\binom{n}{k}$ 又叫二项式系数。它之所以反复出现，是因为很多不同问题都能转化为“从 $n$ 个位置中选 $k$ 个位置”。

二项式系数的多重组合解释概念图 — 二项式系数可解释为选对象、放标记、展开式选项与网格路径转向位置。

下面是几个常见解释。

从 $n$ 个对象中选 $k$ 个，数量是 $\binom{n}{k}$ 。

长度为 $n$ 的二值序列中，恰好有 $k$ 个位置填入某个标记，数量也是 $\binom{n}{k}$ 。

从 $(a+b)^n$ 的 $n$ 个因子中，选择哪 $k$ 个因子贡献 $b$ ，其余因子贡献 $a$ ，数量仍是 $\binom{n}{k}$ 。

在只能向右和向上走的网格路径中，如果总共走 $n$ 步，其中 $k$ 步向上，那么路径数是 $\binom{n}{k}$ 。

组合证明的味道

组合解释可以用来证明恒等式。例如：

\binom{n}{k}=\binom{n}{n-k}

不是因为阶乘公式化简后碰巧相等，而是因为“选出 $k$ 个留下”和“选出 $n-k$ 个不留下”描述的是同一批选择，只是从相反角度记录。

再看 Pascal 恒等式：

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

它可以这样解释：从 $n$ 个对象中选 $k$ 个，固定看某个特殊对象甲。合法选择分成两类：包含甲，或者不包含甲。

若选择包含甲，则还要从其余 $n-1$ 个对象中选 $k-1$ 个，有 $\binom{n-1}{k-1}$ 种。

二项式定理与 Pascal 三角

二项式定理说，对任意非负整数 $n$ ，

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k

为什么系数是 $\binom{n}{k}$ ？把 $(a+b)^n$ 看成 $n$ 个因子的乘积：

(a+b)(a+b)\cdots(a+b)

展开时，每一项都来自每个因子中选 $a$ 或选 $b$ 。如果某一项含有 $k$ 个 $b$ ，就必须从 $n$ 个因子中选出 $k$ 个因子贡献 $b$ ，其余因子贡献 $a$ 。这种选法有种，所以的系数就是。

帕斯卡三角前六行与二项式展开系数的对应关系，突出显示相邻相加规则。 — Pascal 三角的第 (n) 行给出 ((a+b)^n) 的展开系数。

Pascal 三角从第 $0$ 行开始：

1

1\quad 1

1\quad 2\quad 1

1\quad 3\quad 3\quad 1

每个内部数等于它左上方和右上方两个数之和。这正是 Pascal 恒等式的数值版本。

下面的交互可以选择 $n$ 和 $k$ ，观察 $\binom{n}{k}$ 在 Pascal 三角、组合解释和二项式展开中的同一个位置。

例题：求展开式中的系数

求 $(2x-3)^6$ 中 $x^4$ 的系数。

把表达式看成 $(a+b)^6$ ，其中 $a=2x$ ， $b=-3$ 。一般项是

常见误区与检查清单

计数题最容易出现的错误，通常可以归到以下几类。

把有序结果当成无序结果。比如安排三个人坐三个座位是排列，不是组合。

把无序结果当成有序结果。比如选三名委员时，甲乙丙和丙乙甲是同一个小组。

忽略重复限制。密码、抽牌、选人、选口味的规则不同，同一个对象能否再次出现必须由题目决定。

把重叠类别直接相加。若两个条件可能同时满足，直接相加会重复计数。

把公式当作判断依据。正确顺序应是先判断对象，再选择公式。

一个可靠的计数解法通常能回答两句话：我数的对象是什么？为什么每个对象恰好被数一次？

小练习

从 12 名同学中选 3 名参加辩论队，不设队长，有多少种？

顺序不重要，且同一名同学不能重复选择，所以是普通组合：

\binom{12}{3}=220

从 12 名同学中选出队长、副队长、记录员各 1 名，同一人不能兼任，有多少种？

三个职位不同，顺序或角色重要，且不能重复，所以是不重复排列：

12\cdot11\cdot10=1320

一个 5 位数字验证码允许重复，且每一位都可以是 $0$ 到 $9$ ，有多少种？

顺序重要，允许重复。每位有 10 种选择，共有

10^5=100000

种。

有 6 种糖果，要买 4 颗，可以重复买同一种，且只关心每种糖果买了几颗，有多少种买法？

顺序不重要，允许重复，是可重复组合：

\binom{6+4-1}{4}=\binom{9}{4}=126

求 $(x+2)^7$ 中 $x^3$ 的系数。

一般项为

\binom{7}{k}x^{7-k}2^k

要得到 $x^3$ ，需要，所以。系数为

本章收束

本章的核心不是背下四个公式，而是建立计数判断的顺序。先判断结果对象，再看是互斥分类还是连续步骤；再判断顺序是否重要、是否允许重复；最后才选择排列、组合或二项式系数。

下一章会处理本章刻意避开的两类问题：类别之间有重叠时怎样避免重复计数，以及在有限位置中放入足够多对象时为什么必然出现重复。

10

4\cdot6\cdot8=192

8 \cdot 7 \cdot 6 = 336

8\cdot7\cdot6=336

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 12 章：计数原理、排列组合与二项式系数 | 自在学