组合数学

# 组合计数

加法原理

• 若完成一件事的方法有n类,其中第i类方法包括a1种不同的方法,且这些方法互不重合,则完成这件事共有a₁+a₂+…+a_n种不同的方法

乘法原理

• 0若完成一件事需要n个步骤,其中第个步骤有a种不同的完成方法,且这些步骤互不干扰,则完成这件事共有a₁·a₂......·a_n种不同的方法

排列数

• 从n个不同元素中依次取出m个元素排成一列,产生的不同排列的数量为:A(n,m)=n!/(n-m)!

组合数

• 从n个不同元素中取出m个组成一个集合(不考虑顺序),产生的不同集合数量 C(n,m)=n!/m!·(n-m)!

性质：

# 多重集的组合计数

# Lucas定理

对于任意的质数p：

\left(\begin{array}{l}n \\ m\end{array}\right) \bmod p=\left(\begin{array}{l}\lfloor n / p\rfloor \\ \lfloor m / p\rfloor\end{array}\right) \cdot\left(\begin{array}{l}n \bmod p \\ m \bmod p\end{array}\right) \bmod p