集合
计数原理
计数原理是组合数学中的基本原则，用于系统地计算事件发生的总数。主要包括两个核心原则：加法原理和乘法原理。
加法原理
概念
当有几种互斥的方式可以完成一件事情时，事情的总完成方式数等于各个方式数的总和。
例子
如果你要从成都去上海，有乘火车、坐飞机这两种交通方式可供选择，而乘火车以有 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
两种方法：
- 方法一，4 个位置选 2 个放甲乙，剩下的全排列；
- 方法二，先排剩下的，再把甲乙插空（注意，甲乙还可以相邻）
对于 2
隔板法
例：10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？
![[CleanShot 2024-08-29 at 13.13.06.png]]