组合数学中小球放盒子问题的通解

高中数学·组合数学·错排问题变种

问题引入

在高中数学中，我们常遇到类似的问题：

例题1：3个小球和3个盒子，编号均相同。要求每个盒子放一个小球，且所有小球都不在自己的盒子。有多少种放法？
例题2：5个小球和5个盒子，编号均相同。要求恰好1个小球在自己的盒子。有多少种放法？

这类问题看似不同，但其实都可以归结为一个通用模型：已知 $n$ 个小球和 $n$ 个盒子，编号相同，要求恰好 $m$ 个小球在自己的盒子中，求放法总数。本文将从基础到高阶，逐步推导出通解公式。

基础概念铺垫

1. 排列与组合

全排列： $n$ 个不同元素的排列数为 $n!$ 。
组合数：从 $n$ 个元素中选 $m$ 个的组合数为 $(\binom{n}{m}) = \frac{n!}{m! (n - m)!}$ 。

2. 错排问题（Derangement）

定义：将 $n$ 个元素重新排列，使得没有一个元素在原位置。这样的排列数记为 $D (n)$ 。
公式： $D (n) = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \dots + (- 1)^{n} \frac{1}{n!})$ 或者更简单的公式： $D (n) = round (\frac{n!}{e}) (n \geq 1)$ （其中 round 表示四舍五入， $e$ 是自然对数的底）

图论建模：小球放盒子的环结构

将问题抽象为图：

每个小球和盒子编号为 $1 \sim n$ 。
若小球 $a$ 放入盒子 $b$ ，则画一条有向边 $a \to b$ 。
最终的图由多个环组成（例如：1→2→3→1 形成 3 元环）。

关键结论：

每个小球必须放入一个盒子，每个盒子必须有一个小球，因此图中所有边构成若干不重叠的循环。
自环（如1→1）表示小球放入同编号盒子，即“固定点”。

拆分与分类：如何计算不同情况

我们需要统计所有满足“恰好 $m$ 个自环”的循环结构总数。这可以分解为两个步骤：

步骤1：选择自环

从 $n$ 个小球中选择 $m$ 个作为自环，共有 $(\binom{n}{m})$ 种方法。

步骤2：计算剩余小球的错排

剩余 $n - m$ 个小球必须形成无自环的循环结构，即错排问题，共有 $D (n - m)$ 种方法。

通解公式：

总方法数为：

(\binom{n}{m}) \cdot D (n - m)

实例验证

例题1：n=3, m=0

选择0个自环： $(\binom{3}{0}) = 1$ 。
剩余3个错排： $D (3) = 2$ 。
总放法数： $1 \times 2 = 2$ 。

例题2：n=5, m=1

选择1个自环： $(\binom{5}{1}) = 5$ 。
剩余4个错排： $D (4) = 9$ 。
总放法数： $5 \times 9 = 45$ 。

扩展案例：n=8, m=1

选择1个自环： $(\binom{8}{1}) = 8$ 。
剩余7个错排： $D (7) = 1854$ 。
总放法数： $8 \times 1854 = 14832$ 。

错排的计算逻辑与近似公式推导

1. 错排的基本概念

错排（Derangement）是指将 $n$ 个元素重新排列，使得没有一个元素出现在其原始位置的排列方式。例如，对于 $n = 3$ ，所有排列为：

\begin{aligned} 123 (无错排) \\ 132 (1在原位置) \\ 213 (3在原位置) \\ 231 (错排) \\ 312 (错排) \\ 321 (2在原位置) \end{aligned}

其中，只有 $231$ 和 $312$ 是错排，因此 $D (3) = 2$ 。

2. 递推公式的逻辑

递推公式1：

D (n) = (n - 1) (D (n - 1) + D (n - 2))

推导逻辑：

固定一个元素：考虑第 $n$ 个元素的位置。假设第 $n$ 个元素被放入位置 $k$ （ $k \neq n$ ）。此时有 $n - 1$ 种选择（ $k = 1, 2, \dots, n - 1$ ）。
分两种情况讨论：
- 情况1：位置 $k$ 的元素被放入位置 $n$ 。此时，第 $k$ 个元素和第 $n$ 个元素形成一个2元循环（如 $n \to k \to n$ ）。剩下的 $n - 2$ 个元素需要错排，共有 $D (n - 2)$ 种方法。
- 情况2：位置 $k$ 的元素不被放入位置 $n$ 。此时，第 $k$ 个元素和第 $n$ 个元素形成一个“干扰”，剩下的 $n - 1$ 个元素（包括第 $k$ 个元素）需要错排，共有 $D (n - 1)$ 种方法。
总和：对于每个 $k$ ，两种情况的总和为 $D (n - 1) + D (n - 2)$ 。由于有 $n - 1$ 个 $k$ ，最终得到： $D (n) = (n - 1) (D (n - 1) + D (n - 2))$

验证示例：

$D (1) = 0$
$D (2) = 1$
$D (3) = (3 - 1) (D (2) + D (1)) = 2 \times (1 + 0) = 2$
$D (4) = (4 - 1) (D (3) + D (2)) = 3 \times (2 + 1) = 9$

递推公式2：

D (n) = n D (n - 1) + (- 1)^{n}

推导逻辑：

