计数原理

分类加法计数原理与分步乘法计数原理

分类加法计数原理

引例

• 题干

  用一个大写的英文字母或一个阿拉伯数字给教室里的一个座位编号，总共能编出多少种不同的号码？

• 解决

  因为英文字母共有 \(26\) 个，阿拉伯数字共有 \(10\) 个，所以总共可以编出 \(26 + 10 = 36\) 种不同的号码。

引申：逻辑连接词

• \(a\) 或 \(b\)

  符号：\(a \wedge b\)
  含义：1.有 \(a\) 无 \(b\)； 2.无 \(a\) 有 \(b\)； 3.有 \(a\) 也有 \(b\)。

• \(a\) 且 \(b\)

  符号：\(a \vee b\)
  含义：有 \(a\) 也有 \(b\)。

• 非 \(a\)

  符号：\(\urcorner a\)
  含义：\(a\) 的对立面。
  举例：\(a \ge 0\)，那么 \(\urcorner a < 0\)

定义

完成一件事有两类不同方案，在第一类方案中有 \(m\) 种不同的方法，在第二类方案中有 \(n\) 中不同的方法，那么一共有 \(N=m+n\) 种不同的方案。

注意：
方案一和方案二中不应有重复的方法，如果有的话就应该去重。

探究思考

在第一类方案中有 \(m_1\) 种不同的方法，在第二类方案中有 \(m_2\) 种不同的方法......在第 \(n\) 类方案中有 \(m_n\) 种不同的方法，那么完成这件事一共有多少种不同的方法？

\(N = m_1 + m_2 + m_3 + ... + m_n = \sum\limits_{i=1}^{n} m_i\)

分步乘法计数原理

引子

• 题干

  用前六个大写英文字母和 \(1 ~ 9\) 这九个阿拉伯数字给座位编号，共有多少种不同的号码？

• 解决

  由于前六个英文字母中的任意一个都能与九个数字中的任意一个组成一个号码，而且他们互不相同，因此共有 \(N = 9 + 9 + 9 + 9 + 9 + 9 = 6 \times 9 = 54\) 种不同的号码。

• 思路

  1. 六大类，每一类分别有九种。
  2. 分步数

定义

完成一件事需要两个步骤，做第一步有 \(m\) 种不同的方法，做第二步有 \(n\) 中不同的方案，那么完成这件事共有 \(N = m \times n\) 种不同的方法。