放球问题

题目描述

给定 \(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 \]