离散数学（六）——排列组合与数列递推

一、排列与组合的基本公式

注 1.（记号约定）

这里略去排列数、组合数的定义，直接给出相关公式。排列数记为

𝑃_{𝑛}^{𝑟}

或

𝑃 (𝑛, 𝑟)

；组合数记为

𝐶_{𝑛}^{𝑟}

、

𝐶 (𝑛, 𝑟)

或

(\binom{𝑛}{𝑟})

。

1.排列数基本公式

(1)排列数计算式

𝑃 (𝑛, 𝑟) = \frac{𝑛!}{(𝑛 - 𝑟)!}

规定 $𝑃 (𝑛, 0) = 1$ ， $𝑟 > 𝑛$ 时 $𝑃 (𝑛, 𝑟) = 0$ 。当 $𝑟 = 𝑛$ 时有 $𝑃 (𝑛, 𝑛) = 𝑛!$ 。

2.组合数基本公式

(1)组合数计算式

𝐶 (𝑛, 𝑟) = \frac{𝑃 (𝑛, 𝑟)}{𝑃 (𝑟, 𝑟)} = \frac{𝑛!}{𝑟! (𝑛 - 𝑟)!}

规定 $𝐶 (𝑛, 0) = 𝐶 (𝑛, 𝑛) = 𝐶 (0, 0) = 1$ ， $𝑟 > 𝑛$ 时 $𝐶 (𝑛, 𝑟) = 0$ 。

(2)组合数对称式

𝐶 (𝑛, 𝑟) = 𝐶 (𝑛, 𝑛 - 𝑟)

(3)恒等式

(𝑟 + 1) \cdot 𝐶_{𝑛}^{𝑟 + 1} = (𝑛 - 𝑟) \cdot 𝐶_{𝑛}^{𝑟}

(4)帕斯卡等式

𝐶_{𝑛}^{𝑘} = 𝐶_{𝑛 - 1}^{𝑘} + 𝐶_{𝑛 - 1}^{𝑘 - 1}

帕斯卡等式是组合数的一种递推式。实际是在说，杨辉三角中的某一个数等于其左上与右上之数之和。

(5)递推式

将上面第(3)恒等式变形即可得到：

𝑟 \cdot 𝐶_{𝑛}^{𝑟} = (𝑛 - 𝑟 + 1) \cdot 𝐶_{𝑛}^{𝑟 - 1}

𝑟 \cdot 𝐶_{𝑛}^{𝑟} = 𝑛 \cdot 𝐶_{𝑛 - 1}^{𝑟 - 1}

(6)乘积化简式

𝐶_{𝑛}^{𝑚} \cdot 𝐶_{𝑚}^{𝑘} = 𝐶_{𝑛}^{𝑘} \cdot 𝐶_{𝑛 - 𝑘}^{𝑚 - 𝑘}

这要求 $𝑘 \leq 𝑚 \leq 𝑛$ 。

(7)上下标求和式

\sum_{𝑘 = 0}^{𝑛} 𝐶_{𝑚 + 𝑘}^{𝑘} = 𝐶_{𝑚}^{0} + 𝐶_{𝑚 + 1}^{1} + \dots + 𝐶_{𝑚 + 𝑛}^{𝑛} = 𝐶_{𝑛 + 𝑚 + 1}^{𝑛}

\sum_{𝑘 = 0}^{𝑛} 𝐶_{𝑘}^{𝑚} = 𝐶_{0}^{𝑚} + 𝐶_{1}^{𝑚} + \dots + 𝐶_{𝑛}^{𝑚} = 𝐶_{𝑛 + 1}^{𝑚 + 1}

(8)朱世杰-范德蒙等式

\sum_{𝑘 = 0}^{𝑛} 𝐶_{𝑚}^{𝑛 - 𝑘} \cdot 𝐶_{𝑟}^{𝑘} = 𝐶_{𝑚 + 𝑟}^{𝑛}

这要求 $𝑟 \leq 𝑚, 𝑟 \leq 𝑛$ 。

(9)二项式定理及其衍生式

定理 1.（二项式定理）

