- 离散数学资源
- 离散数学 - 快速指南
- 离散数学 - 资源
- 离散数学 - 讨论
离散数学 - 计数理论
在日常生活中，我们经常需要找出某一系列事件所有可能结果的数量。例如，从50名男性和38名女性中，有多少种方法可以选择一个由6名男性和4名女性组成的评审团？可以生成多少个不同的10位数个人所得税识别号（PAN），其前五位是英文字母大写，接下来的四位是数字，最后一位又是英文字母大写？为了解决这些问题，我们使用数学计数理论。计数主要包括基本计数规则、排列规则和组合规则。
加法规则和乘法规则
加法规则和乘法规则用于将复杂的计数问题分解成简单的问题。
加法规则 - 如果一系列任务$T_1, T_2, \dots, T_m$分别可以用$w_1, w_2, \dots w_m$种方法完成（条件是这些任务不能同时进行），那么完成其中一项任务的方法数为$w_1 + w_2 + \dots +w_m$。如果我们考虑两个不相交的任务A和B（即$A \cap B = \emptyset$），那么在数学上$|A \cup B| = |A| + |B|$
乘法规则 - 如果一系列任务$T_1, T_2, \dots, T_m$分别可以用$w_1, w_2, \dots w_m$种方法完成，并且每个任务都在前一个任务发生后才进行，那么完成这些任务的方法数为$w_1 \times w_2 \times \dots \times w_m$。在数学上，如果任务B在任务A之后进行，则$|A \times B| = |A|\times|B|$
示例
问题 - 一个男孩住在X地，想去Z地的学校。他必须先从家X到达Y地，然后再从Y地到达Z地。他可以乘坐3条公交线路或2条火车线路从X地到达Y地。从那里，他可以选择4条公交线路或5条火车线路到达Z地。从X地到Z地有多少种方法？
解答 - 从X地到Y地，他可以有$3 + 2 = 5$种方法（加法规则）。然后，他可以有$4 + 5 = 9$种方法从Y地到Z地（加法规则）。因此，从X地到Z地，他可以有$5 \times 9 = 45$种方法（乘法规则）。
排列
排列是某些元素的一种排列方式，其中顺序很重要。换句话说，排列是元素的有序组合。
示例
从集合S ={x, y, z}中每次取两个元素，所有排列为：
$xy, yx, xz, zx, yz, zy$。
我们必须从数字集合$S = \lbrace 1, 2, 3 \rbrace$中组成一个三位数的排列。当我们排列这些数字时，将形成不同的三位数。排列将是 = 123, 132, 213, 231, 312, 321
排列数
从'n'个不同的元素中取'r'个元素的排列数记为$n_{P_{r}}$
$$n_{P_{r}} = \frac{n!}{(n - r)!}$$
其中 $n! = 1.2.3. \dots (n - 1).n$
证明 - 假设有'n'个不同的元素。
有n种方法填充第一个位置。填充第一个位置后，剩下(n-1)个元素。因此，有(n-1)种方法填充第二个位置。填充第一个和第二个位置后，剩下(n-2)个元素。因此，有(n-2)种方法填充第三个位置。现在我们可以将填充第r个位置的方法数推广为[n – (r–1)] = n–r+1
所以，从第一个位置到第r个位置的填充方法总数为：
$n_{ P_{ r } } = n (n-1) (n-2)..... (n-r + 1)$
$= [n(n-1)(n-2) ... (n-r + 1)] [(n-r)(n-r-1) \dots 3.2.1] / [(n-r)(n-r-1) \dots 3.2.1]$
因此，
$n_{ P_{ r } } = n! / (n-r)!$
一些重要的排列公式
如果有n个元素，其中$a_1$个是某种类型的相同元素，$a_2$个是另一种类型的相同元素；$a_3$个是第三种类型的相同元素，以此类推，$a_r$个是第$r$种类型的相同元素，其中$(a_1 + a_2 + ... a_r) = n$。
那么，这n个对象的排列数为 = $n! / [(a_1!(a_2!) \dots (a_r!)]$。
从n个不同的元素中取n个元素的排列数 = $n_{P_n} = n!$
从n个不同元素中取r个元素的排列数，当x个特定元素总是占据特定位置时 = $n-x_{p_{r-x}}$
当r个指定元素总是放在一起时，n个不同元素的排列数为 − $r! (n−r+1)!$
当r个指定元素永远不会放在一起时，n个不同元素的排列数为 − $n!–[r! (n−r+1)!]$
从n个不同元素中取x个元素的环状排列数 = $^np_{x}/x$
n个不同元素的环状排列数 = $^np_{n}/n$
一些问题
问题1 - 从一堆6张不同的卡片中，有多少种方法可以排列它们？
解答 - 因为我们一次从6张卡片中取6张卡片，所以排列数为$^6P_{6} = 6! = 720$
问题2 - 单词'READER'的字母有多少种排列方式？
解答 - 单词'READER'是一个6个字母的单词（2个E，1个A，1个D和2个R）。
排列数将是 $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$
问题3 - 单词'ORANGE'的字母有多少种排列方式，使得辅音只占据偶数位置？
解答 - 单词'ORANGE'中有3个元音和3个辅音。辅音本身的排列方式数量 = $^3P_{3} = 3! = 6$。剩余的3个空位将用3个元音填充，有$^3P_{3} = 3! = 6$种方法。因此，排列总数为$6 \times 6 = 36$
组合
组合是一些给定元素的选择，其中顺序无关紧要。
从n个元素中取r个元素的所有组合数为：
$$^nC_{ { r } } = \frac { n! } { r!(n-r)! }$$
问题1
求集合$\lbrace1, 2, 3, 4, 5, 6\rbrace$中含有3个元素的子集个数。
解答
集合的基数为6，我们必须从集合中选择3个元素。这里，顺序无关紧要。因此，子集个数为$^6C_{3} = 20$。
问题2
一个房间里有6名男性和5名女性。有多少种方法可以选择3名男性和2名女性？
解答
从6名男性中选择3名男性的方法数为$^6C_{3}$，从5名女性中选择2名女性的方法数为$^5C_{2}$
因此，方法总数为 − $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$
问题3
从总共9名学生中选择3个不同的3人小组有多少种方法？
解答
我们将小组编号为1、2和3
为第一个小组选择3名学生的方法数 − $^9C_{3}$
在选择第一个小组后，为第二个小组选择3名学生的方法数 − $^6C_{3}$
在选择第一个和第二个小组后，为第三个小组选择3名学生的方法数 − $^3C_{3}$
因此，方法总数 $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$
帕斯卡恒等式
帕斯卡恒等式，最早由布莱斯·帕斯卡在17世纪推导出来，指出从n个元素中选择k个元素的方法数等于从(n-1)个元素中选择(k-1)个元素的方法数与从n-1个元素中选择k个元素的方法数之和。
在数学上，对于任何正整数k和n：$^nC_{k} = ^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$
证明 −
$$^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$$
$= \frac{ (n-1)! } { (k-1)!(n-k)! } + \frac{ (n-1)! } { k!(n-k-1)! }$
$= (n-1)!(\frac{ k } { k!(n-k)! } + \frac{ n-k } { k!(n-k)! } )$
$= (n-1)! \frac{ n } { k!(n-k)! }$
$= \frac{ n! } { k!(n-k)! }$
$= n_{ C_{ k } }$
鸽巢原理
1834年，德国数学家彼得·古斯塔夫·勒热纳·狄利克雷提出了一种他称之为抽屉原理的原理。现在，它被称为鸽巢原理。
鸽巢原理指出，如果鸽子的数量少于鸽巢的数量，并且每只鸽子都被放入一个鸽巢中，那么至少有一个鸽巢中不止一只鸽子。如果n只鸽子被放入m个鸽巢中，其中n > m，那么至少有一个鸽巢中不止一只鸽子。
示例
十个人在一个房间里，他们正在进行握手。如果每个人至少握手一次，并且没有人与同一个人握手不止一次，那么两个人进行了相同次数的握手。
在一个30人的班级中，至少有两名学生的姓名以相同的字母开头。
容斥原理
容斥原理用于计算多个非不相交集合的并集的基数。对于两个集合A和B，该原理指出：
$|A \cup B| = |A| + |B| - |A \cap B|$
对于三个集合A、B和C，该原理指出：
$|A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C |$
其一般公式为：
$|\bigcup_{i=1}^{n}A_i|=\sum_{i=1}^n |A_i| - \sum\limits_{1\leq i<j\leq n}|A_i \cap A_j|+\sum\limits_{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k|- \dots +(-1)^{\n-1}|A_1 \cap \dots \cap A_n|$
问题1
从1到50的整数中，有多少个是2或3的倍数，但不是两者兼而有之的？
解答
从1到50，有 $50/2 = 25$ 个是2的倍数。
有 $50/3 = 16$ 个是3的倍数。
有 $50/6 = 8$ 个同时是2和3的倍数。
因此，$|A|=25$，$|B|=16$，$|A \cap B|= 8$。
$|A \cup B| = |A| + |B| - |A \cap B| = 25 + 16 - 8 = 33$
问题2
在一个有50名学生的群体中，24人喜欢冷饮，36人喜欢热饮，每个学生至少喜欢其中一种饮料。有多少人既喜欢咖啡又喜欢茶？
解答
设X为喜欢冷饮的学生集合，Y为喜欢热饮的学生集合。
因此，$| X \cup Y | = 50$，$|X| = 24$，$|Y| = 36$
$|X \cap Y| = |X| + |Y| - |X \cup Y| = 24 + 36 - 50 = 10$
因此，有10名学生既喜欢咖啡又喜欢茶。