数学复健5-基本记数原理

序言

有些问题不是在问一个对象是什么，而是在问：

满足条件的对象究竟有多少个？

例如：

• 一个长度为 $8$ 的二进制串有多少种？
• 从 $n$ 个人中选出 $k$ 个人有多少种？
• 一条路线由三次独立选择组成，一共有多少种走法？

逐个列出所有结果叫作枚举。

枚举在对象很少时可靠，但当选择层数增加时，数量会迅速膨胀：

$$ 2^{10}=1024, \qquad 2^{100}\approx 1.27\times 10^{30}.$$

计算机也无法靠“把一切都列出来”解决所有有限问题。

组合数学研究有限或离散对象怎样被选择、排列、分类、连接和计数。

组合数学的第一步，是把枚举背后的结构提取出来：

• 互斥分类用加法
• 连续选择用乘法

排列、组合、二项式系数与隔板法，都会从这两条规则生长出来。

本章始终区分：

对象本身 $\neq$ 对象的排列顺序 $\neq$ 对象所属的类别

有限集与基数

定义

如果一个集合里元素的个数是有限的、能数清楚的，就叫有限集

集合 $A=\{1,2,3\}$，一共三个元素，是一个有限集

集合 $B=\{a, b\}$，一共两个元素，也是一个有限集

严谨定义

有限集可以基于双射进行严谨定义：

一个集合 $A$ 称为有限集，当且仅当存在某个自然数 $n$，使 $A$ 与 $[n]$ 之间存在双射：

$$ f:A\to[n].$$

这里的 $[n]$ 是标准有限集：对自然数 $n$，定义：

$$ [n]=\{1,2,\ldots,n\}.$$

特别地 $n$ 为0对应的是空集，也是一个有限集：

$$ [0]=\varnothing.$$

双射表示：

• $A$ 中每个元素恰好对应一个编号；
• 每个编号恰好对应 $A$ 中一个元素。

这时称 $A$ 的基数或元素个数为 $n$，记作：

$$ |A|=n$$

性质1

对于有限集，自映射的单射、满射、双射，三者等价，即
若$f:A\to A$ ，单射 $\iff f$ 是满射 $\iff f$ 是双射

第一步:

证明：$f:[n]\to [n]$ ，单射 $\iff f$ 是满射

基例 $n=1$：$[1]=\{1\}$。单射只能 $f(1)=1$，显然是满射。成立。
归纳假设：对 $n=k$，任意单射 $f:[k]\to[k]$ 一定是满射。
归纳步骤 $n=k+1$：
设 $f:[k+1]\to [k+1]$ 是单射。
分两种情况：

1. $f(k+1)=k+1$：
   限制在 $[k]$ 上 $f|_{[k]}:[k]\to [k]$ 仍是单射。由归纳假设，$f|_{[k]}$ 满射到 $[k]$，于是整个 f 满射到 $[k+1]$。
2. $f(k+1)=m \neq k+1$，设 $f(t)=k+1$（$t\neq k+1$，后面证明这个 t 一定存在）。
   构造新映射 g：

$$ g(x)= \begin{cases} f(x), & x\neq t,k+1\\ m, & x=t\\ k+1, & x=k+1 \end{cases}$$

$g$ 仍然是单射，且 $g(k+1)=k+1$，回到情况 1，所以 $g$ 满射，从而 $f$ 也满射。

归纳完成：$[n]$ 上单射必满射。

第二步：

证明：$f:[n]\to [n]$，满射 $\implies$ 单射

反证法：
假设 $f$ 满射但不是单射，则存在 $a\neq b$，$f(a)=f(b)$。
那么像集的元素个数最多只有 $n-1$个，不可能覆盖全部 $n$ 个元素，与 “满射（像集 =$[n]$）” 矛盾。
所以满射一定是单射。

像集就是映射的像，也可以称做值域

第三步：

推广到一般有限集 A

因为 $|A|=n$，存在双射 $\varphi:A\to [n]$。
对 $f:A\to A$，构造

$$ \tilde f = \varphi \circ f \circ \varphi^{-1}: [n]\to [n]$$

映射复合保持单射、满射、双射：

• f 单射 $\iff \tilde f$ 单射
• f 满射 $\iff \tilde f$ 满射

我们已经知道 $\tilde f$ 单射$\iff\tilde f$满射，因此：

$$ f\text{ 单射}\iff f\text{ 满射}$$

而双射 = 单射 + 满射，所以三者等价。

性质2

两个有限集$A,B$
存在双射 $A\leftrightarrow B \iff |A|=|B|$
存在单射 $A\to B \iff |A|\le |B|$
存在满射 $A\to B \iff |A|\ge |B|$

交集与并集

两个集合 $A,B$ 的交集定义为：

$$ A\cap B = \{x\mid x\in A\land x\in B\}.$$

