【学习笔记】初等数论-组合计数

发布时间 2023-11-10 20:38:01作者: HZOI-Isaac

加法原理

  • 若完成一件事的方法有 \(n\) 类,其中第 \(i(1 \le i \le n)\) 类方法包括 \(a_i\) 种不同的方法,且这些方法互不重合,则完成这件事共有 \(\sum\limits_{i=1}^{n}a_i\) 种不同的方法。

乘法原理

  • 若完成一件事的步骤有 \(n\) 个,其中第 \(i(1 \le i \le n)\) 个步骤包括 \(a_i\) 种不同的方法,且这些方法互不重合,则完成这件事共有 \(\prod\limits_{i=1}^{n}a_i\) 种不同的方法。

排列

  • \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列,产生的不同排列的数量为 $A_{n}^{m}=n \times (n-1) \times (n-2) \times \dots $ 。

组合

二项式定理

卢卡斯定理

扩展卢卡斯定理