多重排列与多重全排列

Template:Citecheck 多重排列与多重全排列是组合数学中的常见的两个排列模型，具有广泛的应用场景。尽管多重排列与多重全排列仅有一字之差，但是具有完全不同的实际意义。

定义

多重排列定义

设多重集的几何大小为$n$，取其中的$m$个数进行排列，即为多重排列。设多重集内元素细节为$r_1$个$x_1$，$r_2$个$x_2$，...，$r_k$个$x_k$，则可记为$P(m;r_1+r_2+...+r_k=n)$.

多重全排列定义

有$r_1$个$x_1$，$r_2$个$x_2$，...，$r_k$个$x_k$个数，其中$r_1+r_2+...+r_k=n$，对这样的$n$个数所求的排列，即为多重全排列，记为$P(n;r_1,r_2,...,r_k)$或$(\genfrac{}{}{0ex}{}{n}{r_1{r}_2...r_k})$。

计算方法

多重排列计算方法

枚举法：小范围的多重排列采用分类枚举方法即可得出正确结果。

多重全排列计算方法

$P(n;r_1,r_2,...,r_k)\cdot r_1!\cdot r_2!\cdot ...\cdot r_k!=n!$

$⟹P(n;r_1,r_2,...,r_k)=\frac{n!}{r_1!\cdot r_2!\cdot ...\cdot r_k!}$

即$(\genfrac{}{}{0ex}{}{n}{r_1{r}_2...r_k})=\frac{n!}{r_1!\cdot r_2!\cdot ...\cdot r_k!}$

举例

举例：多重排列

某校举办运动会，计算机系派出代表人数分布如下：人智所有3个人报名，高性能所有2个人报名，软件所有4名同学报名（ps:认为同一所的同学无差别，仅代表研究所内一个成员），共有8个完全不同的个人单项项目，计算机系需要选择其中的8个人代表院系参加比赛（每人必须参加一项，且不能超过一项），报名的三个所至少每个所获得一个参赛名额，问共有多少种排列方案？

解：

大类一： $\frac{8!}{3!\cdot 1!\cdot 4!}=280$

大类二： $\frac{8!}{3!\cdot 2!\cdot 3!}=560$

大类三： $\frac{8!}{2!\cdot 2!\cdot 4!}=420$

总计： $280+560+420=1260$

举例：多重全排列

某校举办运动会，计算机系派出代表人数分布如下：网络所有3名同学报名，软件所有4名同学报名，人智所有3个人报名，高性能所有2个人报名（ps:认为同一所的同学无差别，仅代表研究所内一个成员），共有12个完全不同的个人单项项目，每人必须参加一项，且不能超过一项，问共有多少种排列方案？

解：

设排列方案为$ans$，则

$ans=\frac{12!}{3!\cdot 4!\cdot 3!\cdot 2!}=277200$