On two related questions of Wilf concerning standard Young tableaux
Let \(u_k(n)\) be the number of permutations of length \(n\) that contain no increasing subsequence of length \(k+1\), and let \(y_k(n)\) be the number of standard Young tableaux on \(n\) boxes that have no rows longer than \(k\). \textit{H. S. Wilf} has proved [J. Comb. Theory, Ser. A 60, No.1, 155-157 (1992; Zbl 0769.05100)] that, for all \textit{even} positive integers \(k\), \({2n\choose n} u_k(n)=\sum_{r=0}^{2n}\binom{2n}{r} (-1)^r y_k(r)y_k(2n-r)\) (Theorem 1). Wilf's proof is not elementary, and he asked (a) whether there is a purely combinatorial proof, and (b) what happens for odd \(k\). In the paper under review, the author gives a combinatorial proof in the case \(k=2n\), and this leads to a more general answer when \(k\) is odd. The following facts about the Robinson-Schensted correspondence are important in the proof: there is a one-to-one correspondence \(RS\) between involutions on an \(n\)-element set and standard Young tableaux on \(n\) boxes; the length of the longest increasing (decreasing) subsequence of the involution \(v\) equals the length of the first row (column) of \(RS(v)\); and the number of fixed points of \(v\) equals the number of odd columns of \(RS(v)\). In the case \(k=2n\), Theorem 1 simplifies to: \(\binom{2n}{n}n!=\sum_{r=0}^{2n}\binom{2n}{r} (-1)^r y(r)y(2n-r)\), where \(y(m)\) denotes the number of involutions of an \(m\)-element set (Proposition 1). The same line of proof, which uses the fixed point-free involutions, cannot be used to prove Theorem 1, but it can be used to prove that for all \textit{odd} integers \(k\), \(\sum_{r=0}^{2n}\binom{2n}{r} (-1)^r x_k(r)x_k(2n-r)=\sum_{r=0}^{2n}\binom{2n}{r} (-1)^r y_k(r)y_k(2n-r)\), where \(x_k(r)\) is the number of fixed point-free involutions of length \(r\) with no decreasing subsequences with more than \(k\) elements (Theorem 3). The case \(k=3\) takes on the following interesting form: \(\sum_{r=0}^{2n}\binom{2n}{r} (-1)^r y_3(r)y_3(2n-r)=y_4(2n)=C_n C_{n+1}\), where \(C_i\) is the \(i\)th Catalan number (Corollary 1).
- On standard Young tableaux of bounded height
- On descents in standard Young tableaux
- Standard Young tableaux in the Weyl group setting
- Two partial orders for standard Young tableaux
- On the number of standard Young tableaux of slanting diagrams
- An extension of the Foata map to standard Young tableaux
- Standard Young tableaux in a \(( 2 , 1 )\)-hook and Motzkin paths
- Identities for the number of standard Young tableaux in some \((k,l)\)-hooks
- Correspondence between Young walls and Young tableaux and its application
- scientific article; zbMATH DE number 1001729
- Ascending subsequences of permutations and the shapes of tableaux
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1522339 (Why is no real title available?)
- La correspondance de Robinson
- Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux
- Standard Young tableaux of height 4 and 5
- The On-Line Encyclopedia of Integer Sequences
- Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux
- Standard Young tableaux of height 4 and 5
- Young tableaux and linear independence of standard monomials in multiminors of a multimatrix
- Ascending subsequences of permutations and the shapes of tableaux
- Combinatorial proofs of identities involving symmetric matrices
- Subsequence containment by involutions
- On standard Young tableaux of bounded height
- An extension of the Foata map to standard Young tableaux
- scientific article; zbMATH DE number 3987281 (Why is no real title available?)
- An asymptotic version of a theorem of Knuth
- Permutations whose reverse shares the same recording tableau in the RS correspondence
- Enumerating \(r\)c-invariant permutations with no long decreasing subsequences
This page was built for publication: On two related questions of Wilf concerning standard Young tableaux
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024331)
