排列与组合的模板总结

TIP

本页总结了第二章常用的公式和问题模板

环形排座

可以看作 n 元素的循环 n 排列，要在线性排列的基础上除以 n 去除轮换对称的重复项。

\frac{P (n, n)}{n}

\frac{P (n, r)}{r}

多重集合 ${n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$ ，集合大小 $n = n_{1} + n_{2} + \dots + n_{k}$ ，使用乘法原理化简，得到排序个数公式。

\frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

把 n 个对象放到 k 个盒子中，盒子可能有标签（也可能没有标签）。

可以从每一组选择对象加入考虑，本质上就是多重集合排序。

\frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

转化为平均分组问题。

\frac{n!}{k! \cdot n_{1}! n_{2}! \dots n_{k}!}

可以把配对问题转化为组无区别的分组问题。

先从大棋盘中选出小棋盘，然后逐行考虑放在哪一列，最后考虑哪些列染什么色。

(\binom{n}{m}) (\binom{n}{m}) \times m! \times (\binom{m}{r})

多重集合 ${\infty \cdot a_{1}, \infty \cdot a_{2}, \dots, \infty \cdot a_{k}}$ ，该多重集合的 r 组合个数为

(\binom{r + k - 1}{k - 1}) = (\binom{r + k - 1}{r})

x_{1} + x_{2} + \dots + x_{k} = r, x_{i} \geq 0

非负整数解的个数为 $(\binom{r + k - 1}{r})$ 。

有 r 个物品，从中选择 k 个不相邻的物品。

该问题可以转化为把 r-k 个物品划分为 k+1 个部分。