Appearance
函数是特殊的关系，是刻画映射与计数的核心工具。本笔记梳理函数的定义、单射/满射/双射、复合与逆函数，以及函数计数模型（与排列组合衔接）。
函数的基本概念
定义
函数 f: A→B：A 中每个元素恰好对应 B 中一个元素（关系 + 单值性）。A 为定义域，B 为陪域，f(A) 为值域。
- 函数是关系：f ⊆ A×B，且 ∀x∈A，存在唯一 y∈B 使 (x,y)∈f
- |A|=m, |B|=n 时，函数总数 = n^m
三种特殊函数（核心考点）
| 类型 | 定义 | 计数（|A|=m, |B|=n） | |------|------|---------------------| | 单射 | 不同 x 对应不同 y（一一对应到值域） | P(n,m) = n!/(n−m)!（需 n≥m） | | 满射 | 每个 y∈B 至少被一个 x 对应 | 容斥原理计算（见下） | | 双射 | 既是单射又是满射 | n!（需 n=m） |
记忆：单射 = 排列数 P(n,m)（"每人占一个不同位置"）；双射要求 |A|=|B|。
相关概念
- 常函数：所有 x 对应同一个 y
- 恒等函数 IA：每个 x 对应自身
- 单调递增/递减函数、严格单调函数：可用非降路径计数（C(n,m)）
复合函数与逆函数（考点）
复合函数
(f∘g)(x) = f(g(x))，要求 g 的值域 ⊆ f 的定义域。结合律成立：(f∘g)∘h = f∘(g∘h)。
逆函数
f⁻¹ 存在（f 可逆）当且仅当 f 是双射。此时 f⁻¹: B→A 满足 f⁻¹(y)=x ⇔ f(x)=y。
常见错误：只有双射才有逆函数。单射或满射都不能直接求逆。
重要性质
- 若 f, g 都是单射，则 f∘g 是单射；满射的复合是满射；双射的复合是双射
- (f∘g)⁻¹ = g⁻¹∘f⁻¹（先内后外取逆）
函数计数与组合模型
从 A={1,…,m} 到 B={1,…,n} 的函数分类计数：
| 函数类型 | 计数公式 | 对应组合模型 |
|---|---|---|
| 单射 | P(n,m) | 排列 |
| 满射 | n!·S(m,n)（第二类 Stirling 数） | 放球（球不同盒相同） |
| 双射 | n!（n=m） | 排列 |
| 单调函数 | 2·C(n+m−1, m) 等 | 非降路径 |
| 严格单调 | C(n,m) | 选取 |
一句话总结
函数 = 单值关系；单射是"排列"、双射才有逆；函数计数把函数问题翻译成排列组合问题（非降路径、放球模型）。