{(𝑥 + 𝑦)}^{𝑛} = \sum_{𝑖 = 0}^{𝑛} 𝐶_{𝑛}^{𝑖} 𝑥^{𝑖} 𝑦^{𝑛 - 𝑖}

令 $𝑦 = 1$ ：

{(𝑥 + 1)}^{𝑛} = \sum_{𝑖 = 0}^{𝑛} 𝐶_{𝑛}^{𝑖} 𝑥^{𝑖} = 𝐶_{𝑛}^{0} + 𝐶_{𝑛}^{1} 𝑥 + \dots + 𝐶_{𝑛}^{𝑛} 𝑥^{𝑛}

令 $𝑥 = 𝑦 = 1$ ：

\sum_{𝑖 = 0}^{𝑛} 𝐶_{𝑛}^{𝑖} = 𝐶_{𝑛}^{0} + 𝐶_{𝑛}^{1} + \dots + 𝐶_{𝑛}^{𝑛} = 2^{𝑛}

令 $𝑥 = - 1, 𝑦 = 1$ ：

\sum_{𝑖 = 0}^{𝑛} {(- 1)}^{𝑖} 𝐶_{𝑛}^{𝑖} = 𝐶_{𝑛}^{0} - 𝐶_{𝑛}^{1} + \dots + {(- 1)}^{𝑛} 𝐶_{𝑛}^{𝑛} = 0

因此：

𝐶_{𝑛}^{0} + 𝐶_{𝑛}^{2} + 𝐶_{𝑛}^{4} + \dots = 𝐶_{𝑛}^{1} + 𝐶_{𝑛}^{3} + 𝐶_{𝑛}^{5} + \dots = 2^{𝑛 - 1}

对 $𝑥 = 𝑥, 𝑦 = 1$ 情况两边求导：

𝑛 {(𝑥 + 1)}^{𝑛 - 1} = \sum_{𝑖 = 0}^{𝑛} 𝑖 𝐶_{𝑛}^{𝑖} 𝑥^{𝑖 - 1}

上式中令 $𝑥 = 1$ ：

\sum_{𝑖 = 0}^{𝑛} 𝑖 𝐶_{𝑛}^{𝑖} = 𝐶_{𝑛}^{1} + 2 𝐶_{𝑛}^{2} + \dots + 𝑛 𝐶_{𝑛}^{𝑛} = 𝑛 \cdot 2^{𝑛 - 1}

二、一些经典问题

1.具有重复度的n类物体的r排列

假如有 $𝑛$ 类物体，每类分别有 $𝑚_{1}, 𝑚_{2}, \dots, 𝑚_{𝑛}$ 个，令 $𝑟 = 𝑚_{1} + 𝑚_{2} + \dots + 𝑚_{𝑛}$ ，那么允许重复的 $𝑟$ 排列数是：

𝐶_{𝑟}^{𝑚_{1}} \cdot 𝐶_{𝑟 - 𝑚_{1}}^{𝑚_{2}} \cdot \dots \cdot 𝐶_{𝑟 - 𝑚_{1} - 𝑚_{2} - \dots - 𝑚_{𝑛 - 1}}^{𝑚_{𝑛}} = \frac{𝑟!}{𝑚_{1!} 𝑚_{2!} \dots 𝑚_{𝑛!}}

一个典型的问法是：字母 $𝐴, 𝐵, 𝐶$ 分别有 $𝑥, 𝑦, 𝑧$ 个，问能组成长度为 $𝑥 + 𝑦 + 𝑧$ 的字符串多少个？

2.不限上限的不定方程解的数量

问： $𝑥_{1} + 𝑥_{2} + \dots + 𝑥_{𝑛} = 𝑠$ 的非负整数解的数量是多少？

想象一列总计有 $𝑠$ 个的物品。这个方程相当于：切 $𝑛 - 1$ 刀、将其分为 $𝑛$ 份，总共有多少种切法？其中允许某一处重复切。也就相当于，一个长度为 $𝑠$ 的全 $1$ 字符串，向其中插入 $𝑛 - 1$ 个 $0$ ，问有多少种插法？也就相当于，一个长度为 $𝑠 + (𝑛 - 1)$ 的字符串，其中有 $𝑛$ 个 $0$ ，问这样的字符串有几种？这就是在 $𝑠 + 𝑛 - 1$ 种物品中选出 $𝑛$ 种的问题！因此答案就是：

