Longest alternating subsequence

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible. Formally, if \mathbf{x} = \{x_1, x_2, \ldots, x_n\} is a sequence of distinct real numbers, then the subsequence \{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\} is alternating (or zigzag or down-up) if : x_{i_1} > x_{i_2} \cdots x_{i_k}\qquad \text{and} \qquad 1\leq i_1 Similarly, \mathbf{x} is reverse alternating (or up-down) if : x_{i_1} x_{i_3} Note that every sequence of length 1 is both alternating and reverse alternating.

Let {\rm as}_n(\mathbf{x}) denote the length (number of terms) of the longest alternating subsequence of \mathbf{x} . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that * {\rm as}_5(5,4,3,2,1) = 2 , because there are alternating subsequences of length 2, (for example 5,4 or 5,2 or 3,1), but all subsequences of length 3 are not alternating; * {\rm as}_5(1,2,3,4,5) = 1 , because all subsequences of length 2 are not alternating.…

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible. Formally, if \mathbf{x} = \{x_1, x_2, \ldots, x_n\} is a sequence of distinct real numbers, then the subsequence \{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\} is alternating (or zigzag or down-up) if x_{i_1} > x_{i_2} \cdots x_{i_k}\qquad \text{and} \qquad 1\leq i_1 Similarly, \mathbf{x} is reverse alternating (or up-down) if x_{i_1} x_{i_3} Note that every sequence of length 1 is both alternating and reverse alternating.

Let {\rm as}_n(\mathbf{x}) denote the length (number of terms) of the longest alternating subsequence of \mathbf{x} . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that {\rm as}_5(5,4,3,2,1) = 2 , because there are alternating subsequences of length 2, (for example 5,4 or 5,2 or 3,1), but all subsequences of length 3 are not alternating; {\rm as}_5(1,2,3,4,5) = 1 , because all subsequences of length 2 are not alternating.

(actually, they are reverse alternating); {\rm as}_5(5,1,3,4,2) = 4, because 5,1,3,2 and 5,1,4,2 and 5,3,4,2 are all alternating, and there is no alternating subsequence with more elements; {\rm as}_5(4,3,5,1,2) = 5, because 4,3,5,1,2 is itself alternating. E[A_n] = \frac{2 n}{3} + \frac{1}{6} \qquad \text{and} \qquad \operatorname{Var}[A_n] = \frac{8 n}{45} - \frac{13}{180}.

Moreover, as n \rightarrow \infty , the random variable A_n , appropriately centered and scaled, converges to a standard normal distribution.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369239592 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.