Subsequence

This article page is a stub, please help by expanding it.

A sequence $\scriptstyle \{a_{i}\}_{i_{\min }}^{i_{\max }}\,$ is a subsequence of $\scriptstyle \{b_{j}\}_{j_{\min }}^{j_{\max }}\,$ if there are indices $\scriptstyle \{k_{i}\}_{i_{\min }}^{i_{\max }}\,$ such that

$a_{i}=b_{k_{i}},\quad \forall k_{i}\in [j_{\min },\,j_{\max }].\,$

In other words, a subsequence of a sequence s is s with some (possibly none) terms omitted. This is similar to the subset concept except that order and multiplicity matter, since a sequence is ordered. Substrings are (typically finite) subsequences with all terms adjacent. The rarely-used submultiset (subbag) considers multiplicity but not order.

Sequences are preordered by the subsequence relation. This becomes a partial order if only monotonic sequences are considered.

Cite this page as

Charles R Greathouse IV, Subsequence.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Subsequence]