wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

杂项

启发式合并

高精度

一些经典问题

约瑟夫环

曼哈顿距离

多重集合的排列组合

排列与置换

[[ item.c ]]

多重集合的排列组合

## 多重集合的排列
**定理1**
设$$S$$是多重集合，它有$$k$$种不同类型的对象，每一种类型分别有$$n_1, n_2, \cdots, n_k$$个
如果$$S$$的大小是$$n = n_1 + n_2 + \cdots + n_k$$，那么$$S$$的排列数为
```math
\displaystyle
\dfrac{n!}{n_1!n_2!\cdots n_k!}
```
> 证明，依次考虑每个位置，第一个位置有$$\displaystyle \binom{n}{n_1}$$，第二个位置有$$\displaystyle \binom{n - n_1}{n_2}$$，以此类推
```math
\displaystyle
\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3} \cdots \binom{n-n_1-n_2-n_{k-1}}{n_k}
```

**定理2**
设$$n$$是正整数，并且$$n_1 + n_2 + \cdots + n_k = n$$，将其分到$$k$$个**有标签的盒子**中
使得第`1`个盒子有$$n_1$$个对象，第`2`个盒子有$$n_2$$个对象，第$$k$$个盒子有$$n_k$$个
方案数是
```math
\displaystyle
\dfrac{n!}{n_1!n_2!\cdots n_k!}
```
如果这些盒子没有标签，并且$$n_1 = n_2 = \cdots = n_k$$，方案数为
```math
\dfrac{n!}{k! n_1!n_2!\cdots n_k!}
```
实际上，把$$k!$$**除掉**，就是把$$k$$个有标签的盒子，抹去标签，当成同样的盒子看待

**互相不攻击的车**
有多少种方案，在$$8 \times 8$$棋盘上，放置互相不攻击的车？
先考虑行，那么行一定是形如$$1 \sim 8$$的排列，比如`[2, 1, 5, 6, 3, 7, 8, 4]`
分别表示$$(?, 2), (?, 1), \cdots, (?, 4)$$**被车占有**，方案数是$$n! = 8!$$

那么考虑$$?$$，不难发现，$$?$$也是两两不等的，方案数为$$n!$$，所以总的方案数是$$(n!)^2$$

**车有不同颜色**
有$$k$$种颜色共$$n$$个车，第一种颜色有$$n_1$$个，第二种有$$n_2$$个，第$$k$$种有$$n_k$$个
把这些车放在$$n \times n$$棋盘上，互相不攻击的方案数是
```math
\displaystyle
n!\dfrac{n!}{n_1!n_2!\cdots n_k!} = \dfrac{(n!)^2}{n_1!n_2!\cdots n_k!}
```

> 证明，首先应该为车染色，`(?, *)`，选出关于`*`的方案数，$$\displaystyle \dfrac{n!}{n_1!n_2!\cdots n_k!}$$
然后考虑排列，`?`是关于`1-n`的排列，方案数是$$n!$$

## 多重集合的组合
设$$S = \left< 2\cdot a, 1 \cdot b, 3 \cdot c \right>$$，一共`6`个数，那么$$S$$的`3`组合是
（需要拿掉`3`个数）
```bash
(2a, 1b), (2a, 1c),
(1a, 1b, 1c), (1a, 2c)
(1b, 2c)
(3c)
```

**定理1**
设$$S$$是一个有$$k$$种**类型**的多重集合，$$S$$的$$r$$组合，定义为
多重集合的$$r$$组合数，即**选$$r$$个元素**，（所有元素的重复数是无限的，可放回选择，或者至少是$$r$$）
```math
\displaystyle
\binom{r + k - 1}{r}
```
实际上，问题等价于，**有放回的选择**，第`1`种类型选$$x_1$$个，第`2`种选$$x_2$$个
第`k`种类型选$$x_k$$个，满足$$x_1 + x_2 + \cdots + x_k = r$$，其中$$x_i \geqslant 0$$
求这个不定方程解的方案数

实际上，极端情况，有$$k-1$$个`0`，$$x_i = r = 1+1+\cdots +1$$，有$$r$$个`1`
而`0, 1`的个数不变，构造不定方程的方案数，就是
```math
\displaystyle
\binom{r + k - 1}{r}
```
> 根据**球盒模型**来证明

其中，$$r$$个`1`可以看作$$r$$个球，放入$$k$$个盒子里，如果要求$$x_i > 0$$不能有空盒
那么可以**插板**，相当于在$$r-1$$个空位中，插入$$k-1$$个隔板，方案数是$$\displaystyle \binom{r-1}{k-1}$$

那么允许空盒呢？也就相当于$$x_i \geqslant 0$$，可以在$$k$$个盒子里，都预放入一个球
相当于有$$r + k$$个球，有$$r+k-1$$个空位，插入$$k-1$$个隔板，不允许有空盒的方案数
这样就转化成上面的问题了，方案数是$$\displaystyle \binom{r+k-1}{k-1}$$

**例子**
项取自`1, 2, ......, k`的，长度为$$r$$的非递减序列个数是多少，每个元素可以选多次
实际上，只需要考虑`1, 2, 3..., k`分别选多少个就可以了，选出来，排列方案是唯一的，就是非递减排序
那么这就相当于$$x_1 + x_2 +\cdots x_k = r$$的不定方程的解的数量，答案自然是
```math
\displaystyle
\binom{k-1+r}{r}
```

**例子**
对于多重集，$$\left< 10\cdot a, 10\cdot b, 10 \cdot c, 10\cdot d \right>$$，每种类型的对象至少出现一次
求`10`组合的方案数

实际上，要求$$x_i$$严格$$> 0$$，那么做变量替换
```math
\displaystyle
y_1 = x_1 - 1, y_2 = x_2 - 1 \cdots
```
相当于$$y_1 + y_2 + y_3 + y_4 = 6$$的不定方程解的个数，方案数是$$\binom{6 + 4 - 1}{6}$$

看完文章有啥想法

算法小站

wiki 主题

杂项

多重集合的排列组合

目录