---
title: "离散与组合数学"
description: "离散与组合数学等竞赛相关数学知识。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 离散与组合数学

![](https://img.dailyup.xyz/originals/8208462119722-58398905-9685-433d-8893-e9cc165ac6e5.png)

## 集合

## 计数原理

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

### 加法原理

#### 概念

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

#### 例子

如果你要从成都去上海，有乘火车、坐飞机这两种交通方式可供选择，而乘火车以有 $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]]



## 杨辉三角


## 小结

Source: https://cppguide.xyz/maths/discrete/index.mdx