On two related questions of Wilf concerning standard Young tableaux (Q1024331)

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).