𝐶_{𝑠 + 𝑛 - 1}^{𝑛}

3.限定上限的不定方程解的数量

问： $𝑥_{1} + 𝑥_{2} + \dots + 𝑥_{𝑛} = 𝑠$ 的非负整数解的数量是多少？其中 $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}$ 具有上限 $𝑚_{1}, 𝑚_{2}, \dots, 𝑚_{𝑛}$ 。

这个问题实际是将问题分割并转化为几个不限上限的不定方程解的数量问题，然后利用容斥原理来解。

4.字符串的下一字典序

假设字符串 $𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑛}$ 。将字符串从后往前遍历，寻找第一个破坏从前往后递减规律的字符，替换为已遍历字符中大于此字符但最小的那个字符，再将剩余字符按递增顺序排列。

例如给出字符串 $12348765$ 的下一字典序。从后往前遍历到 $4$ ， $4$ 恰好破坏了 $8765$ 的递减，因此将 $4$ 替换为 $8765$ 中大于 $4$ 的且最小的 $5$ ，剩下的四个数按递增顺序排列为 $4678$ ，因此 $12348765$ 的下一字典序就是 $12354678$ 。

三、数列线性递推

数列的通项公式是指数列的第 $𝑛$ 项可以由一个关于 $𝑛$ 的表达式直接给出，即 $𝑎_{𝑛} = 𝑓 (𝑛)$ 。而数列的递推式，是指数列的第 $𝑛$ 项可以利用前面的项给出：

𝑎_{𝑛} = 𝑓 (𝑎_{𝑖_{1}}, 𝑎_{𝑖_{2}}, \dots, 𝑎_{𝑖_{𝑘}}), 0 < 𝑖_{𝑗} < 𝑛

由递推式给出的数列称为递推式的解。如果这个解是通项公式，那么称为封闭公式解。这一节主要讨论如何从常系数数列线性递推得到封闭公式解，而所谓的常系数 $𝑘$ 阶线性递推关系式是指：

𝑎_{𝑛} = 𝑐_{1} 𝑎_{𝑛 - 1} + 𝑐_{2} 𝑎_{𝑛 - 2} + \dots + 𝑐_{𝑘} 𝑎_{𝑛 - 𝑘} + 𝐹 (𝑛)

1.齐次递推

若 $𝐹 (𝑛) = 0$ ，那么上述的线性递推式是齐次的，称为常系数 $𝑘$ 阶线性齐次递推关系式。否则是非齐次的。此时上式写为：

𝑎_{𝑛} = 𝑐_{1} 𝑎_{𝑛 - 1} + 𝑐_{2} 𝑎_{𝑛 - 2} + \dots + 𝑐_{𝑘} 𝑎_{𝑛 - 𝑘}

它对应一个特征方程：

𝑥^{𝑘} = 𝑐_{1} 𝑥^{𝑘 - 1} + 𝑐_{2} 𝑥^{𝑘 - 2} + \dots + 𝑐_{𝑘}

它的解有以下情况：

(1) $𝑘$ 个互不相同的根 $𝑟_{1}, 𝑟_{2}, \dots, 𝑟_{𝑘}$

𝑎_{𝑛} = 𝛽_{1} 𝑟_{1}^{𝑛} + 𝛽_{2} 𝑟_{2}^{𝑛} + \dots + 𝛽_{𝑘} 𝑟_{𝑘}^{𝑛}

是递推式的解，其中 $𝛽_{1}, 𝛽_{2}, \dots, 𝛽_{𝑘}$ 是待定系数。

(2) $𝑡$ 个互不相同的根 $𝑟_{1}, 𝑟_{2}, \dots, 𝑟_{𝑡}$ ，每个根的重数是 $𝑚_{1}, 𝑚_{2}, \dots, 𝑚_{𝑡}$

首先显然 $𝑚_{1} + 𝑚_{2} + \dots + 𝑚_{𝑡} = 𝑘$ 。那么递推式的解是：

