多重集合的排列组合

多重集合的排列组合

​ 论述一些在组合数学里比较基础的问题。

多重集合的排列

​ 给定 $n$ 个数：$a_1,a_2,...,a_n$，求不重复的排列方案数。

​ 显然我们可以直接发现，由于求不重复的排列方案数，代数值相同的两个数是没有区别的。

​ 那么，考虑建立一个桶的数组，对代数值相同的计个数，所以可以得到一个不同的表示方法：

$t_1 \times a_1,t_2 \times a_2,...,t_k \times a_k$

​ $t_i \times a_i$ 表示给定的 $n$ 个数中，数值大小为 $a_i$ 的数为 $t_i$ 个，且对于 $a_1,a_2,...,a_k$ 而言是 $k$ 个互不相同的代数值，而此时一共具有 $k$ 个不同的代数值。

​ 那么依次对于 $t_i \times a_i$ 进行放置，考虑到如果现在剩余 $m$ 个位置，那么放置的方案数为 $\binom{m}{t_i}$。

​ 每次操作之后对于剩余位置数的处理为 $m-t_i$，所以总方案数则为：

$\sum_{i=1}^{k} \binom{n - \sum_{j=1}^{j<i} t_j}{t_i}$

$\frac{n!}{t_1!(n-t_1)!} \cdot \frac{(n-t_1)!}{t_2!(n-t_1-t_2)!} \cdot ,..., \cdot \frac{t_k!}{t_k!0!} = \frac{n!}{\prod_{i=1}^{k} {t_i}!}$

​ 换一种方式而言，$\frac{n!}{\prod_{i=1}^{k} {t_i}!}$ 的表示可以看成对于所有的排列方案中，除去代数值相同的数所产生的重复排列的方案数。即对于 $a_i$ 而言，他所产生的多余的贡献值则为一个累积上的 $t_i$，即本身的排列数。

多重集合的组合

无限元素多重集合

​ 设 $S$ 为有 $k$ 种对象类型对象的多重集合，每种元素均具有无限的重复数，求 $S$ 的 $r$ 组合的方案数。

​ 稍微考虑到一个简单的转化，原问题即求出对于 $x_1 + x_2 + ... + x_k = r$ 方程的非负整数解的个数。

​ 考虑插板法，对于 $k$ 个对象中选出 $r$ 组合而言，考虑到由于组合不计顺序，则形同于在 $r+k-1$ 个位置中选出 $k-1$ 个来放置隔板，从而分段形成 $k$ 个区间来表示 $x_1$ 到 $x_k$ 的大小，即：

$\binom{r+k-1}{k-1}$

有限元素多重集合

​ 设 $S$ 为有 $k$ 种对象类型对象的多重集合 { $n_1 \cdot a_1 , n_2 \cdot a_2 , ... , a_k \cdot n_k$ }，求 $S$ 的 $r$ 组合的方案数。

​ 则此问题可以转化为：求对于 $x_1+x_2+...+x_k=r$ 方程中满足 $0\leq x_1 \leq n_1$，$0\leq x_2 \leq n_2$，$...$，$0\leq x_k \leq n_k$ 时的非负整数解的个数。

​ 此时考虑到会涉及容斥原理的相关内容，我们将放在以后通过利用容斥原理对其予以讨论。