Exercise 8.6 of Algebraic Combinatorics by Stanley

Question

Problem 6 in Chapter 8 of Algebraic Combinatorics by Stanley: Show that the total number of standard Young tableaux (SYT) with $n$ entries and at most two rows is ${n \choose \lfloor n/2 \rfloor}$. Equivalently, $$\sum_{i = 0}^{\lfloor n/2 \rfloor} f^{(n - i, i)} = {n \choose \lfloor n/2 \rfloor}.$$ Try to give an elegant combinatorial proof (the book literally says this). Note that $f^\lambda$ is the number of SYT's of shape $\lambda$.

My attempt: I tried to first prove this for the even case by writing $n = 2m$. Then, I tried to show that if you select any $m$ elements of $[n] = [2m]$ to be in the first row of the SYT (and the remaining in the second row), then you should end up with a unique valid SYT by simply moving the elements of the second row into the first row, in order of left to right, as needed to yield a valid SYT. I believe this operation should yield unique SYT and be surjective, i.e. be able to reach all valid SYT's of $n$ with at most two rows. I got somewhere with showing that every choice of $m$ elements in the first row should yield a unique final SYT, but it is very messy and incomplete; I have no idea where to start in showing that all SYT's of this kind correspond to a choice of $m$ elements to be placed in the first row.

Answer 1

You can use this fact from this other answer by Marc van Leeuwen.

The number of words of length $n$ in the alphabet $\{A,B\}$, such that every prefix has at least as many $A$’s as $B$’s, is $\binom{n}{\lfloor n/2\rfloor}$.

He proves this fact bijectively, where these words are in bijection with $\{A,B\}$-words with exactly $\lfloor n/2 \rfloor$ copies of $A$.

There is a bijection from the set of SYT with at most two rows to the set of $\{A,B\}$-words where each prefix has at least as many $A$’s as $B$’s. Given a tableaux, $T$, you get a word $w=w_1w_2\dots w_n$ as follows. For each $i\in\{1,\dots,n\}$, then $w_i=A$ if $i$ is in the first row of $T$, and $w_i=B$ if $i$ is in the second row of $T$.