组合计数中，为什么本题中要除去高亮部分所示的因子？
2023-05-11 阅读 44
对于组合计数，我们有以下公式：
\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日
