最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

组合数学笔记-计数原理

来源:博客园
目录
  • 计数原理
    • 基本计数原理
      • 加法原理(分类)
      • 乘法原理(分步)
      • 减法原理(正难则反)
      • 除法原理(等价划分)
    • 重要计数原理
      • 抽屉原理(鸽巢原理)
      • 容斥原理

约定:


【资料图】

本笔记涉及的一切变量,若未特殊指明,则默认为非负整数。

计数原理

基本计数原理

加法原理(分类)

描述若完成一件事有 \(n\) 种方式,第 \(i\) 种方式有 \(a_i\) 种方法,那么完成这件事共有 \(\displaystyle \sum_{i=1}^n a_i\) 种方法。

应用从武汉到上海有乘火车、飞机、轮船 \(3\) 种交通方式可供选择,而火车、飞机、轮船分别有 \(k_1,k_2,k_3\) 个班次,那么从武汉到上海共有 \(k_1+k_2+k_3\) 种方法可以到达。

乘法原理(分步)

描述若完成一件事有 \(n\) 个步骤,第 \(i\) 个步骤有 \(a_i\) 种方法,那么完成这件事共有 \(\displaystyle \prod_{i=1}^n a_i\) 种方法。

应用从武汉到上海乘火车要换乘 \(3\) 次,\(3\) 次换乘分别有 \(k_1,k_2,k_3\) 个班次,那么从武汉到上海共有 \(k_1 \cdot k_2 \cdot k_3\) 种方法可以到达。

减法原理(正难则反)

描述若方法全集为 \(U\) ,则满足性质 \(A\) 的方法集合 \(S_A\) 为 全集-不满足性质A的方法集合,即 \(U - \overline{S_A}\) ,共有 \(|U| - |\overline{S_A}|\) 种方法。

应用\([1,n]\) 中不能被 \(2\) 整除的整数个数为 全部数字-能被2整除的数字,即 \(|[1,n]| - |\{x| 2\mid x,1 \leq x \leq n \}| = n- \left\lfloor \dfrac{n}{2} \right\rfloor\) 。

除法原理(等价划分)

描述若方法全集为 \(U\) ,恰好能被性质 \(A\) 划分成 \(k\) 个大小相等的等价类 \(S_i(1\leq i\leq n)\)(每个等价类内的方法对于性质 \(A\) 是同一种方法),则满足性质 \(A\) 的方法集合 \(S_A\) 为 每个等价类任选一个代表元组成的集合,共有 \(k = \dfrac{|U|}{|S_i|}\) 种方法。

应用\(n\) 个数中选 \(m\) 个数的组合 \(C_n^m\) 为 选数的排列数/每个组合被重复计数的次数,共有 \(\dfrac{\text{P}_n^m}{\text{P}_m^m}\) 种。

重要计数原理

抽屉原理(鸽巢原理)

第一抽屉原理把 \(n\) 个物品放入 \(m\) 个抽屉,则至少存在一个抽屉有至少 \(\left\lceil \dfrac{n}{m} \right\rceil\) 个物品。

第二抽屉原理把 \(n\) 个物品放入 \(m\) 个抽屉,则至少存在一个抽屉有至多 \(\left\lfloor \dfrac{n}{m} \right\rfloor\) 个物品。

应用\([1,2n]\) 中任选 \(n+1\) 个整数,一定存在互质的数。考虑给连续两个数分组 \((1,2),(3,4),\cdots,(2n-1,2n)\) ,根据第一抽屉原理,至少存在一个组两个数都被选了,这两个数一定互质。

容斥原理

描述有 \(n\) 个集合 \(S_i(1\leq i \leq n)\) ,那么其全集大小 \(\displaystyle \left| \bigcup_{i=1}^n S_i\right|\) 满足

\[\begin{aligned}\left| \bigcup_{i=1}^n S_i\right| &= \sum_{1\leq i_1 \leq n} |S_{i_1}| - \sum_{1\leq i_1应用\([1,n]\) 中能被 \(2\) 和 \(3\) 整除的整数个数为 能被2整除的数字+能被3整除的数字-能被6整除的数字,即 \(n- \left\lfloor \dfrac{n}{2} \right\rfloor - \left\lfloor \dfrac{n}{3} \right\rfloor + \left\lfloor \dfrac{n}{6} \right\rfloor\) 。

关键词: 从武汉到 加法原理 乘法原理