数学 / 排列组合 · 从计数原理到 P(n,k) 与 C(n,k) / 多重集排列 待审核 8 / 25
multiset permutation · n! / ∏ nᵢ!

多重集排列

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

1 · 除掉同组内部的互换

multiset permutation · n! / ∏ nᵢ!

设源里有 rr 种不同的值，第 ii 种出现 nin_i 次，且 ∑ini=n\sum_i n_i = n。先当它们全不同，有 n!n! 种；但第 ii 种的 nin_i 个相同元素之间有 ni!n_i! 种互换、结果都一样。按乘法原理这些互换相乘，故可区分的排列数是

n!n1! n2!⋯nr!=n!∏i=1rni!\frac{n!}{n_1!\, n_2! \cdots n_r!} = \frac{n!}{\prod_{i=1}^{r} n_i!}

这个量称为多项式系数（multinomial coefficient）。

图 1-1 · 多项式系数随各值出现次数的变化。可拖动各元素的个数，观察分母中每一项如何折叠掉对应的等价排法。
图 1-2 · 一个多重集的全部可区分排列。可对照枚举条数与上式的计算值。

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

2 · 参考文献

  1. Permutations of multisets. Wikipedia. 多重集排列 n!/∏ni!n!/\prod n_i! 的推导。https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets
  2. Multinomial coefficient. Wikipedia. 多项式系数，以及它与二项式系数的关系。https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients