组合数学[1]——球放入盒子的方案数

近日观室友做面试题有感, 恰好遇到了球装盒子的问题, 顺手整理一波.

\(n\) 个球放入 \(m\) 个盒子, 共有多少种不同的方案?

球	盒	允许空	方案数
不同	不同	是	\(m^n\)
不同	不同	否	\(m!\cdot S(n,m)\)
不同	相同	是	\(\sum\limits_{k=0}^m S(n,k)\)
不同	相同	否	\(S(n,m)\)
相同	不同	是	\(\binom{n+m-1}{m-1}\)
相同	不同	否	\(\binom{n-1}{m-1}\)
相同	相同	是	\(dp(n,m)\)
相同	相同	否	\(dp(n-m,m)\)

球不同

盒子不同

不允许有空盒子

可以先视盒子为相同, 方案数为 \(S(n,m)\)（参见下文）, 再考虑盒子的全排列.

\(n\) 个不同的球放入 \(m\) 个不同的盒子, 盒子不允许为空, 方案数为 \(m!\cdot S(n,m)\).

允许有空盒子

最简单的情况没有之一:

\(n\) 个不同的球放入 \(m\) 个不同的盒子, 盒子允许为空, 方案数为 \(m^n\).

盒子相同

不允许有空盒子

\(n\) 个不同的球放入 \(m\) 个相同的盒子, 盒子不允许为空, 方案数为第二类Stirling数 \(S(n,m)\).

简略证明: 对于第 \(n\) 个球, 有且仅有如下两种情况:

前 \(n-1\) 个球的放法已经保证了 \(m\) 个盒子都不空: 此时只需将 \(n\) 号球随意放即可, 方案数为 \(mS(n-1,m)\);
前 \(n-1\) 个球放好后有且仅有一个盒子是空的: 此时必须将 \(n\) 号球放入空盒中, 方案数为 \(S(n-1,m-1)\).

于是, 此时的方案数递推式为 \[S(n,m)=mS(n-1,m)+S(n-1,m-1)\] 初值为:

\(S(0,m)=1\). (没球的方案只有一种)
\(S(n,1)=1\). (一个盒子的方案只有一种)

一段计算该种方案数的代码如下（递归版本）:

球不同, 盒相同, 不许空

int dp(int n, int m)
{
    if(n < m) return 0; // 球比盒子还少, 无法满足盒子非空
    if(n == 0 || m == 1) return 1; // 没球 or 一个盒子
    return m * dp(n - 1, m) + dp(n - 1, m - 1);
}

允许有空盒子

\(n\) 个不同的球放入 \(m\) 个相同的盒子, 盒子允许为空, 方案数为 \(\sum\limits_{k=0}^m S(n,k)\).

只需要枚举非空箱子的个数, 然后按照上一种情况的方法来计算, 求和即可. 在计算时最好先预处理出 \(S(n,m)\) 的值.

球相同

盒子不同

不允许有空盒子

\(n\) 个相同的球放入 \(m\) 个不同的盒子, 盒子不允许为空, 方案数为 \(\binom{n-1}{m-1}\).

简略证明: 将 \(n\) 球装入 \(m\) 个盒子, 相当于插 \(m-1\) 个板. 由于不允许为空, 故在 \(n-1\) 个空中选出 \(m-1\) 个插板即可.

允许有空盒子

\(n\) 个相同的球放入 \(m\) 个不同的盒子, 盒子允许为空, 方案数为 \(\binom{n+m-1}{m-1}\).

简略证明: \(n\) 个球放完之后, 在每个盒子中都加一个球, 此时一定无空箱. 这说明此时的方案数不多于 \(n+m\) 个相同的球放入 \(m\) 个不同盒子的方案数. 反过来也可证明另一边的不等式, 于是此时的方案数就是\(n+m\) 个相同的球放入 \(m\) 个不同盒子的方案数.

盒子相同

不允许有空盒子

\(n\) 个相同的球放入 \(m\) 个相同的盒子, 盒子不允许为空, 方案数为 \(dp(n-m,m)\).

其中 \(dp(n,m)\) 为下一种情况的方案数.

允许有空盒子

\(n\) 个相同的球放入 \(m\) 个相同的盒子, 盒子允许为空, 方案数为 \(dp(n,m)\).

计算思路:: 在放置 \(n\) 个球的时候, 有且仅有如下两种策略:

给每个盒子放一个球: 还剩下 \(n-m\) 个球, 故此时的方案数为 \(dp(n-m,m)\);
至少一个盒子不放球: 可以扔掉一个空盒子, 故此时的方案数为 \(dp(n,m-1)\).

于是此种情况的递推式为: \[dp(n,m)=dp(n-m,m)+dp(n,m-1)\] 边界值为:

\(S(0,m)=1\). (没球的方案只有一种)
\(S(n,1)=1\). (一个盒子的方案只有一种)

上述推导过程中我们做了 \(n\geqslant m\), 即“球不少于盒子”的假设. 当该假设不成立时, \(n\) 个苹果至多放满 \(n\) 个盘子, 故此时方案数实际上为 \(dp(n,n)\).

一段计算该情况方案数的代码如下（递归版本）:

球相同, 盒相同, 允许空

int dp(int m, int n)
{
    if(n == 1 || m == 0) return 1;
    if(m < n) return dp(m, m);
    return dp(m, n - 1) + dp(m - n, n);
}