Longest Increasing and Decreasing Subsequences

1961/01/01 by C. Schensted · 7 citations
Computer Science · Mathematics · #Coding theory and cryptography #Analytic Number Theory Research #Advanced Combinatorial Mathematics #Subsequence #Mathematics #Repetition (rhetorical device) #Longest increasing subsequence #Combinatorics #Longest common subsequence problem #Discrete mathematics #Arithmetic #Mathematical analysis #Linguistics

paper · pdf · doi:10.4153/cjm-1961-015-3

openalex publication_date 1961/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Abstract

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.

Citations

• The Hook Graphs of the Symmetric Group

Cited by

• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Hardness of Median and Center in the Ulam Metric
• On the distribution of the length of the longest increasing subsequence of random permutations
• Classic Papers in Combinatorics
• Bigrassmannian permutations and Verma modules
• On the Representation Theory of the Finite Groups of Lie Type over an Algebraically Closed Field of Characteristic 0
• Longest increasing subsequence [wikipedia]