多重集的排列组合

组合数学 数学

---

多重集

定义 元素可以多次出现的集合 (即元素可以重复), 设某个元素 $a_i$ 的出现次数为 $n_i, i=0,1,2,\cdots$ 通常把含 $k$ 种不同元素的多重集记为

$$S=\{n_1a_1, n_2a_2,\cdots,n_ka_k\}.$$
(PS : 中间省略了乘号.)

---

可重排列

概念

r-可重排列 从多重集 $S=\{n_1a_1,n_2a_2,\cdots,n_ka_k\}$ 中有序地取出 $r$ 个元素, 称为 $S$ 的一个 $r$-可重排列. 当 $r=n$ 时, 就叫做 $S$ 的一个全排列.

定理1 假设多重集 $S=\{\infty a_1,\infty a_2,\cdots,\infty a_k\}$, 则 $S$ 的 $r$-可重排列数为 $k^r$.
推论1 假设多重集 $S=\{n_1a_1,n_2a_2,\cdots,n_ka_k\}$, 且有 $n_i\ge r,i=1,2,3,\cdots,k$, 则 $S$ 的 $r$-可重排列数为 $k^r$.

定理2 假设 $S=\{n_1a_1,n_2a_2,\cdots,n_ka_k\}$, 且 $n=\sum_{i=1}^{k} n_i$, 则 $S$ 的全排列数为 $\frac{n!}{n_1n_2\cdots n_k}$.
理解 : 先求出总的全排列 $n!$, 再除去每一种元素的重复度.

例题

例1 求不多于 4 位数的二进制数个数.
问题可以转化为求可重集 $S=\{\infty 0,\infty 1\}$ 的 $4$-可重排列, 排列数即为 $2^4$.

总结

设 $S=\{n_1a_1,n_2a_1,\cdots,n_ka_k\}$, 且 $n=\sum_{i=1}^{k}$, 则 $S$ 的 $r$-可重排列数 $N$ 满足 :
1. 若 $r>n$, 则 $N=0$.
2. 若 $r=n$, 则 $N=\frac{n!}{n_1!n_2!\cdots n_k}$.
3. 若 $r<n$, 且对于所有 $i$ 都有 $n_i\ge r$, 则 $N=k^r$.
4. 若 $r<n$, 且存在 $i$, 使 $n_i<r$, 则对 $N$ 没有一般求解公式.

---

可重组合

概念

定义 从 $S=\{n_1a_1,n_2a_1,\cdots,n_ka_k\}$ 中取 $r$ 个元素 $b_1,b_2,\cdots,b_r$, 且允许重复, 即允许 $b_i=b_j(i \not=j)$, 的组合记为 $\overline{C}(k,r)$.

定理1 从 $S=\{\infty a_1,\infty a_2,\cdots,\infty a_k\}$ 中取出 $r$ 个元素作可重组合, 其组合数为 $C(k+r-1,r)$.

证明 :
方法1 (组合证法) :
这相当于把 $r$ 个相同的球放进 $k$ 个不同的盒子里, 每个盒子里的球数量无限制的方案数,
又可以进一步转化为, 有 $r$ 个球, 要用 $k-1$ 个(相同的)隔板把它们隔开 (隔板是相同的, 是因为我们不在乎哪块隔板隔出了哪个区域, 我们只在乎每个区域中球的数量, 这就代表了每个盒子里球的数量), 那就用 $r$ 个球和 $k-1$ 个隔板排列一下, 但这里球和隔板都是相同的, 所以在除去它们各自的重复度(即它们的全排列), 得到

$$\frac{A(r+k-1,r+k-1)}{A(r,r)A(k-1,k-1)}=\frac{(r+k-1)!}{r!(k-1)!}=C(r+k-1,r).$$

方法2 (拉伸压缩技巧) :
假设某一个 $r$-可重组合为 $b_1,b_2,\cdots,b_r$, 且 $b_1 \le b_2 \le \cdots \le b_k$.
设 $c_1=b_1,c_2=b_2+1,\cdots,c_i=b_i+i-1$, 则 $c_1<c_2<\cdots<c_k=b_k+r-1$,
所以问题转化为在 $k+r-1$ 个元素中取出 $r$ 个不重复元素的方案数, 即为 $C(k+r-1,r)$.

推论1 设 $S=\{n_1a_1,n_2a_1,\cdots,n_ka_k\}$, 若 $n_i\ge r,i=1,2,\cdots,k$, 则 $S$ 的 $r$-可重排列数为 $C(k+r-1,r)$.

推论2 设 $S=\{n_1a_1,n_2a_1,\cdots,n_ka_k\}$, 若 $r\ge k$, 且 $n_i>r,i=1,2,\cdots,k$, 则 $S$ 中每种元素至少取一个的 $r$-可重组合数为 $C(r-1,k-1)$.

证明 :
对于任意一个满足要求的组合, 将其中每种元素都取出一个, 就得到了一个 $r-k$-可重组合,
反之, 对于任何一个 $r-k$-可重组合, 将 $S$ 中的每一种元素都加入 1 个到该组合中, 就得到了一个每种元素至少取一个的 $r$-可重组合.
所以, $S$ 中每种元素至少取一个的 $r$-可重组合 与 $S$ 中的 $r-k$-可重组合 一一对应, 方案数为 $C(r-k+k-1,r-k)=C(r-k+k-1,k-1)=C(r-1,k-1)$.

例题

例2 问 $(x+y+z)^4$ 有多少项.
问题就相当于可重集 $S={4x,4y,4z}$ 的 4-可重组合, 组合数为 $C(4+3-1,4)=15$,
答案即为 15.

总结

设 $S=\{n_1a_1,n_2a_2,\cdots,n_ka_k\},n=\sum_{i=1}^{k}$, 则 $S$ 的 $r$-可重组合数 $N$ 满足 :
1. 若 $r>n$, 则 $N=0$.
2. 若 $r=n$, 则 $N=1$.
3. 若 $r<n$, 且对所有的 $i$ 都有 $n_i\ge r$, 则 $N=C(r+k-1,r)$.
4. 若 $r<n$, 且存在 $i$, 使得 $n_i<r$, 则对 $N$ 没有一般的求解公式.