Counting

约 477 个字 预计阅读时间 2 分钟

1. 分布计数

多步骤计数规则（乘法原理）：如果一个试验有 \(k\) 个部分，第 \(i\) 个部分有 \(n_{i}\) 种结果，且不同部分相互独立，则试验的总结果数为

\[ \prod_{i=1}^{k}n_{i} \]

集合的或运算（加法原理）：如果一次试验的结果可能来自集合 \(S_{1\sim n}\)，且任意不同集合 \(S_{i},S_{j}\) 两两互斥，则试验的总结果数为

\[ \sum_{i=1}^{n}|S_{i}| \]

当集合不互斥时，需要使用容斥原理：奇数个集合前为正，偶数个集合前为负：

\[ \begin{aligned} |S_{1}\,\text{or}\,S_{2}\,\text{or}\,S_{3}|&= |S_{1}|+|S_{2}|+|S_{3}|\\ &-|S_{1}\,\text{and}\,S_{2}|-|S_{1}\,\text{and}\,S_{3}|-|S_{2}\,\text{and}\,S_{3}|\\ &+|S_{1}\,\text{and}\,S_{2}\,\text{and}\,S_{3}| \end{aligned} \]

2. 排列组合

2.1 排列

不同对象排列：\(n\) 个不同对象共有 \(n!\) 种排列方法．若从 \(n\) 个对象中选出 \(r\) 个对象进行排列，共有 \(A_{n}^{r}=\dfrac{n!}{r!}\) 种排列方法．

含有相同对象排列：\(n\) 个对象中，分为 \(r\) 组，每组内 \(n_{i}\) 个对象两两相同（或者组内的顺序不影响），则总排列方法数为

\[ \dfrac{n!}{\prod_{i=1}^{r}n_{1}! } \]

2.2 组合

不同对象组合：从 \(n\) 个对象中无序地选择 \(r\) 个对象，共有 \(\dfrac{n!}{r!(n-r)!}\) 中组合方法，记作 \(\dbinom{n}{r}\) 或 \(C_{n}^{r}\)．

2.3 分桶

不同对象分桶：\(n\) 个不同对象放入 \(r\) 个容器中，每一个对象都有 \(r\) 种选法，总共有 \(r^{n}\) 种分法．

相同对象分桶：\(n\) 个相同对象放入 \(r\) 个容器中，我们可以将 \(r\) 个容器看成 \(r-1\) 个隔板，每两个隔板以及最两侧为容器．此时问题等价于 \(n\) 个相同对象与 \(r-1\) 个相同对象的排列问题，总排列方法数为

\[ \frac{(n+r-1)!}{n!(r-1)!}=\binom{n+r-1}{r-1} \]