离散数学-计数理论

在日常生活中，很多时候我们需要找出一系列事件所有可能结果的数量。例如，从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$ 方式（总和规则）。此后，他可以从 Y 到 Z $4 + 5 = 9$ 方式（总和规则）。因此从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

排列数

一次采用“r”的“n”个不同事物的排列数表示为 $n_{P_{r}}$

n_{P_{r}} = \frac{n!}{(n - 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 footer{
text-align:center;
padding:30px;
}
footer a{
color:white}$

TutorialSpoint在线教程