89 lines
3.8 KiB
Markdown
89 lines
3.8 KiB
Markdown
# 组合数学
|
||
|
||
### 我的错误
|
||
|
||
我搞了很久在想自己在这个问题上放的错误。原始错误是，m+n长度路径，应该选择（n-1）个情况进行选择，因为最右的点只有一个选择。
|
||
真的是错得离谱了。正确理解应该是程度为m+n的长度上，选择在m或者n的次序上改变方向。
|
||
|
||
那我就整体回顾一下组合数学吧。
|
||
|
||
### 另一条路
|
||
|
||
[整数序列 A000984](https://oeis.org/A000984) 。这里也有这个的详细说明和讨论。
|
||
|
||
### 组合数学概念速览
|
||
|
||
组合数学（Combinatorics）是研究离散对象的计数、排列、组合及结构关系的数学分支，广泛应用于计算机科学、统计学、密码学等领域。其核心思想是**系统化地处理有限结构的排列与选择问题**，以下是其核心原理和关键定理的概述：
|
||
|
||
#### **一、基本原理**
|
||
1. **加法原理**
|
||
若完成一项任务有 \(m\) 种互斥的方法，另一种任务有 \(n\) 种方法，则选择其中一种任务的方法数为 \(m+n\)。
|
||
**示例**：从3本数学书和4本历史书中选一本，有 \(3+4=7\) 种选法。
|
||
|
||
2. **乘法原理**
|
||
若完成一项任务需连续执行多个步骤，第一步有 \(m\) 种方法，第二步有 \(n\) 种方法，则总方法数为 \(m \times n\)。
|
||
**示例**：从3件上衣和2条裤子搭配，有 \(3 \times 2=6\) 种搭配。
|
||
|
||
#### **二、关键定理与公式**
|
||
1. **排列与组合**
|
||
- **排列**（顺序相关）：
|
||
\(n\) 个不同元素取 \(r\) 个排列：
|
||
\[
|
||
P(n,r) = \frac{n!}{(n-r)!}
|
||
\]
|
||
- **组合**（顺序无关）：
|
||
\(n\) 个不同元素取 \(r\) 个组合：
|
||
\[
|
||
C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}
|
||
\]
|
||
|
||
2. **二项式定理**
|
||
展开二项式幂的关键公式：
|
||
\[
|
||
(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k}
|
||
\]
|
||
组合数 \(\binom{n}{k}\) 称为**二项式系数**，体现在杨辉三角（帕斯卡三角）中。
|
||
|
||
3. **鸽巢原理（抽屉原理）**
|
||
将 \(n\) 个物品放入 \(m\) 个容器，若 \(n>m\)，则至少有一个容器包含至少两个物品。
|
||
**应用**：证明重复性存在（如生日悖论）。
|
||
|
||
4. **容斥原理**
|
||
计算多个集合的并集大小，避免重复计数：
|
||
\[
|
||
|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|
|
||
\]
|
||
**应用**：错排问题、素数计数。
|
||
|
||
5. **生成函数**
|
||
将序列转化为形式幂级数，化组合问题为代数问题。例如，求组合数时：
|
||
\[
|
||
(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k
|
||
\]
|
||
普通生成函数用于计数，指数生成函数用于排列问题。
|
||
|
||
6. **卡特兰数**
|
||
定义：
|
||
\[
|
||
C_n = \frac{1}{n+1} \binom{2n}{n}
|
||
\]
|
||
应用于括号匹配、二叉树计数、网格路径问题。
|
||
|
||
7. **斯特林数**
|
||
- **第二类斯特林数** \(S(n,k)\)：将 \(n\) 个不同元素划分为 \(k\) 个非空集合的方法数。
|
||
- **第一类斯特林数**：与轮换排列相关。
|
||
|
||
8. **波利亚计数定理**
|
||
考虑对称性下的计数问题，用于染色、图形枚举等场景。
|
||
|
||
#### **三、核心思想**
|
||
- **一一对应**：将复杂计数映射到已知模型（如将组合问题转化为方程整数解个数）。
|
||
- **递归与递推**：通过子问题构造关系式（如斐波那契数列、错排公式）。
|
||
- **对称性与分类讨论**：利用对称性简化问题，对不重不漏的分类要求严格。
|
||
|
||
#### **四、应用领域**
|
||
- **算法设计**：分析算法复杂度（如动态规划状态数）。
|
||
- **图论**：树、图的计数与结构分析。
|
||
- **编码理论**：纠错码的构造与组合设计。
|
||
- **概率论**：古典概型中的样本空间计数。
|