1 概念与定义
1.1 序列、下标与相对顺序
在离散数学中，序列通常指按顺序排列的一串元素，可写作 \(a_1,a_2,\dots,a_n\)。这里的关键不是元素本身的值，而是它们在序列中的位置关系。用下标表示位置时，若 \(i<j\)，则元素 \(a_i\) 在原序列中出现在 \(a_j\) 之前。子序列讨论的核心约束就是：保留元素的相对先后次序。
1.2 子序列的形式化定义
给定序列 \(a_1,a_2,\dots,a_n\)，从中删去若干元素（也可以不删）得到的新序列称为它的一个子序列。形式上，子序列可由一组严格递增的下标 \[ 1\le i_1<i_2<\cdots<i_k\le n \] 选取，其结果为 \[ a_{i_1},a_{i_2},\dots,a_{i_k}. \] 这一定义强调：下标必须严格递增，因此得到的子序列在原序列中对应的元素始终从左到右抽取。
1.3 真子序列与恰当子序列
当抽取的下标集合不等于全部下标 \(\{1,2,\dots,n\}\) 时，得到的子序列不会包含所有元素，此时称为真子序列或恰当子序列。直观理解是：至少删掉了一个元素，因此长度严格小于原序列长度。
1.4 空子序列与全子序列
- 空子序列：允许删去全部元素，因此可以得到长度为 0 的序列。
- 全子序列：不删任何元素，相当于选择下标 \(i_t=t\)，得到原序列本身。
这两类是子序列概念的边界情形，在计数与证明中常被一并纳入，以避免遗漏。
2 基本性质
2.1 子序列与原序列的关系
任何子序列都可以视为原序列通过“删除操作”得到的结果。反向也成立：一个序列若能通过在原序列中删去部分元素得到，就可判定它是原序列的子序列。因而子序列关系可被看作一种“包含于结构中的可达性”。
2.2 与“子串/子段”的区分
在离散数学与算法中，“子序列（subsequence）”与“子串/子段（substring/subarray）”经常被混淆：
- 子序列只要求保持相对顺序，允许跳过中间元素；
- 子串/子段通常要求连续：下标必须是相邻区间。
例如序列 \(1,2,3,4\) 中，\(1,3,4\) 是子序列，但不是任何连续子段；而 \(2,3\) 是子段也是子序列。
2.3 长度、包含关系与传递性
- 长度：若选择了 \(k\) 个下标，则子序列长度为 \(k\)。因此子序列集合会按长度分层。
- 包含关系：子序列往往不具有像集合那样的直接包含（因为位置不同），但可以讨论“在原序列中出现”的关系。
- 传递性：若 \(B\) 是 \(A\) 的子序列，且 \(C\) 是 \(B\) 的子序列，则 \(C\) 也是 \(A\) 的子序列。原因是：\(C\) 的下标选择最终可以合并为 \(A\) 中的一组严格递增下标。
2.4 可交换性：为何顺序不能乱
子序列的“可交换性”通常不成立：你不能任意调整抽取到的元素位置。即便元素值相同，只要它们在原序列中出现的先后不同，那么得到的下标序列也可能不同，从而影响后续匹配或计数。子序列的本质约束就是保序抽取，而不是重排。
3 计数与组合视角
3.1 选取下标的计数思路
当序列中元素之间没有进一步约束时，一个最直接的计数思路是：子序列数量等于可选下标集合的数量。因为每个位置要么被选入、要么被删除，而且选入后必须保持递增次序；一旦选定下标集合，顺序就由下标自动确定。 因此长度为 \(n\) 的序列，其子序列总数（包含空子序列与全子序列）为 \[ 2^n, \] 因为每个位置独立地“选/不选”。
3.2 有重复元素时的子序列差异
若序列含有重复值，仍然可以用“下标选择”定义子序列：选入的具体位置不同，就对应不同的子序列实例。即使数值序列看起来相同，不同的下标组合也可能产生不同实例。 在计数时需要区分两种口径：
- 按下标选择计数（通常对应算法与组合证明）；
- 按数值序列内容计数（可能因重复而合并）。
目录中的基本框架更接近前者，即把子序列视为由下标决定的结果。
3.3 子序列数量的上界与精确表达
- 上界：由于总子序列数为 \(2^n\)，因此任何受限子序列的数量都不可能超过该值。
- 精确表达：若进一步限制子序列长度为 \(k\)，则只需在 \(n\) 个下标中选出 \(k\) 个严格递增的下标集合，得到
\[ \binom{n}{k}. \] 于是“长度分布”由二项系数给出。
3.4 受约束的子序列计数概览
当子序列还要满足额外条件（如单调性、与目标模式匹配、满足某个和/积约束等）时，计数问题通常不再是简单的组合数，可能需要动态规划、状态转移或更复杂的组合工具。概览上，这类问题常被归为：对“满足条件的下标选择”进行计数，而条件往往让不同下标之间产生依赖。
4 常见特例与相关概念
4.1 子序列与子集（从序列到集合的映射）
从形式上看，“子序列”由一个下标子集决定。将下标集合 \(S\subseteq\{1,\dots,n\}\) 映射为取出的元素序列，可视作从集合选择到序列结果的映射。此时子序列并不等同于子集本身，但二者联系紧密：子序列的不同实例与下标子集一一对应。
4.2 子序列与子序列集合（集合论表述）
可以把所有子序列的集合记作 \(\mathrm{Subseq}(A)\)。在该集合中，每个成员都对应一组合法下标选择。需要注意：若允许重复值，则“集合论意义下去重”与“组合意义下区分不同下标”可能产生差异；因此在数学讨论中应明确采用哪种等价标准。
4.3 作为部分有序关系的比较对象
子序列关系可与部分有序关系联系起来：给定两个序列 \(B\) 与 \(A\)，若 \(B\) 是 \(A\) 的子序列，则可视作一种“较小/包含于结构之中”的关系。它通常满足反身性与传递性，但不一定具备对称性，因此更符合偏序而非全序的直觉框架。
4.4 最长递增子序列（LIS）引出
最长递增子序列（LIS, Longest Increasing Subsequence）是最经典的“受约束子序列”问题之一：在给定序列中，寻找一个长度最大的严格递增子序列。它体现了子序列概念与优化思想的结合，也是后续算法章节的核心动机。
5 算法与应用（离散数学视角）
5.1 动态规划：最长递增子序列思路框架
动态规划处理子序列问题时常采用“以某个位置结尾”的状态定义。以 LIS 为例，常见思路是令状态表示：在位置 \(i\) 作为末尾时，能够得到的最长严格递增子序列长度。状态转移通常枚举更早的位置 \(j<i\)，若满足 \(a_j<a_i\)，就可把以 \(j\) 结尾的最优结果扩展到 \(i\)。 整体框架的要点在于：
5.2 贪心与二分（LIS的常见优化路线）
在 LIS 的进一步优化中，常用贪心思想维护“长度为某值的递增序列的最优结尾”。搭配二分查找，可以在不直接枚举所有转移的情况下更新结构，从而把复杂度降低。该方法的关键直觉是：对相同长度的候选序列，选择“结尾尽可能小”的版本更有利于后续扩展。 虽然实现细节依赖具体定义（严格递增或非严格递增），但总体目标一致：利用结构单调性减少比较次数。
5.3 字符串中的“删除得到”关系：子序列匹配
在字符串模型里，子序列匹配常被表述为：给定字符串 \(T\)，问是否能通过删除字符从 \(S\) 中得到 \(T\)。这里子序列意味着不要求连续，只要求相对顺序保持。该关系常用于：
- 判断模式是否可由另一串“删减”得到；
- 计算在约束条件下的匹配规模；
- 作为更复杂编辑类问题的组成部分。
形式化上对应的也是下标递增选择，只是元素是字符而非一般数值。
5.4 编辑距离中的子序列相关视角（概念性介绍）
编辑距离研究将一个串变为另一个串的最少操作次数。子序列视角常出现在概念关联中：若两串存在较长的共同结构（可通过删除得到的部分一致），那么往往意味着某类“删除/保留”操作的成本会更低。尽管编辑距离的严格定义还涉及插入、替换等操作，但子序列作为“保序保留的共同骨架”经常被用来解释最优解的组成与界限。
6 扩展方向
6.1 多维序列的子序列概念（简要）
当元素具有多维属性（例如带坐标的点、带多个字段的记录）时，子序列的“保序抽取”仍然成立，但“满足递增/比较”的判定可能改为按某种偏序或比较准则进行。例如按两个坐标同时递增、或按欧氏尺度变化等。概念上仍是“选择下标保持顺序 + 对选中元素施加约束”。
6.2 有序集合中的链与子序列对应关系
在部分有序集合（poset）中，链（chain）指一组两两可比的元素。若把序列视为按出现顺序排列的元素，并用元素之间的偏序关系来判断是否“递增”，则某些“递增子序列”可以与链对应起来：选中的元素不仅保持出现先后，还满足偏序可比性。该对应关系提供了从集合论到算法问题的桥梁。
6.3 概率模型下的子序列事件（概念性）
在随机序列模型中，可以把“存在某个长度的满足条件子序列”视为事件，研究其发生概率、期望规模或渐近行为。此类分析通常利用独立性或对称性，结合组合计数与极限定理的思想，但细节会随模型（随机独立同分布、置换模型等）而变化。
6.4 工程化问题：从“找子序列”到“验证子序列”
在工程应用中，经常出现两类需求：
- 寻找：在约束下最大化某指标（如最长匹配、最长递增、最大满足条件长度）；
- 验证：给定候选序列，判断它是否为原序列的子序列，或是否与目标模式匹配。
验证问题通常可用线性扫描完成：沿原序列前进并依次匹配候选元素，成功则说明存在一组递增下标实现该子序列。
7 术语辨析与易错点（快速小抄）
7.1 子序列 vs 子串/子数组
最常见错误是把“允许跳过”误当成“必须连续”。记忆方法：子串/子段强调“连续片段”，子序列强调“序关系不变”。
7.2 严格递增 vs 非严格递增
严格递增要求 \(a_{i_1}<a_{i_2}<\cdots\)。非严格递增允许相等：\(a_{i_1}\le a_{i_2}\le\cdots\)。两者会直接影响 LIS 的计算与二分/贪心更新规则。
7.3 下标选择与元素重复的混淆
当元素重复时，不同的下标组合可能产生“看上去相同”的数值结果，但从子序列定义出发，它们仍可能被视为不同实例。因此在题目要求“计数多少种”时，必须确认计数口径是否区分下标。
7.4 “子序列像点子”——为什么不能随便重排（轻度梗）
有些新手会把子序列当成“想取就取、顺便换个顺序也行”的自由拼接。其实不行：子序列就像“点子”——灵感可以多，但一旦决定从原序列挑选元素，排列就由原来的先后顺序“定死”了。你可以删减，但不能把原本在后面的东西挪到前面去。