\begin{aligned} 𝑎_{𝑛} = & (𝛽_{1, 0} + 𝛽_{1, 1} \cdot 𝑛 + \dots + 𝛽_{1, 𝑚_{1}} \cdot 𝑛^{𝑚_{1} - 1}) 𝑟_{1}^{𝑛} \\ + (𝛽_{2, 0} + 𝛽_{2, 1} \cdot 𝑛 + \dots + 𝛽_{2, 𝑚_{2}} \cdot 𝑛^{𝑚_{2} - 1}) 𝑟_{2}^{𝑛} + \dots \\ + (𝛽_{𝑡, 0} + 𝛽_{𝑡, 1} \cdot 𝑛 + \dots + 𝛽_{𝑡, 𝑚_{𝑡}} \cdot 𝑛^{𝑚_{𝑡} - 1}) 𝑟_{𝑡}^{𝑛} \end{aligned}

其中 $𝛽_{𝑖, 𝑗} (𝑖 = 1 \sim 𝑡, 𝑗 = 1 \sim 𝑚_{𝑖})$ 共计 $𝑘$ 个待定系数。

2.非齐次递推

此时：

𝑎_{𝑛} = 𝑐_{1} 𝑎_{𝑛 - 1} + 𝑐_{2} 𝑎_{𝑛 - 2} + \dots + 𝑐_{𝑘} 𝑎_{𝑛 - 𝑘} + 𝐹 (𝑛)

而将剔除掉 $𝐹 (𝑛)$ 的递推式：

𝑎_{𝑛} = 𝑐_{1} 𝑎_{𝑛 - 1} + 𝑐_{2} 𝑎_{𝑛 - 2} + \dots + 𝑐_{𝑘} 𝑎_{𝑛 - 𝑘}

称为它的伴随齐次递推关系式。我们只对 $𝐹 (𝑛)$ 具有如下形式：

𝐹 (𝑛) = (𝑏_{𝑡} \cdot 𝑛^{𝑡} + 𝑏_{𝑡 - 1} \cdot 𝑛^{𝑡 - 1} + \dots + 𝑏_{1} \cdot 𝑛 + 𝑏_{0}) 𝑠^{𝑛}

的非齐次递推式讨论。记由伴随齐次式得到的解为 ${𝑎_{𝑛}^{(ℎ)}}$ ，而非齐次递推式的一个特解为 ${𝑎_{𝑛}^{(𝑝)}}$ ，那么非齐次递推式的一个解为 ${𝑎_{𝑛}^{(𝑝)} + 𝑎_{𝑛}^{(ℎ)}}$ 。

因此首先解伴随齐次式，得到特征方程的根及其未待定系数的封闭公式解 ${𝑎_{𝑛}^{(ℎ)}}$ 。之后针对 $𝐹 (𝑛)$ 中的参数讨论：

(1)若 $𝑠$ 不是伴随齐次式特征方程的根

那么一个特解的形式是：

𝑎_{𝑛}^{(𝑝)} = (𝑝_{𝑡} \cdot 𝑛^{𝑡} + 𝑝_{𝑡 - 1} \cdot 𝑛^{𝑡 - 1} + \dots + 𝑝_{1} \cdot 𝑛 + 𝑝_{0}) 𝑠^{𝑛}

(2)若 $𝑠$ 是伴随齐次式特征方程的一个 $𝑚$ 重根

那么一个特解的形式是：

𝑎_{𝑛}^{(𝑝)} = 𝑛^{𝑚} (𝑝_{𝑡} \cdot 𝑛^{𝑡} + 𝑝_{𝑡 - 1} \cdot 𝑛^{𝑡 - 1} + \dots + 𝑝_{1} \cdot 𝑛 + 𝑝_{0}) 𝑠^{𝑛}

这里 $𝑝_{0} \sim 𝑝_{𝑡}$ 是待定系数。将特解直接代入原递推式，可以对比指数得到待定系数。这样就得到确定了待定系数的特解 ${𝑎_{𝑛}^{(𝑝)}}$ 。之后再相加得到 ${𝑎_{𝑛}^{(𝑝)} + 𝑎_{𝑛}^{(ℎ)}}$ ，由初始条件确定 ${𝑎_{𝑛}^{(ℎ)}}$ 中未确定的系数，即得到原非齐次递推式的封闭公式解。