两个集合的并集定义为：

$$ A\cup B = \{x\mid x\in A\lor x\in B\}.$$

并集收集至少属于 $A$ 和 $B$ 中一个集合的全部元素。

不相交集合

如果：

$$ A\cap B=\varnothing,$$

就称 $A$ 与 $B$不相交。

不相交意味着没有对象同时属于两个集合。

多个集合 $A_1,\ldots,A_m$ 若满足：

$$ i\neq j \Longrightarrow A_i\cap A_j=\varnothing,$$

就称它们两两不相交。

这个条件决定了什么时候可以直接相加。

加法原理

加法原理

若 $A,B$ 是有限集，并且两者不相交：

$$ A\cap B=\varnothing,$$

那么：

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

这叫作加法原理。

若两个有限集相交，那么：

$$ |A\cup B| = |A|+|B|-|A\cap B|$$

分类计数

若一个有限集合 $S$ 被分成两两不相交的类别：

$$ S=A_1\cup A_2\cup\cdots\cup A_m,$$

则：

$$ |S| = \sum_{i=1}^{m}|A_i|$$

这种把对象分入互斥类别的方法叫作分类计数。

分类必须同时满足：

1. 不遗漏：每个对象至少进入一个类别；
2. 不重复：每个对象至多进入一个类别。

两者合起来就是：每个对象恰好进入一个类别

乘法原理

两步乘法原理

设第一步有 $m$ 种选择。

对第一步的每一种选择，第二步都恰好有 $n$ 种选择。

那么完整的两步结果共有 $m \times n$ 种

这叫作乘法原理。

它对应笛卡尔积：

$$ |A\times B| = |A||B|.$$

每个完整结果都是一个有序对：

$$ (a,b) \qquad a\in A,\ b\in B.$$

多步乘法原理

若一个过程有 $r$ 步，第 $i$ 步始终有 $n_i$ 种选择，那么完整结果数为：

$$ n_1n_2\cdots n_r$$

形式上：

$$ \left| A_1\times A_2\times\cdots\times A_r \right| = \prod_{i=1}^{r}|A_i|.$$

乘积记号：

$$ \prod_{i=1}^{r}c_i$$

表示：

$$ c_1c_2\cdots c_r.$$

排列

有序序列

一个长度为 $k$ 的有序序列写作：

$$ (x_1,x_2,\ldots,x_k).$$

位置不同通常表示不同序列，若$a\neq b$。：

$$ (a,b)\neq(b,a)$$

排列的定义

设有限集：

$$ X=\{x_1,\ldots,x_n\}.$$

把 $X$ 的全部元素放入 $n$ 个有顺序的位置，并且每个元素恰好使用一次，得到的有序序列叫作 $X$ 的一个排列。

等价地，一个排列可以看作双射：

$$ \sigma:[n]\to X$$

其中 $\sigma(i)$ 表示第 $i$ 个位置放入的元素。

$n$ 个不同元素排列

将 $n$ 个不同元素进行排列

第一个位置有 $n$ 种选择。

选定以后，第二个位置还剩 $n-1$ 种选择。

继续下去：

$$ n,\ n-1,\ n-2,\ldots,1.$$

由乘法原理：

$$ n! =n(n-1)\cdots2\cdot1$$

所以 $n$ 个不同元素的排列数是：

$$ n!$$

空集的排列

空集没有元素。

把空集的全部元素按顺序排列，只有一种结果：什么也不放。

它叫作空排列。

为了让空选择也有一个唯一结果，规定：

$$ 0!=1$$

部分排列

从 $n$ 个不同元素中选出 $k$ 个，并把它们放入有顺序的 $k$ 个位置，叫作一个 $k$ 项部分排列。

第一位有 $n$ 种选择，第二位有 $n-1$ 种，直到第 $k$ 位。

因此：

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

使用阶乘：

$$ P(n,k) = \frac{n!}{(n-k)!} \qquad 0\leq k\leq n.$$

这个乘积也叫作下降阶乘，记作：

$$ (n)_k = n(n-1)\cdots(n-k+1).$$

允许重复的有序选择

如果每个位置都可以从 $n$ 个元素中重新选择，并且允许同一元素多次出现，那么长度为 $k$ 的有序序列有 $n^k$
个。

多重集合

定义

普通集合只记录元素是否出现，不记录重复次数。

一个多重集合除了记录元素，还给每种元素规定一个非负整数重复次数。

这个次数叫作元素的重数。

例如单词：

$$ \text{LEVEL}$$

包含：

• $L$ 两次；
• $E$ 两次；
• $V$ 一次。

把这些字母看成多重集合，可以写成重数：

$$ m_L=2, \qquad m_E=2, \qquad m_V=1.$$

有重复元素的排列数

设总共有 $n$ 个位置，其中：

