LONGEST INCREASING AND DECREASING SUBSEQUENCES

LONGEST INCREASING AND DECREASING SUBSEQUENCES

June 23, 1959; revised form August 29, 1960 | C. SCHENSTED
This paper discusses the problem of determining the number of sequences of length n consisting of integers 1 to m that have a longest increasing subsequence of length α. It introduces the concept of standard Young tableaux and uses them to express results. The paper is divided into two parts: Part I deals with sequences without repetition, while Part II extends the results to sequences with repetition. In Part I, a standard Young tableau is defined as an arrangement of numbers in rows and columns with increasing sequences in each row and column. The shape of a tableau is the arrangement of squares corresponding to the numbers in the tableau. The number of standard tableaux of a given shape is calculated using hook lengths. The paper defines operations S ← x and x → S, which generate standard tableaux. It proves that these operations result in standard tableaux and establishes a one-to-one correspondence between sequences and ordered pairs of standard tableaux. The paper also shows that the number of columns in the P-symbol (or Q-symbol) equals the length of the longest increasing subsequence, and the number of rows equals the length of the longest decreasing subsequence. In Part II, the paper extends the results to sequences with repetition. It shows that by replacing repeated numbers with unique numbers, the properties of sequences with repetition can be analyzed using standard Young tableaux. The paper presents Theorem 4, which generalizes Theorem 3 to sequences with repetition, stating that the number of sequences with a longest non-decreasing subsequence of length α and a longest decreasing subsequence of length β is the sum of the products of the number of modified standard tableaux and the number of standard tableaux of the same shape. The paper also provides examples and formulas for binary sequences.This paper discusses the problem of determining the number of sequences of length n consisting of integers 1 to m that have a longest increasing subsequence of length α. It introduces the concept of standard Young tableaux and uses them to express results. The paper is divided into two parts: Part I deals with sequences without repetition, while Part II extends the results to sequences with repetition. In Part I, a standard Young tableau is defined as an arrangement of numbers in rows and columns with increasing sequences in each row and column. The shape of a tableau is the arrangement of squares corresponding to the numbers in the tableau. The number of standard tableaux of a given shape is calculated using hook lengths. The paper defines operations S ← x and x → S, which generate standard tableaux. It proves that these operations result in standard tableaux and establishes a one-to-one correspondence between sequences and ordered pairs of standard tableaux. The paper also shows that the number of columns in the P-symbol (or Q-symbol) equals the length of the longest increasing subsequence, and the number of rows equals the length of the longest decreasing subsequence. In Part II, the paper extends the results to sequences with repetition. It shows that by replacing repeated numbers with unique numbers, the properties of sequences with repetition can be analyzed using standard Young tableaux. The paper presents Theorem 4, which generalizes Theorem 3 to sequences with repetition, stating that the number of sequences with a longest non-decreasing subsequence of length α and a longest decreasing subsequence of length β is the sum of the products of the number of modified standard tableaux and the number of standard tableaux of the same shape. The paper also provides examples and formulas for binary sequences.
Reach us at info@study.space