【数学2-2】组合数学与计数

对应进阶篇第 20 章。

在《基础篇》第 20 章中已经介绍了计数原理与排列组合相关的问题,可以帮助求解在各种场合下的方案数。有一些概念需要复习一下:

  1. 加法原理:做一件事,有 n 类方法,第一类方法中有 m_1 种方法,第二类有 m_2 种……第 n 类有 m_n 种,则完成这件事有 \sum_{i=1}^n m_i 种不同的方案。
  2. 乘法原理:做一件事,有 n 个步骤需要依次完成,第一步中有 m_1 种方法,第二步有 m_2 种……第 n 步有 m_n 种,则完成这件事有 \prod_{i=1}^n m_i 种不同的方案。
  3. 排列数:从 n 个人里面选出 m 个人站成一排,考虑这些人的相对顺序,方案数是:A_n^m=n\cdot (n-1)\cdots(n-m+1) = \frac{n!}{(n-m)!}
  4. 组合数:从 n 个人里面选出 m 个人,不考虑这些人的相对顺序,方案数是 C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!\cdot (n-m)!}

这一章将会介绍更多和计数和排列组合相关知识,可以解决更多的方案数量统计的问题。


  1. P3197 - [HNOI2008] 越狱
  2. P5664 - [CSP-S 2019] Emiya 家今天的饭
  3. P1287 - 盒子与球
  4. P1450 - [HAOI2008] 硬币购物
  5. P5520 - [yLOI2019] 青原樱
  6. P4071 - [SDOI2016] 排列计数
  7. P1313 - [NOIP 2011 提高组] 计算系数
  8. CF1332E - Height All the Same
  9. P1044 - [NOIP 2003 普及组] 栈
  10. P2567 - [SCOI2010] 幸运数字
  11. P5505 - [JSOI2011] 分特产
  12. P3223 - [HNOI2012] 排队
  13. P2822 - [NOIP 2016 提高组] 组合数问题
  14. P3214 - [HNOI2011] 卡农
  15. P2532 - [AHOI2012] 树屋阶梯
  16. P3200 - [HNOI2009] 有趣的数列
  17. CF1278F - Cards
  18. P3228 - [HNOI2013] 数列
  19. CF961G - Partitions