组合数学

kuoying 2020-04-19

# 组合计数


加法原理

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

乘法原理

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

排列数

  • 从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

相关推荐