球盒模型

发表于 2018-10-15 更新于 2021-05-07 分类于 ACM ，学习笔记，数学阅读次数： 3 本文字数： 4.3k 阅读时长 ≈ 4 分钟

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

介绍

球盒模型指的是把球放入盒子里的题目模型（强行解释）

分为盒子同或不同，球同或不同，盒子允许空或不空，所以一共八种问题

结论

不妨假设n个球，m个盒子

盒异，球同，盒子允许空 $C_{m + n - 1}^{m - 1}$

盒异，球同，盒不允许空 $C_{n - 1}^{m - 1}$

盒同，球同，盒子允许空 $\begin{array}{r} \prod_{j = 1}^{m} \frac{1}{1 - x^{j}} \end{array}$ 中的 $x^{n}$ 系数

盒同，球同，盒不允许空 $\begin{array}{r} x^{m} \prod_{j = 1}^{m} \frac{1}{1 - x^{j}} \end{array}$ 中 $x^{n}$ 的系数

盒异，球异，盒子允许空 $m^{n}$

盒异，球异，盒不允许空 $\begin{array}{r} \sum_{k = 0}^{m} (C_{m}^{k} (- 1)^{m - k} k^{n}) \end{array}$

盒同，球异，盒子允许空 $\begin{array}{r} \sum_{i = 0}^{m} \sum_{k = 0}^{i} \frac{C_{i}^{k} (- 1)^{i - k} k^{n}}{i!} \end{array}$

盒同，球异，盒不允许空 $\begin{array}{r} \sum_{k = 0}^{m} \frac{C_{m}^{k} (- 1)^{m - k} k^{n}}{m!} \end{array}$

证明

盒异，球同，盒子允许空

做法1

考虑母函数，我们用指数代表球的个数，显然每个盒子可以放0个，1个，2个，3个，等等，一共m个盒子，则这些多项式直接乘起来即可，则定义母函数 $f (x) = (\sum_{i = 0}^{\infty} x^{i})^{m} = (\frac{1}{1 - x})^{m} = (1 - x)^{- m}$

很明显，其中的 $x^{n}$ 的系数就是答案。

根据二项式定理，我们考虑 $(- x)^{n}$ 这一项，他是
$\begin{aligned} C_{- m}^{n} (- x)^{n} \\ = \frac{\prod_{k = - m - n + 1}^{- m} k}{n!} (- x)^{n} \\ = \frac{\prod_{k = m}^{m + n - 1} k}{n!} x^{n} \\ = C_{m + n - 1}^{m - 1} x^{n} \end{aligned}$

如果大家认为这个解释很牵强，那我们对 $f (x)$ 进行泰勒展开，根据泰勒公式 $f (𝑥) = \sum_{i = 0}^{\infty} \frac{𝑓^{(i)} (x_{0})}{i!} (𝑥 - 𝑥_{0})^{i}$

