OI中组合数学公式与定理有哪些90%以上被应用歼灭？

本文共计8849个文字，预计阅读时间需要36分钟。

组合数学基础概念加法和乘法原理，同一步骤下的不同选择，可以通过累加得到方案数。乘法原理：整个流程的方案数可由每一步的方案数相乘得到。有了加法和乘法原理，可以简化计算。

组合数学 基础概念 加法和乘法原理 加法原理

同一步下的不同选择，可以通过累加得到方案数。

乘法原理

整个流程的方案数可以由每一步的方案数相乘得到。

有了加法原理和乘法原理，就可以解决一些没有选择导致分支的问题了。

例题1

有 \(n\) 个篮子，第 \(i\) 篮子有 \(a_i\) 有水果，每个水果各不相同，问每个篮子选出一个得到的水果的方案数。

解答：

用加法和乘法原理，那么每个篮子选出的方案数为 \(a_i\) ，总共就是 \(\prod a_i\) 种方案。

排列和组合 排列数

从 \(n\) 个不同元素中选出 \(m\) 个，按照一定顺序排列，简而言之就是选出一个数列的方案数。

\[A^m_n=n(n-1)(n-2)..(n-m+1)=\frac{n!}{(n-m)!} \]

组合数

从 \(n\) 个不同元素中选出 \(m\) 个的方案数，换句话就是选出一个集合的方案数。