#离散与组合数学

#集合

#计数原理

计数原理是组合数学中的基本原则，用于系统地计算事件发生的总数。主要包括两个核心原则：加法原理和乘法原理。

#加法原理

#概念

当有几种互斥的方式可以完成一件事情时，事情的总完成方式数等于各个方式数的总和。

#例子

如果你要从成都去上海，有乘火车、坐飞机这两种交通方式可供选择，而乘火车以有 $m$ 个班次可选；坐飞机也 $n$ 个班次可选，根据加法原理，从成都到上海共有 $m + n$ 种方式可以到达。

#乘法原理

#概念

当一件事情需要多个步骤完成，每个步骤有若干种选择，且各步骤相互独立时，总的完成方式数等于各步骤选择数的乘积。

#例子

如果你有 3 件上衣，2 条裤子，问选择一套衣服，总共有多少种搭配方式呢？

• 选择上衣有 3 种
• 选择裤子有 2 种

又如，在 C++ 中，一个字节是 8 位（bit），能表达的状态共有 $2^8=64$ 种，这也是基于乘法原理的一种结果。

根据乘法原理，选择一套衣服的总搭配数是 $3 \times 2=6$ 种搭配。

#应用场景

• 加法原理用于计算“或”的情况。
• 乘法原理用于计算“且”的情况。

计数原理为解决复杂的组合问题提供了基础方法。

#排列组合

排列组合是组合数字中的重要概念，用于计算不同情况下的元素选择方式。排列数表示为 $P(n,r)$，是指从 $n$ 个元素中选取 $r$ 个元素进行排列的方式数。$P(n,r)$ 也可以写作 $A(n,r)$ 。

排列是指从一组元素中选取一定数量的元素，需要考虑排列顺序。而组合也是从一组元素中选取一定数量的元素，但不考虑排列顺序。组合数表示为 $C(n,r)$ ，表示从 $n$ 个元素中选择 $r$ 个元素的组合方式数。

#排列

排列的计算公式如下：

$A_{n}^{m} = n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}$ 全排列是排列数的一种特殊情况。

$n$ 个人排队，第一个位置有 $n$ 种选择方式，第二位置有 $n-1$ 种，以此类推，可以得出：

$A_{n}^{n}=n(n-1)(n-1)...3 \times 2 \times 1 = n!$

例如：从 5 个人中选 3 个人排成一排，请问排列的方法数是多少？

#组合

#排列组合题型

#相邻元素捆绑法

例：有 6 个人排成一队拍照，其中甲乙两人必须相邻，请问有多少种排法？

#不相邻元素插空法

例：有 6 个人排成一队拍照，其中甲乙两人不能站在一起，请问有多少种排法？

#特殊优先法

对于特殊元素，优先处理；特殊位置，优先考虑。

例：6 人站一排拍照

1. 甲乙既不在排头也不可排尾的排法数？
2. 甲不是排头，乙不在排尾，且甲乙不相邻的排法数？

对于 1

两种方法：

1. 方法一，4 个位置选 2 个放甲乙，剩下的全排列；
2. 方法二，先排剩下的，再把甲乙插空（注意，甲乙还可以相邻）

对于 2

#隔板法

例：10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？

![[CleanShot 2024-08-29 at 13.13.06.png]]

#杨辉三角

#小结