计数原理

计数原理是计数的根本规则；它通常归类于排列规则和组合规则。它指出，如果一个工作 X 可以有 m 种方式完成，工作 Y 可以有 n 种方式完成，那么假设 X 和 Y 是互斥的，完成 X 和 Y 的方式数量是 m x n。例如，假设一个人（T）可以乘公交车、步行和骑自行车从家去市场，即 T = 3；如果他乘步行和汽车回家（B），即 B = 2。那么 TB 可以有 3*2 = 6 种方式完成。

加法原理和乘法原理

加法原理和乘法原理如下给出。

加法原理（加法原理）

如果若干个任务 P1, P2, P3………, Pm 分别可以有 K1, K2, K3…. Km 种方式完成，且这些任务不能同时执行，那么完成其中一个任务的方式数量为

K1 + K2 + ………… + Km。

假设两个不同的任务 P 和 Q，它们是不相交的，意味着 P ∩Q = Ø

数学上，

|P∪Q|=|P|+|Q|

乘法原理（乘法规则）

如果若干个任务 P1, P2, P3,…………, Pm 分别可以有 K1, K2, K3,………..Km 种方式完成，并且每个任务都发生在前一个任务发生之后，那么完成其中一个任务的方式数量为

K1 x K2 x ………… x Km。

数学上，

如果任务 Q 发生在任务 P 之后，则

|P x Q|=|P| x |Q|

示例 1

一名员工住在 K 地，想去 G 地的办公室。从他的家 K，他必须先到达 B 地，然后从 B 到 G。他可以从 K 到 B，选择四条地铁路线或三条公交路线。从那里，他可以选择六条地铁路线或四条公交路线到达 G 地。找出从 K 到 G 的方式数量。

解决方案

他可以有 4 + 3 = 7 种方式（加法原理）。之后，他可以从 B 到 G，有 6 + 4 = 10 种方式（加法原理）。因此，从 K 到 G，他可以有 7 * 10 = 70 种方式（乘法原理）。

排列

排列是指以特定方式排列元素。例如

我们必须从数字集 S = (5, 7) 中形成两位数的排列。当我们排列给定的数字时，将形成不同的两位数。排列将是 = (5,7) 和 (7,5)。

示例 1

从集合 S = (P, Q, R) 中，每次取两个的全部排列是

pq, qp, pr,rp,qr,rq

示例 2

我们必须从集合 S = (H, T) 中形成两位硬币的排列。当我们排列两个面时，将形成不同的两面。排列将是

(H, T) 和 (T, H)

排列的数量

从 n 个不同对象中取 r 个进行排列的数量为

P(n,r) = n(n-1) (n-2)………(n-r-1) (n≥r) = n! / (n-r)!

其中，

n! = 1.2.….(n-1).n

注意：n 总是大于或等于 r，这也等同于 n 的阶乘除以 n 减去 r 的阶乘。

排列公式证明

假设有三个空箱子，你需要用三种不同的颜色填充它们。填充第一个箱子有 n 种方式。填充第一个箱子后（n-1），剩下（n-1）个箱子。因此，第二个位置的颜色填充有（n-1）种方式。填充第一个和第二个位置后，剩下（n-2）个箱子。因此，用不同颜色填充第三个位置有（n-2）种方式。现在，我们可以将填充第 r 个箱子的总方式数推广为

[n - (r-1)] = n-r+1

因此，从第一个位置到第 r 个位置填充颜色的总方式数为

n_pr=n(n-1) (n-2) .... (n-r+1)

n_pr= [n(n-1) (n-2) ...(n-r+1)] [(n-r) (n-r-1) …3.2 .1]/[(n-r) (n-r-1) …3.2.1]

故，

=n! /(n-r)!

排列中需要记住的点

