Longest increasing and decreasing subsequences
C Schensted - Canadian Journal of mathematics, 1961 - cambridge.org
C Schensted
Canadian Journal of mathematics, 1961•cambridge.orgThis paper deals with finite sequences of integers. Typical of the problems we shall treat is
the determination of the number of sequences of length n, consisting of the integers 1, 2,…,
m, which have a longest increasing subsequence of length α. Throughout the first part of the
paper we will deal only with sequences in which no numbers are repeated. In the second
part we will extend the results to include the possibility of repetition. Our results will be stated
in terms of standard Young tableaux.
the determination of the number of sequences of length n, consisting of the integers 1, 2,…,
m, which have a longest increasing subsequence of length α. Throughout the first part of the
paper we will deal only with sequences in which no numbers are repeated. In the second
part we will extend the results to include the possibility of repetition. Our results will be stated
in terms of standard Young tableaux.
This paper deals with finite sequences of integers. Typical of the problems we shall treat is the determination of the number of sequences of length n, consisting of the integers 1, 2, … , m, which have a longest increasing subsequence of length α. Throughout the first part of the paper we will deal only with sequences in which no numbers are repeated. In the second part we will extend the results to include the possibility of repetition. Our results will be stated in terms of standard Young tableaux.
Cambridge University Press