从全排列出发：全排列数为 $n!$ ，但我们需要排除所有有固定点的排列。
容斥原理：使用容斥原理计算错排数： $D (n) = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!})$ 这个公式可以通过数学归纳法或生成函数推导出递推式。
递推关系：将容斥公式展开后，发现满足： $D (n) = n D (n - 1) + (- 1)^{n}$ 例如，当 $n = 1$ 时， $D (1) = 1 \times D (0) + (- 1)^{1} = 1 \times 1 - 1 = 0$ ，符合定义。

验证示例：

$D (1) = 0$
$D (2) = 2 D (1) + (- 1)^{2} = 0 + 1 = 1$
$D (3) = 3 D (2) + (- 1)^{3} = 3 \times 1 - 1 = 2$
$D (4) = 4 D (3) + (- 1)^{4} = 4 \times 2 + 1 = 9$

3. 近似公式的推导

近似公式：

D (n) \approx \frac{n!}{e}

推导逻辑：

容斥公式的展开：错排数的精确表达式为： $D (n) = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!})$
泰勒展开：自然指数 $e^{x}$ 的泰勒展开为： $e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots$ 当 $x = - 1$ 时： $e^{- 1} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots$
截断误差：当 $n \to \infty$ 时，容斥公式中的项数趋于无穷，因此： $D (n) \approx n! \cdot e^{- 1}$ 即： $D (n) \approx \frac{n!}{e}$
四舍五入修正：由于截断误差的存在，实际计算中可以使用四舍五入： $D (n) = round (\frac{n!}{e})$

验证示例：

$D (5) = 44$ ，计算： $\frac{5!}{e} \approx \frac{120}{2.71828} \approx 44.15$ ，四舍五入后为 44。
$D (6) = 265$ ，计算： $\frac{720}{2.71828} \approx 264.87$ ，四舍五入后为 265。

4. 总结与比较

方法	公式	优点	局限
递推法1	$D (n) = (n - 1) (D (n - 1) + D (n - 2))$	直观，适合记忆	需要知道 $D (0) = 1$ ， $D (1) = 0$
递推法2	$D (n) = n D (n - 1) + (- 1)^{n}$	简洁，适合数学归纳	需要知道 $D (0) = 1$
近似公式	$D (n) \approx \frac{n!}{e}$	计算速度快	适用于 $n \geq 1$ ，可能有四舍五入的精度问题

5. 实际应用示例

问题：计算 $D (10)$ 。

方法1：使用递推公式1

$D (1) = 0$
$D (2) = 1$
$D (3) = 2$
$D (4) = 9$
$D (5) = 44$
$D (6) = 265$
$D (7) = 1854$
$D (8) = 14833$
$D (9) = 133496$
$D (10) = 9 \times (133496 + 14833) = 9 \times 148329 = 1334961$

方法2：使用近似公式

$\frac{10!}{e} \approx 1334960.916$ ，四舍五入后为 1334961。

6. 结论

递推公式是计算错排数的基础工具，尤其适合编程实现。
近似公式在 $n$ 较大时非常高效，但需注意四舍五入修正。
数学归纳与容斥原理是推导这些公式的理论基础，理解其逻辑有助于灵活应用。

总结

通过图论建模和拆分思想，我们发现：

所有小球放盒子的问题最终可转化为“选择自环+错排”的组合问题。
通解公式 $(\binom{n}{m}) \cdot D (n - m)$ 简洁且普适，适用于任意 $n$ 和 $m$ 。

附录：常见错排数值表

$n$	$D (n)$
0	1
1	0
2	1
3	2
4	9
5	44
6	265
7	1854
8	14833

写在最后

组合数学的魅力在于将复杂问题抽象为简单模型。通过理解“循环结构”和“错排问题”，我们可以快速解决看似复杂的排列组合题。希望这篇文章能帮助你建立对这类问题的系统性思考！

组合数学中小球放盒子问题的通解 ​

问题引入 ​

基础概念铺垫 ​

1. 排列与组合 ​

2. 错排问题（Derangement） ​

图论建模：小球放盒子的环结构 ​

拆分与分类：如何计算不同情况 ​

步骤1：选择自环 ​

步骤2：计算剩余小球的错排 ​

通解公式： ​

实例验证 ​

例题1：n=3, m=0 ​

例题2：n=5, m=1 ​

扩展案例：n=8, m=1 ​

错排的计算逻辑与近似公式推导 ​

1. 错排的基本概念 ​

2. 递推公式的逻辑 ​

3. 近似公式的推导 ​

4. 总结与比较 ​

5. 实际应用示例 ​

问题：计算 D(10)。 ​

6. 结论 ​

总结 ​

附录：常见错排数值表 ​

写在最后 ​

组合数学中小球放盒子问题的通解

问题引入

基础概念铺垫

1. 排列与组合

2. 错排问题（Derangement）

图论建模：小球放盒子的环结构

拆分与分类：如何计算不同情况

步骤1：选择自环

步骤2：计算剩余小球的错排

通解公式：

实例验证

例题1：n=3, m=0

例题2：n=5, m=1

扩展案例：n=8, m=1

错排的计算逻辑与近似公式推导

1. 错排的基本概念

2. 递推公式的逻辑

3. 近似公式的推导

4. 总结与比较

5. 实际应用示例

问题：计算 $D (10)$ 。

6. 结论

总结

附录：常见错排数值表

写在最后