按分布型分类计数

解题套路

题面形如「$k$ 个人（球、书）放到 $m$ 个位置（台阶、盒子、小组），每个位置最多放 $c$ 个，问几种放法」。直接一把数容易漏，按分布型切最稳：

1. 列出所有分布型。 把 $k$ 写成不超过 $c$ 的正整数之和（不计次序），每一种写法就是一型。$k=3$、$c=2$ 时只有两型：$1+1+1$ 与 $2+1$。
2. 每一型各算各的：先选位置，再把元素分配到选中的位置上。
3. 相加。

为什么不重不漏

「各位置各装几个」这个多重集由一次放法唯一确定，而不同的型给出不同的多重集——所以每一种放法恰好落在一型里。这是分类加法原理的前提，不需要额外论证。这正是选它当分类轴的理由：换个轴（比如「甲站在第几级」）就得自己去证不重不漏。

型内怎么数：位置有别、元素有别

最常见的两种写法（以 $1+1+1$ 与 $2+1$、$m$ 个位置、元素两两不同为例）：

• $1+1+1$ 型：从 $m$ 个位置里挑 $3$ 个再排给 $3$ 个元素，$A_m^3$；等价地 $\mathrm{C}_m^3\cdot3!$。
• $2+1$ 型：先挑出单独的那个元素（$\mathrm{C}_k^1$），再给「两个的那个位置」与「一个的那个位置」各选一个位置——两个位置角色不同，所以是 $A_m^2$ 而不是 $\mathrm{C}_m^2$。

两个常翻的车

• 同一个位置内部再排一次顺序。 若题面说「同一处不分先后」，那一处内部是无序的，乘 $2!$ 就把每种放法数了两遍。
• 型内的两个位置当成没有区别。 $2+1$ 型里「装两个的」与「装一个的」角色不同，选位置要用排列数。