This paper by C. Schensted focuses on finite sequences of integers, particularly the determination of the number of sequences of length \( n \) consisting of the integers \( 1, 2, \ldots, m \) that have a longest increasing subsequence of length \( \alpha \). The paper is divided into two parts: the first part deals with sequences without repetitions, while the second part extends the results to include sequences with repetitions. - **Definition**: A standard Young tableau of order \( n \) is an arrangement of \( n \) distinct natural numbers in rows and columns, where each row and column forms an increasing sequence. - **Shape**: The shape of a standard tableau is the arrangement of squares corresponding to the numbers in the tableau. - **Theorem**: The number of standard tableaux of a given shape containing the integers \( 1, 2, \ldots, n \) is given by \( \frac{n!}{\prod_{j=1}^{n} h_{j}} \), where \( h_{j} \) are the hook lengths. - **P-Symbol and Q-Symbol**: The P-symbol and Q-symbol are defined for a sequence of distinct integers, and they are shown to be standard tableaux. - **Lemma 3**: There is a one-to-one correspondence between sequences of distinct integers and ordered pairs of standard tableaux of the same shape. - **Theorems**: - The number of columns in the P-symbol is equal to the length of the longest increasing subsequence. - The number of rows in the P-symbol is equal to the length of the longest decreasing subsequence. - The number of sequences with a longest increasing subsequence of length \( \alpha \) and a longest decreasing subsequence of length \( \beta \) is the sum of the squares of the numbers of standard tableaux with shapes having \( \alpha \) columns and \( \beta \) rows. - **Modified Standard Tableaux**: For sequences with repetitions, modified standard tableaux are introduced, where each column forms an increasing sequence and each row forms a non-decreasing sequence. - **Theorem 4**: The number of sequences with a longest non-decreasing subsequence of length \( \alpha \) and a longest decreasing subsequence of length \( \beta \) is the sum of the products of the number of modified standard tableaux of a given shape with the number of standard tableaux of the same shape, each having \( \alpha \) columns and \( \beta \) rows. - **Examples**: Examples are provided to illustrate the application of Theorem 4, including binary sequences. The paper provides a comprehensive framework for understanding and calculating the number of sequences with specific longest increasing and decreasing subsequences, both with and without repetitions.This paper by C. Schensted focuses on finite sequences of integers, particularly the determination of the number of sequences of length \( n \) consisting of the integers \( 1, 2, \ldots, m \) that have a longest increasing subsequence of length \( \alpha \). The paper is divided into two parts: the first part deals with sequences without repetitions, while the second part extends the results to include sequences with repetitions. - **Definition**: A standard Young tableau of order \( n \) is an arrangement of \( n \) distinct natural numbers in rows and columns, where each row and column forms an increasing sequence. - **Shape**: The shape of a standard tableau is the arrangement of squares corresponding to the numbers in the tableau. - **Theorem**: The number of standard tableaux of a given shape containing the integers \( 1, 2, \ldots, n \) is given by \( \frac{n!}{\prod_{j=1}^{n} h_{j}} \), where \( h_{j} \) are the hook lengths. - **P-Symbol and Q-Symbol**: The P-symbol and Q-symbol are defined for a sequence of distinct integers, and they are shown to be standard tableaux. - **Lemma 3**: There is a one-to-one correspondence between sequences of distinct integers and ordered pairs of standard tableaux of the same shape. - **Theorems**: - The number of columns in the P-symbol is equal to the length of the longest increasing subsequence. - The number of rows in the P-symbol is equal to the length of the longest decreasing subsequence. - The number of sequences with a longest increasing subsequence of length \( \alpha \) and a longest decreasing subsequence of length \( \beta \) is the sum of the squares of the numbers of standard tableaux with shapes having \( \alpha \) columns and \( \beta \) rows. - **Modified Standard Tableaux**: For sequences with repetitions, modified standard tableaux are introduced, where each column forms an increasing sequence and each row forms a non-decreasing sequence. - **Theorem 4**: The number of sequences with a longest non-decreasing subsequence of length \( \alpha \) and a longest decreasing subsequence of length \( \beta \) is the sum of the products of the number of modified standard tableaux of a given shape with the number of standard tableaux of the same shape, each having \( \alpha \) columns and \( \beta \) rows. - **Examples**: Examples are provided to illustrate the application of Theorem 4, including binary sequences. The paper provides a comprehensive framework for understanding and calculating the number of sequences with specific longest increasing and decreasing subsequences, both with and without repetitions.