This site is supported by donations to The OEIS Foundation.

Subsequence

From OeisWiki
Jump to: navigation, search


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


A sequence is a subsequence of if there are indices such that

In other words, a subsequence of a sequence s is s with some (possibly none) terms omitted.[1] 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.

Notes

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, 2001, ISBN 0-262-03293-7, p. 350


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]