排列组合常见模型

\(~~~~\) 约定：下文涉及到球和盒子若未特殊说明，则有 \(n\) 个球，\(r\) 个盒子。

球同，盒不同，不空

\(~~~~\) 考虑每个盒子放多少球，那就是不允许空的插板，故方案数 \(\begin{pmatrix} n-1\\r-1 \end{pmatrix}\).

球同，盒不同，可空

\(~~~~\) 只是将上题的不可空变为可空，仍然插板，方案数 \(\begin{pmatrix} n+r-1\\r-1 \end{pmatrix}\).

球不同，盒同，不空

\(~~~~\) 由第二类斯特林数定义：方案数 \(\begin{Bmatrix} n\\r \end{Bmatrix}\).

球不同，盒同，可空

\(~~~~\) 枚举实际占用了几个盒子，方案数 \(\sum_{i=1}^r \begin{Bmatrix} n\\i \end{Bmatrix}\)

球不同，盒不同，无空

\(~~~~\) 在第二类斯特林树的基础上加上盒子的独立性，答案为 \(\begin{Bmatrix} n\\r \end{Bmatrix}\times r!\)

球不同，盒不同，可空

\(~~~~\) 那么考虑每个球进哪个盒子，发现都有 \(r\) 种选择，故为 \(r^n\) 。

球同，盒同，无空

\(~~~~\) 实际就是考虑划分成 \(r\) 个可空集合，所有集合的元素个数之和为 \(n\) 的方案数。进而是预先给每个盒子放一个球，故最终求 \(r\) 个非负整数，所有数的和为 \(n-r\) 的升序数列个数。dp解决即可。

球同，盒同，有空

\(~~~~\) 与上种情况相似，甚至不用加入兜底的小球。

圆排列

\(~~~~\) 首先考虑不在圆上是 \(n\) 个物品的排列方案为 \(A_{n}^n=n!\) ，然后在圆上时相当于每组在普通情况下循环同构的序列将被算成一组，每组循环同构显然都恰有 \(n\) 个序列。故最后方案数为 \(\dfrac{n!}{n}=(n-1)!\).

错排问题

\(~~~~\) 考虑 \(n\) 个球，\(n\) 个盒子。一个球有且仅有一个盒子不能放入，一个盒子有且仅有一个球不能装，求方案数。

\(~~~~\) 记 \(D_i\) 表示 \(i\) 个球，\(i\) 个盒子时的方案数。手玩有：\(D_1=0,D_2=1\) 。

\(~~~~\) 考虑能否递推，当增加一个球时，考虑这个增加的球：其可以放入 \(1\sim n-1\) 任意一个盒子中，假设我们放入了第 \(k\) 个盒子，那么第 \(k\) 个球若放入第 \(n\) 个盒子，剩下的方案则为 \(D_{n-2}\) ，否则就是第 \(k\) 个球不能放入第 \(n\) 个盒子，剩下的方案数为 \(D_{n-1}\)。同时把选择 \(k\) 的方案数考虑进来，故：

\[D_n=(D_{n-1}+D_{n-2})(n-1)(n \geq 2) \]