子列

子序列
术语名称	子序列
英语名称	subsequence
别名	子列

子序列(subsequence)简称子列，指一个序列中部分元素按原顺序排列得到的新序列。 子列元素不要求在原序列中连续，但是新序列中的顺序需要与原序列中的顺序相同。

也可以认为子列是原序列中不改变顺序地删除部分元素得到的序列。

定义

子列关系
关系名称	子列关系
关系符号
Latex
关系对象	序列
关系元数	2
类型	偏序

对无穷序列，序列 [math]\displaystyle{ a_1,a_2,\dots }[/math] 和序列 [math]\displaystyle{ b_1,b_2,\dots }[/math] ，若存在一组正整数下标 [math]\displaystyle{ i_1,i_2,\dots }[/math] 满足 [math]\displaystyle{ 1\leq i_1\lt i_2\lt \cdots }[/math] 且使得 [math]\displaystyle{ b_j = a_{i_j} }[/math] ，则称序列 [math]\displaystyle{ b_1,b_2,\dots }[/math] 为序列 [math]\displaystyle{ a_1,a_2,\dots }[/math] 的子列(subsequence)。

对有限序列，序列 [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math] 和序列 [math]\displaystyle{ b_1,b_2,\dots,b_m }[/math] ，若存在一组正整数下标 [math]\displaystyle{ i_1,i_2,\dots,i_m }[/math] 满足 [math]\displaystyle{ 1\leq i_1\lt i_2\lt \cdots\lt i_m\leq n }[/math] 且使得 [math]\displaystyle{ b_j = a_{i_j} }[/math] ，则称序列 [math]\displaystyle{ b_1,b_2,\dots,b_m }[/math] 为序列 [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math] 的子列(subsequence)。

说明：

• 定义中“存在一组正整数下标 [math]\displaystyle{ 1\leq i_1\lt i_2\lt \cdots }[/math] ”也被描述为“存在下标间的严格单调递增的映射 [math]\displaystyle{ f:j\mapsto i_j }[/math] ”。
• 定义也常常描述为：序列 [math]\displaystyle{ a_{i_1},a_{i_2},\dots }[/math] 为序列 [math]\displaystyle{ a_1,a_2,\dots }[/math] 的子列，要求其中 [math]\displaystyle{ 1\leq i_1\lt i_2\lt \cdots }[/math] ，是一组严格递增的正整数下标。

性质

• 子列关系是一种偏序。