组合计数中，为什么本题中要除去高亮部分所示的因子？
2023-05-11 阅读 29
对于组合计数，我们有以下公式：
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$$
其中，$n!$ 表示 $n$ 的阶乘，即 $n \times (n-1) \times (n-2) \times \cdots \times 1$。
在本题中，我们需要求的是从 $n$ 个物品中选出 $k$ 个物品的方案数，其中 $k$ 个物品中有 $p$ 个相同的物品，$q$ 个相同的物品，$\cdots$，$r$ 个相同的物品。那么，根据乘法原理，方案数可以表示为：
$$
\binom{n}{k} \times \binom{k}{p} \times \binom{k-p}{q} \times \cdots \times \binom{k-p-q-\cdots-s}{r}
$$
其中，$\binom{n}{k}$ 表示从 $n$ 个物品中选出 $k$ 个物品的方案数，$\binom{k}{p}$ 表示从 $k$ 个物品中选出 $p$ 个相同的物品的方案数，$\binom{k-p}{q}$ 表示从剩余的 $k-p$ 个物品中选出 $q$ 个相同的物品的方案数，以此类推。
但是，由于 $p$ 个相同的物品是不加区分的，$q$ 个相同的物品也是不加区分的，因此，上述公式中的方案数会将这些相同的物品重复计算。例如，对于 $p$ 个相同的物品，我们在 $\binom{k}{p}$ 中已经将它们选出来了，但是在 $\binom{k-p}{q}$ 中，我们又将它们重新选了一遍，导致方案数重复计算了。因此，我们需要将重复计算的部分除去，即除去高亮部分所示的因子，得到最终的方案数：
$$
\frac{\binom{n}{k} \times \binom{k}{p} \times \binom{k-p}{q} \times \cdots \times \binom{k-p-q-\cdots-s}{r}}{p!q!\cdots r!}
$$
其中，$p!q!\cdots r!$ 表示将重复计算的部分除去的因子。
更新于 2023年05月14日
