放球问题

题目描述

给定 $n$ 个（有标号/无标号）的球
放到 $m$ 个（有标号/无标号）的盒子里
每个盒子（可空/不可空）

注：“可空”表示可以有空的盒子，但不能全是空的盒子。

一些可能会出现的东西：

$A_{m}^n$ ：$n$ 个元素选 $m$ 个元素的排列。

$S(n,m)$ 为第二类斯特林数，表示将 $n$ 个不同元素划分为 $m$ 个无区别的非空子集的方案数，有

$S(n,0)=[n=0] \\[6pt] S(n,m) = S(n-1,m-1) + mS(n-1,m)$

解法

给定 $n$ 个「无标号」的球，放到 $m(n \ge m)$ 个「无标号」的盒子里，每个盒子「不可空」

解：可以把原问题看作：有 $m$ 种质量为 $1,2,\cdots,m$ 的砝码若干，求质量为 $n-m$ 的方案数。

定义生成函数 $F(x)$
$\begin{aligned} F(x) &= (1 + x^1 + x^2 + \cdots)\times(1+x^2 + x^4 + \cdots) \times \cdots \times (1 + x^m + x^{2m} + \cdots) \\[6pt]&=\frac{1}{(1-x)\left(1-x^2\right) \ldots\left(1-x^m\right)} \end{aligned}$
答案即为 $[x^{n-m}]F(x)$ ，即生成函数第 $n-m$ 项的系数。
给定 $n$ 个「无标号」的球，放到 $m(n < m)$ 个「无标号」的盒子里，每个盒子「不可空」

解：显然此时答案为 $0$ 。
给定 $n$ 个「无标号」的球，放到 $m(n\ge m)$ 个「无标号」的盒子里，每个盒子「可空」

解：可以把原问题看作：有 $m$ 种质量为 $1,2,\cdots,m$ 的砝码若干，求质量为 $n$ 的方案数。

定义生成函数 $F(x)$
$\begin{aligned} F(x) &= (1 + x^1 + x^2 + \cdots)\times(1+x^2 + x^4 + \cdots) \times \cdots \times (1 + x^m + x^{2m} + \cdots) \\[6pt]&=\frac{1}{(1-x)\left(1-x^2\right) \ldots\left(1-x^m\right)} \end{aligned}$
答案即为 $[x^n]F(x)$ ，即生成函数第 $n$ 项的系数。
给定 $n$ 个「无标号」的球，放到 $m(n< m)$ 个「无标号」的盒子里，每个盒子「可空」

解：可以把原问题看作：有 $n$ 种质量为 $1,2,\cdots,n$ 的砝码若干，求质量为 $n$ 的方案数。

为什么是 $1$ 到 $n$ 的砝码呢？因为 $m > n$ 时质量为 $n$ 的砝码不存在。

定义生成函数 $F(x)$
$\begin{aligned} F(x) &= (1 + x^1 + x^2 + \cdots)\times(1+x^2 + x^4 + \cdots) \times \cdots \times (1 + x^n + x^{2n} + \cdots) \\[6pt]&=\frac{1}{(1-x)\left(1-x^2\right) \ldots\left(1-x^n\right)} \end{aligned}$
答案即为 $[x^n]F(x)$ ，即生成函数第 $n$ 项的系数。
给定 $n$ 个「无标号」的球，放到 $m(n\ge m)$ 个「有标号」的盒子里，每个盒子「不可空」

解：问题等价于求解下面方程的解的个数
$x_1 + x_2 + \cdots + x_m = n \qquad(x_i \in \mathbb{Z}_+)$
考虑插空法。将 $m-1$ 个隔板插到 $n-1$ 个空隙中（空隙只能放至多一个）

则方案数为
$\dbinom{n-1}{m-1}$
给定 $n$ 个「无标号」的球，放到 $m(n < m)$ 个「有标号」的盒子里，每个盒子「不可空」

解：显然此时答案为 $0$ 。
给定 $n$ 个「无标号」的球，放到 $m(n \ge m)$ 个「有标号」的盒子里，每个盒子「可空」

解：和问题5差不多，只不过 $x_i \in \mathbb{N}$ ，我们只要令 $y_i = x_i+1$ ，就i转化为了
$y_1 + y_2 + \cdots + y_m = n + m\qquad(y_i \in \mathbb{Z_+})$
则方案数为
$\dbinom{n+m-1}{m-1}$
给定 $n$ 个「无标号」的球，放到 $m(n < m)$ 个「有标号」的盒子里，每个盒子「可空」

解：此问题和问题7等价，方案数同样为
$\dbinom{n+m-1}{m-1}$
给定 $n$ 个「有标号」的球，放到 $m(n\ge m)$ 个「无标号」的盒子里，每个盒子「不可空」

解：根据第二类斯特林数的定义易得
$S(n,m)$
给定 $n$ 个「有标号」的球，放到 $m(n < m)$ 个「无标号」的盒子里，每个盒子「不可空」

解：显然此时答案为 $0$ 。
给定 $n$ 个「有标号」的球，放到 $m(n \ge m)$ 个「无标号」的盒子里，每个盒子「可空」

解：枚举非空盒子的个数，注意不能全为空
$\sum_{i=1}^{m}S(n,i)$
给定 $n$ 个「有标号」的球，放到 $m(n < m)$ 个「无标号」的盒子里，每个盒子「可空」

解：和问题11一样，只不过可以去掉贡献为 $0$ 的情况
$\sum_{i=1}^{n}S(n,i)$
给定 $n$ 个「有标号」的球，放到 $m(n\ge m)$ 个「有标号」的盒子里，每个盒子「不可空」

解：枚举 $m$ 个盒子的全排列即可
$m!S(n,m)$
给定 $n$ 个「有标号」的球，放到 $m(n < m)$ 个「有标号」的盒子里，每个盒子「不可空」

解：显然此时答案为 $0$ 。
给定 $n$ 个「有标号」的球，放到 $m(n \ge m)$ 个「有标号」的盒子里，每个盒子「可空」

解：这等价于给每个球染色，可以有颜色没有被用到
$m^n$
给定 $n$ 个「有标号」的球，放到 $m(n < m)$ 个「有标号」的盒子里，每个盒子「可空」

解：这等价于给每个球染色，可以有颜色没有被用到
$m^n$