我们先对 $f (x)$ 进行求导 $\begin{aligned} f^{'} (x) = - m \cdot (1 - x)^{m - 1} \cdot (- 1) \\ f^{″} (x) = - m \cdot (- m - 1) \cdot (1 - x)^{m - 2} \cdot (- 1)^{2} \\ f^{‴} (x) = - m \cdot (- m - 1) \cdot (- m - 2) \cdot (1 - x)^{m - 3} \cdot (- 1)^{3} \\ . . . \\ f^{(n)} (x) = (\prod_{i = 0}^{n - 1} (- m - i)) \cdot (1 - x)^{m - n} \cdot (- 1)^{n} \end{aligned}$ 我们取出 $f (x)$ 在 $x_{0} = 0$ 的泰勒展开中的n次方项 $\begin{aligned} \frac{(\prod_{j = 0}^{n - 1} (- m - i)) \cdot (1 - 0)^{m - n}}{n!} (𝑥 - 0)^{𝑛} \cdot (- 1)^{n} \\ = \frac{\prod_{j = 0}^{n - 1} (m + i)}{n!} 𝑥^{𝑛} \\ = \frac{\frac{(m + n - 1)!}{(m - 1)!}}{n!} 𝑥^{𝑛} \\ = C_{m + n - 1}^{m - 1} x^{n} \end{aligned}$

做法2

我们可以假设一共有n+m个球，然后每个盒子至少放一个球，可以证明这个问题与当前问题等价

盒异，球同，盒不允许空

考虑隔板，n个球一共n-1个间隙，向其中置入m-1个隔板，形成m个段，每一段放入一个盒子即可。即 $C_{n - 1}^{m - 1}$

盒同，球同，盒子允许空

由于盒子相同，我们不妨设这m个盒子中球的大小分别是 $a_{1} a_{2} . . . a_{m}$

更一般的，由于盒子相同，所以 $a$ 的顺序不影响结果。所以我们让其单增。设 $b_{i} = a_{i} - a_{i - 1} \geq 0 且 b_{1} = a_{1}$

则 $a_{i} = \sum_{j = 1}^{i} b_{j}$

则 $a_{1} + a_{2} + . . . + a_{m} = n$ 可以写作 $m \cdot b_{1} + (m - 1) \cdot b_{2} + (m - 2) \cdot b_{3} + . . . + b_{m} = m$

这里b的唯一约束仅仅只是非负整数。于是构造生成函数, 首先是 $b_{1}$ ,他可以是 $0, 1, 2. . .$ , 则它对应的多项式就是 $(x^{m})^{0} + (x^{m})^{1} + (x^{m})^{2} + . . .$ , 然后是 $b_{2}$ ，他对应是 $(x^{m - 1})^{0} + (x^{m - 1})^{1} + (x^{m - 1})^{2} + . . .$ ，然后乘起来，得到了 $\begin{aligned} f (x) \\ = ((x^{m})^{0} + (x^{m})^{1} + (x^{m})^{2} + . . .) ((x^{m - 1})^{0} + (x^{m - 1})^{1} + (x^{m - 1})^{2} + . . .) . . . \\ = \frac{1}{1 - x^{m}} \frac{1}{1 - x^{m - 1}} \frac{1}{1 - x^{m - 2}} . . . \frac{1}{1 - x} \\ = \prod_{j = 1}^{m} \frac{1}{1 - x^{j}} \end{aligned}$

盒同，球同，盒子不允许空

显然对于上一种情况的 $b_{1}$ ，他的约束从非负变成了恒正。所以生成函数第一个变成了 $(x^{m})^{1} + (x^{m})^{2} + . . .$

于是 $\begin{aligned} f (x) \\ = ((x^{m})^{1} + (x^{m})^{2} + . . .) ((x^{m - 1})^{0} + (x^{m - 1})^{1} + (x^{m - 1})^{2} + . . .) . . . \\ = \frac{x^{m}}{1 - x^{m}} \frac{1}{1 - x^{m - 1}} \frac{1}{1 - x^{m - 2}} . . . \frac{1}{1 - x} \\ = x^{m} \prod_{j = 1}^{m} \frac{1}{1 - x^{j}} \end{aligned}$

盒异，球异，盒子允许空

每个球都有m中选择，即放入任何一个盒子。所以答案是 $m^{n}$

盒异，球异，盒子不允许空

不妨设第一个盒子有 $a_{1}$ 个球，第二个有 $a_{2}$ 个球，后面同理，得到了一个a序列，考虑母函数 $f (x) = (x^{1} + x^{2} + . . .)^{m}$ ，这个函数体现了盒子非空、盒异，但是没有体现出球异。实际上，如果要体现球异，首先要乘以全排 $n!$ ，其次由于多个球放入了一个盒子，这里也要去全排，考虑序列a的放置方法，最终答案为 $n! \frac{1}{a_{1}!} \frac{1}{a_{2}!} \frac{1}{a_{3}!} . . .$ 体现到母函数上就是 $\begin{aligned} f (x) \\ = n! \cdot (\frac{x^{1}}{1!} + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + . . .)^{m} \\ = n! \cdot (e^{x} - 1)^{m} \\ = n! \cdot \sum_{k = 0}^{m} (C_{m}^{k} (- 1)^{m - k} (e^{x})^{k}) \\ = n! \cdot \sum_{k = 0}^{m} (C_{m}^{k} (- 1)^{m - k} (1 + \frac{(k x)^{1}}{1!} + \frac{(k x)^{2}}{2!} + \frac{(k x)^{3}}{3!} + . . .)) \end{aligned}$ 考虑 $x^{n}$ 项 $\begin{aligned} n! \cdot \sum_{k = 0}^{m} (C_{m}^{k} (- 1)^{m - k} \frac{(k x)^{n}}{n!}) \\ = (\sum_{k = 0}^{m} C_{m}^{k} \cdot (- 1)^{m - k} \cdot k^{n}) \cdot x^{n} \end{aligned}$

盒同，球异，盒子允许空

根据下一问枚举空盒子个数 $i$ $\begin{array}{r} \sum_{i = 0}^{m} \sum_{k = 0}^{i} \frac{(C_{i}^{k} (- 1)^{i - k} k^{n})}{i!} \end{array}$

盒同，球异，盒不允许空

相当于盒异，球异，盒不允许空去全排。即除以 $m!$

读者在这里可以花大部分时间想想为什么前面不能使用这种方式来推导。

第二类斯特林数

即盒同，球异，盒不允许空的解

我们回忆一下，这个解是 $\begin{array}{r} \sum_{k = 0}^{m} \frac{(C_{m}^{k} (- 1)^{m - k} k^{n})}{m!} \end{array}$

可以直接定义斯特林数 $S (n, m) = {_{m}^{n}} = \begin{array}{r} \sum_{k = 0}^{m} \frac{(C_{m}^{k} (- 1)^{m - k} k^{n})}{m!} \end{array}$

第二类斯特林数递推

$S (n, m) = S (n - 1, m - 1) + S (n - 1, m) \cdot m$

计算斯特林数的某一整行

即一次性计算 $S (n, 0), S (n, 1), S (n, 2) . . .$

我们对这个S的通项公式稍微变形,分离变量,然后就可以卷积运算了 $\begin{aligned} \sum_{k = 0}^{m} \frac{C_{m}^{k} (- 1)^{m - k} k^{n}}{m!} \\ = \sum_{k = 0}^{m} \frac{(- 1)^{m - k} k^{n}}{k! (m - k)!} \\ = \sum_{k = 0}^{m} \frac{(- 1)^{m - k}}{(m - k)!} \frac{k^{n}}{k!} \end{aligned}$