• 如果有 'n' 个不同的元素，其中 x1 个是某种类型的，x2 个是另一种类型的，X3 个是第三种类型的，Xr 是第 r 种类型的，其中
  (x1 + x2 + x3+ …………. xr) = n
  那么，这 n 个对象的排列数量是
  n! / [(x1! (x2!) …(xr!)]
• 从 n 个不同元素中取 "n" 个元素进行排列的数量
  n_pn=n!
• 从 n 个不同元素中取 r 个元素进行排列的数量，当 m 个特定事物始终占据固定位置时
  n-m_pr-m
• 当 r 个特定事物始终在一起时，n 个不同对象的排列数量为
  r! (n-r+1)!
• 当 r 个特定事物永远不在一起时，n 个不同对象的排列数量为
  n! - [r! (n-r+1)!]
• n 个不同对象取 x 个元素进行排列的圆周排列数量
  n_px/x
• n 个不同事物进行圆周排列的数量
  

  n_pn/n

让我们通过例子来理解这个概念

示例 1

单词 "SCISSORS" 的字母有多少种排列方式？

解决方案

单词 SCISSORS 中有八个字母（4 个 S，1 个 C，1 个 I，1 个 O，1 个 R）。

排列将是 =

8! / [(4!) (1!) (1!) (1!)] = 1680

示例 2

单词 "GOOD" 的字母有多少种排列方式？

解决方案

单词 GOOD 中有 4 个字母（1 个 G，2 个 O，1 个 D）。

排列将是 =

4! / [(1!) (2!) (1!)] = 12

示例 3

从 4 张不同的卡片中，有多少种排列方式？

解：因为我们从一副 4 张牌中取 4 张牌。排列将是

4_p4= 4! = 24

示例 4

单词 'READER' 的字母如何排列，才能使辅音只占据偶数位置？

解决方案

单词 'READER' 中有 3 个元音和 3 个辅音。辅音之间的排列方式有 3_p3= 3! = 6 种。3 个元音将填补剩余的 3 个空位，有 3_p3= 3! = 6 种方式。因此，总排列数量是 6×6=36。

组合

组合是指从一个集合中选择元素，其中选择的顺序不重要，这与排列不同。

在组合中，我们通常只考虑选择。选定元素的顺序不重要。通常，组合的数量大于排列的数量。每个组合对应于许多排列。

从 n 个不同事物中取 r 个进行组合的数量为

n_Cr=n! /r! (n-r)!

示例 1

找出集合 {1,2,3,4,5,6,7} 中具有 4 个元素的子集的数量。

解决方案

集合的基数为 7，我们必须从集合中选择 4 个元素。

这里，数字的顺序不重要。因此，子集的数量将是

n_Cr =n! / r! (n-r)!

7_C4 =7! / 4! (7-4)!

= 7 * 6 * 5/ 3 *2 = 35

示例 2

有 8 个男孩和 6 个女孩参加了一场比赛。有多少种方式可以从比赛中选出 4 个男孩和 3 个女孩？

解决方案

从 8 个男孩中选出 4 个男孩的方式是 8_C4，从 6 个女孩中选出 3 个女孩的方式是 6_Cs。

因此，总方式数量是

8_C4 6_Cs = 8! / 4! (8-4)! 6! / 3! (6-3)!

= 8 × 7 ×6 ×5/ 4 ×3 ×2 × 6×5×4 /3 ×2

= 70 × 20 = 1400

示例 4

从总共 8 名学生中，有多少种方法可以选择 4 个不同的 2 人小组？

解决方案

假设组的数量是 1、2、3 和 4。

为第一个小组选择 2 名学生的方式将是 =8_C2

选择第一个小组后，为第二个小组选择 2 名学生的方式 =6_C2

选择第一个和第二个小组后，为第三个小组选择 2 名学生的方式 =4_C2

选择第一个、第二个和第三个小组后，为第四个小组选择 2 名学生的方式 =2_C2

因此，总方式数量是

8_C2 ×6_C2 ×4_C2× 2_C2 = 28 × 15 ×6 ×1 = 2520

帕斯卡恒等式

帕斯卡恒等式由布莱兹·帕斯卡在 17 世纪首次推导出来。它指出，从 n 个不同元素中选择 k 个元素的总方式数等于从 (n-1) 个元素中选择 (k-1) 个元素的数量与从 n-1 个元素中选择元素的数量之和。

在数学上，对于任何正整数 k 和 n，我们可以写出方程

n_Ck = n-1_Ck-1 + n-1_Ck

容斥原理

容斥原理指的是一个非常基本的计数定理，各种编程竞赛中的各种问题都基于它；下面给出了容斥原理的一个基本示例。

考虑 A 是一个元素集合，|A| 是 A 中的元素数量，B 也是如此。集合 A 和 B 的元素集合的基数（当 A 和 B 都互斥时）可以表示为（对于 2 个有限集）

|AUB|=|A|+|B|

考虑集合不相交的情况。

在计算 A 和 B 的基数时，我们需要减去重复计算的共同元素，新的形式将变为

|AUB|=|A|+|B|-|A∩B|

广义公式

基于容斥原理的示例

示例 1

1 到 100 之间有多少整数是 5 的倍数，6 的倍数，但不是两者兼有的倍数？

解决方案

1 到 100 之间有 100/5 = 20 个数字是 5 的倍数。

有 100/6 = 16 个数字是 6 的倍数。

有 100/30 = 3 个数字是 5 和 6 的公倍数。

因此，

|A| = 20, |B| = 16, |A∩B| = 3

我们知道：

|AUB| =|A|+|B|-|A∩B|

= 20 + 16 -3 = 33

示例 2

在一个有 60 名员工的团队中，32 人喜欢披萨，38 人喜欢汉堡，并且每位员工至少喜欢两种零食中的一种。找出有多少员工同时喜欢披萨和汉堡？

解决方案

设 P 为喜欢披萨的员工集合，Q 为喜欢汉堡的员工集合。

因此，

|P| = 32, |Q| = 38, |PUQ| = 60

我们知道：

|AUB| =|A|+|B|-|A∩B|

所以，

|P∩Q|=|P|+|Q|-|PUQ|

= 32 + 38 - 60 = 70 - 60 = 10