multiset permutation · n! / ∏ nᵢ!

多重集排列：当源自带重复元素

前面的排列都假设 n 个元素互不相同。如果源本身是一个多重集(multiset)——里面有相同的元素，比如 {A, A, B, C}——把它们排成一列，两个 A 互换后看起来完全一样，朴素的 n! 会把这些等价排法重复计数。修正办法：除掉每组相同元素内部互换的次数。

1 · 除掉同组内部的互换：n! / (n₁!·n₂!···)

multiset permutation · n! / ∏ nᵢ!

设源里有 r 种不同的值，第 i 种出现 $n_i$ 次( $Σ n_i = n$ )。先当它们全不同，有 n! 种；但第 i 种的 $n_i$ 个相同元素之间有 $n_i!$ 种互换、结果都一样。按乘法原理这些互换相乘，故可区分的排列数是 $n! / (n_1!\cdot n_2!\cdot \cdot \cdot n_r!)$ （即多项式系数 multinomial coefficient）。拖动各元素的个数看它如何变化。

组合其实是它的特例。「从 n 个里选 k 个」可以看成排列一个两类多重集：k 个「选中」标记加 $n-k$ 个「没选」标记，排成一列的不同方式，就对应哪些位置被选中。于是它的排法数 $n! / (k!\cdot (n-k)!)$ 正是组合 C(n, k)——组合页里「除以 k!」那一步，在这里是「除以 $k!\cdot (n-k)!$ 」的两组版本。

2 · 相关链接

Permutations of multisets — Wikipedia · en.wikipedia.org——多重集排列 $n!/\prod n_i!$ 的推导。
Multinomial coefficient — Wikipedia · en.wikipedia.org——多项式系数，以及它与二项式系数 C(n, k) 的关系。