组合数学 2.2 - 多重集的排列

定义 2.2.1：有 \(n_1\) 个 \(a_1\)，\(n_2\) 个 \(a_2\)，\(\dots\)，\(n_k\) 个 \(a_k\) 组成的集合记为 \(M=\{n_1\cdot a_1,n_2\cdot a_2,\dots,n_k\cdot a_k\}\) 称为多重集。\(M\) 的总元素个数为 \(\sum\limits_{i=1}^k n_i\)。

定义 2.2.2：设 \(M=\{n_1\cdot a_1,n_2\cdot a_2,\dots,n_k\cdot a_k\}\)，\(\pi\) 是集合 \(\{a_1,a_2,\dots,a_k\}\) 的一个 \(n~-\) 可重复排列，若 \(\pi\) 中有 \(n_1\) 个 \(a_1\)，\(n_2\) 个 \(a_2\)，\(\dots\)，\(n_k\) 个 \(a_k\)。称 \(\pi\) 是多重集 \(M\) 的一个全排列。

定理：多重集 \(M=\{n_1\cdot a_1,n_2\cdot a_2,\dots,n_k\cdot a_k\}\) 的全排列个数 \(N=\dfrac{(\sum\limits_{i=1}^k n_i)!}{\prod\limits_{i=1}^k n_i!}\)。

定义 2.2.3：设 \(M=\{n_1\cdot a_1,n_2\cdot a_2,\dots,n_k\cdot a_k\}\)，\(A=\{s_1\cdot a_1,s_2\cdot a_2,\dots,s_k\cdot a_k\}\)，其中 \(0\leqslant s_i\leqslant n_i\)。我们称 \(A\) 是 \(M\) 的一个子集。进一步，设 \(r=\sum\limits_{i=1}^k s_i\)，称 \(A\) 是 \(M\) 的 \(r~-\) 子集。由 \(r~-\) 子集中元素构成的排列称为 \(r~-\) 排列。

例 2.2.1：求多重集 \(M=\{5\cdot a,3\cdot b\}\) 的 \(6~-\) 排列个数。

解：

不难发现 \(6~-\) 排列具体可分类成：\(\begin{cases}\{5\cdot a,b\}\\\{4\cdot a,2\cdot b\}\\\{3\cdot a,3\cdot b\}\end{cases}\)。则可以直接根据公式可以求得：

• 排列 \(\{5\cdot a,b\}\) 的个数为 \(\dfrac{6!}{5!\cdot 1!}=6\)。
• 排列 \(\{4\cdot a,2\cdot b\}\) 的个数为 \(\dfrac{6!}{4!\cdot 2!}=15\)。
• 排列 \(\{3\cdot a,3\cdot b\}\) 的个数为 \(\dfrac{6!}{3!\cdot 3!}=20\)。

因此排列总数为 \(6+15+20=41\)。