• 第一类元素重复 $m_1$ 次；
• 第二类元素重复 $m_2$ 次；
• $\cdots$
• 第 $r$ 类元素重复 $m_r$ 次；

并且：

$$ m_1+\cdots+m_r=n.$$

如果暂时给所有重复元素加上不同编号，会得到：

$$ n!$$

个排列。

但第一类元素内部的：

$$ m_1!$$

种交换不会改变可见结果；其他类别同理。

因此不同排列数为：

$$ \frac{n!}{m_1!m_2!\cdots m_r!}$$

例子：LEVEL

单词 LEVEL 的字符可以组成多少个单词呢？

LEVEL有 $5$ 个位置，重数为：

$$ 2,\ 2,\ 1.$$

不同排列数为：

$$ \frac{5!}{2!2!1!} = \frac{120}{4} = 30.$$

组合

定义

设 $X$ 是一个 $n$-元素有限集。

一个满足：

$$ S\subseteq X, \qquad |S|=k$$

的子集，叫作 $X$ 的一个 $k$-元素子集。

从 $X$ 中选择 $k$ 个元素且不区分选择顺序，叫作一个组合。

二项式系数

$n$-元素集合的 $k$-元素子集数（也称之为组合数），叫作二项式系数，记作：

$$ \binom nk$$

因此：

$$ \binom nk = \left| \{S\subseteq[n]\mid |S|=k\} \right|$$

二项式系数也写作

$$ C_n^k$$

组合公式

我们可以通过部分排列公式，推导出组合公式：

先选出 $k$ 个元素，再把它们排序，可以得到一个 $k$ 项部分排列。

每个 $k$-元素子集内部有：

$$ k!$$

种排列。

因此：

$$ P(n,k) = \binom nk k!$$

代入：

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

得到：

$$ \binom nk = \frac{n!}{k!(n-k)!} \qquad 0\leq k\leq n$$

边界值

从 $n$ 个元素中一个也不选，只有空集这一种选择：

$$ \binom n0=1$$

把全部 $n$ 个元素都选出，也只有一种：

$$ \binom nn=1$$

当 $k<0$ 或 $k>n$ 时，没有这样的子集。为了让递推公式书写方便，常约定：

$$ \binom nk=0$$

对称性

对 $S\subseteq X$，$S$ 在 $X$ 中的补集定义为：

$$ X\setminus S = \{x\in X\mid x\notin S\}.$$

选择一个 $k$-元素子集 $S$，等价于选择不被选中的补集 $X\setminus S$。

如果：

$$ |X|=n, \qquad |S|=k,$$

那么：

$$ |X\setminus S|=n-k.$$

映射：

$$ S\longmapsto X\setminus S$$

在 $k$-元素子集与 $(n-k)$-元素子集之间建立双射。

因此：

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

这不是阶乘公式的偶然对称，而是“选中谁”和“排除谁”描述同一件事。

排列与组合的判断

问自己：

交换两个被选对象的位置，结果是否改变？

如果改变，通常是排列：

$$ (a,b)\neq(b,a).$$

如果不改变，通常是组合：

$$ \{a,b\}=\{b,a\}.$$

Pascal 恒等式与二项式定理

Pascal 恒等式

对：

$$ 1\leq k\leq n-1,$$

有：

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

其物理含义为：

从 $n$ 个东西里选 $k$ 个，分成两类：包含某一个特定元素、不包含这个特定元素，两类相加就是全部选法

证明

固定一个 $n$-元素集合 $X$，再固定其中一个特殊元素 $x\in X$。

所有 $k$-元素子集可以分成两类：

1. 包含 $x$
2. 不包含 $x$

若子集包含 $x$，还需从剩余 $n-1$ 个元素中选出 $k-1$ 个：

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

若子集不包含 $x$，需从剩余 $n-1$ 个元素中选出 $k$ 个：

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

两类互不相交，所以由加法原理：

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

Pascal 三角形

从边界：

$$ \binom n0=\binom nn=1$$

开始，再反复使用 Pascal 恒等式，就得到三角形：

$$ \begin{array}{ccccccc} &&&1\\ &&1&&1\\ &1&&2&&1\\ 1&&3&&3&&1\\ &\cdots \end{array}$$

每个内部数字都是左上和右上两个数字之和。

二项式定理

由两个项组成的和：

$$ x+y$$

叫作一个二项式。

对自然数 $n$，二项式定理为：

$$ (x+y)^n = \sum_{k=0}^{n} \binom nk x^ky^{n-k}$$

证明

展开：

$$ (x+y)^n = \underbrace{(x+y)(x+y)\cdots(x+y)}_{n}$$

要得到项 $x^ky^{n-k}$

必须在 $n$ 个因子中恰好选择 $k$ 个取 $x$，其余取 $y$。

选择哪 $k$ 个因子取 $x$，共有 $\binom nk$ 种。

所以 $x^ky^{n-k}$ 的系数就是：

$$ \binom nk$$

行和

令：

$$ x=y=1,$$

则二项式定理给出：

$$ 2^n = \sum_{k=0}^{n}\binom nk.$$

组合解释是：

• 左边 $2^n$：每个元素选择“进入子集”或“不进入子集”；
• 右边：按子集大小 $k$ 分类。

隔板法

相同物品怎样分入不同容器

弱组合

weak composition，也称作弱合成

设 $n,r\in\mathbb N$，并且 $r\geq1$。

满足：

$$ x_1+x_2+\cdots+x_r=n$$

以及：

$$ x_i\in\mathbb N$$

的有序 $r$ 元组：

$$ (x_1,\ldots,x_r)$$

叫作 $n$ 的一个 $r$ 部分弱组合

“弱”表示允许：

$$ x_i=0.$$

这里的“组合/合成”强调把整数 $n$ 按顺序分成若干部分，不是上一节“选择 $k$-元素子集”的组合。

隔板法

允许盒子为空/隔板可以挨在一起

用 $n$ 个星号表示 $n$ 个相同物品：

* * * * *

要把它们分入 $r$ 个有标签容器

我们可以将思路转化为使用 $r-1$ 个隔板分开各容器

可放隔板的总位置数=星星数量 + 隔板数量，隔板数量=盒子数量-1

$$ n+r-1.$$

只需选择其中 $r-1$ 个位置放隔板，所以解的数量为：

$$ \binom{n+r-1}{r-1}$$

这叫作星与隔板法，也叫隔板法。

每个容器至少一个

若要求：

$$ x_i\geq1,$$

先给每个容器放入一个物品（盒子不为空）。

令：

$$ y_i=x_i-1\geq0.$$

则：

$$ y_1+\cdots+y_r=n-r.$$

因此正整数解的数量为：

$$ \binom{n-1}{r-1} \qquad n\geq r.$$

可重复选择的组合

从 $q$ 种对象中选取 $k$ 个，允许同一种对象被多次选取，并且不记录顺序。

令 $x_i$ 表示第 $i$ 种对象被选了多少次，则：

$$ x_1+\cdots+x_q=k, \qquad x_i\geq0.$$

所以可重复组合数为：

$$ \binom{q+k-1}{k}$$

这与允许重复的有序选择：

$$ q^k$$

不同，因为这里不记录选择顺序。

常见错误

该加时乘

若一个结果属于“类型 $A$ 或类型 $B$”，并且两类互斥，应使用：

$$ |A|+|B|.$$

只有一个完整结果必须同时完成第一步和第二步时，才使用乘法。

该乘时加

若每个完整结果都要选择：

• 一个目的地；
• 一个时间；
• 一个座位；

那么三个选择共同组成有序三元组，应使用乘法原理。

分类发生重叠

如果一个对象可能同时进入两个类别，直接相加会重复计算。

使用加法原理前必须检查：

$$ A_i\cap A_j=\varnothing, \qquad i\neq j.$$

把组合当排列

委员会：

$$ \{a,b,c\}$$

通常不区分谁先被选。

领奖台：

$$ (a,b,c)$$

通常区分第一、第二、第三。

选择了相同的人，不代表两个问题在数同一种对象。

忘记是否允许重复

长度为 $k$ 的字符序列允许重复字符时有：

$$ n^k$$

种；不允许重复时有：

$$ P(n,k)$$

种。

随意除掉“对称”

只有当每个最终对象都被重复计算相同次数时，才能除以统一因子。

所以除法之前必须证明：每个最终对象的重复次数相同

本章小结

核心定义

有限集与基数：

$$ A\leftrightarrow[n] \quad\Longrightarrow\quad |A|=n.$$

加法原理：

$$ A\cap B=\varnothing \quad\Longrightarrow\quad |A\cup B|=|A|+|B|.$$

乘法原理：

$$ |A\times B|=|A||B|.$$

部分排列：

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

组合：

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

多重集合排列：

$$ \frac{n!}{m_1!\cdots m_r!}.$$

Pascal 恒等式：

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

二项式定理：

$$ (x+y)^n = \sum_{k=0}^{n} \binom nkx^ky^{n-k}.$$

隔板法：

$$ x_1+\cdots+x_r=n, \qquad x_i\geq0 \quad\Longrightarrow\quad \binom{n+r-1}{r-1}.$$

判断计数模型的四个问题

遇到一个计数问题，先问：

1. 完整结果由哪些步骤组成？连续用乘法
2. 不同类别是否互斥？互斥用加法
3. 顺序改变是否产生新结果？记录顺序用排列，忽略顺序用组合
4. 同一种对象是否允许重复出现？相同对象分配用隔板法