, 2014

Solution:

We show that $A(n, m)$ is equal to the number of standard Young tableaux with $n$ rows and $m$ columns (i.e., fillings of an $n \times m$ matrix with the numbers $1,2, \ldots, n m$ so that numbers are increasing in each row and column).

Consider the procedure where every time a $k$ appears in the sequence, you add a number to the leftmost empty spot of the $k$-th row. Doing this procedure will result in a valid standard Young tableau. The entries are increasing along every row because new elements are added from left to right. The elements are also increasing along every column. This is because the condition about the sequences implies that there will always be at least as many elements in row $i$ as there are in row $j$ for $i<j$. At the end of this procedure, the Young tableau has been filled because each of the $n$ numbers has been added $m$ times.

Now, consider an $n \times m$ standard Young tableau. If the number $p$ is in row $k$, you add a $k$ to the sequence. This will produce a valid sequence. To see this, suppose that $p$ appears in the entry $(x, y)$. Then all of the entries $(q, y)$ where $q<x$ have already been added to the sequence because they must contain entries less than $p$. Thus, the numbers $1$ through $x-1$ have all already been added at least $y$ times. Then, when we process $p$, we are adding the $y$-th $x$, which is valid. At the end of this procedure, $n$ numbers have been added $m$ times to the sequence.

The two procedures given above are inverses of each other. Thus, $A(n, m)$ is equal to the number of $n \times m$ standard Young tableaux. For every $n \times m$ tableau, we can transpose it to form an $m \times n$ tableau. The number of such tableaux is $A(m, n)$. Thus, $A(n, m)=A(m, n)$.

Solution:

We can also form a direct bijection to show $A(n, m)=A(m, n)$, as follows. Suppose that $a=(a_{1}, \ldots, a_{m n})$ is a sequence satisfying properties 1 and 2. We will define a sequence $f(a)=(b_{1}, \ldots, b_{n m})$ satisfying the same properties 1 and 2, but with $m$ and $n$ switched.

The bijection $f$ is simple: just define $b_{i}$, for $1 \leq i \leq n m$, to be equal to the number of $j$ with $1 \leq j \leq i$ such that $a_{j}=a_{i}$. In other words, to obtain $f(a)$ from $a$, replace the $k$-th occurrence of each number with the number $k$. For example, if $n=2$ and $m=5$, then $f(1,1,2,1,2,2,1,2,1,2)=(1,2,1,3,2,3,4,4,5,5)$.

First, it is clear that $f(a)$ satisfies property 1 with $m$ and $n$ switched. Indeed, it follows directly from the definition of $f$ that for each pair $(k_{1}, k_{2})$ with $1 \leq k_{1} \leq n$ and $1 \leq k_{2} \leq m$, there is exactly one index $i$ for which $(a_{i}, b_{i})=(k_{1}, k_{2})$. This implies the desired result.

Second, we show that $f(a)$ satisfies property 2 with $m$ and $n$ switched. For this, suppose that $i, j, k$ are integers with $1 \leq i \leq n m$ and $1 \leq j \leq k \leq m$. Then, the number of times that $k$ appears in the sequence $(b_{1}, \ldots, b_{i})$ is exactly equal to the number of integers $\ell$ with $1 \leq \ell \leq n$ such that $\ell$ appears at least $k$ times in the sequence $(a_{1}, \ldots, a_{i})$. Similarly, the number of times that $j$ appears in the sequence $(b_{1}, \ldots, b_{i})$ is exactly equal to the number of integers $\ell$ with $1 \leq \ell \leq n$ such that $\ell$ appears at least $j$ times in the sequence $(a_{1}, \ldots, a_{i})$. In particular, the number $j$ appears in the sequence $(b_{1}, \ldots, b_{i})$ at least as many times as $k$ does.

Now, we show that $f$ is a bijection. We claim that $f$ is actually an involution; that is, $f(f(a))=a$. (Note in particular that this implies that $f$ is a bijection, and its inverse is itself.)

Fix an index $i$ with $1 \leq i \leq m n$. Let $\ell=a_{i}$ and $k=b_{i}$; then, $k$ is the number of times that the term $\ell$ appears in the sequence $(a_{1}, \ldots, a_{i})$. It is enough to show that $\ell$ is the number of times that the term $k$ appears in the sequence $(b_{1}, \ldots, b_{i})$. First, note that by definition of $f$, the number of times $k$ appears in the sequence $(b_{1}, \ldots, b_{i})$ is equal to the number of integers $j$ such that the sequence $(a_{1}, \ldots, a_{i})$ contains the number $j$ at least $k$ times.

Now, $\ell$ occurs exactly $k$ times in the sequence $(a_{1}, \ldots, a_{i})$. So by property 2, each $j$ with $j \leq \ell$ appears at least $k$ times in the sequence $(a_{1}, \ldots, a_{i})$. Furthermore, each $j$ with $j>\ell$ appears at most $k-1$ times in the sequence $(a_{1}, \ldots, a_{i-1})$ and thus appears at most $k-1$ times in the sequence $(a_{1}, \ldots, a_{i})$ as well (because $a_{i}=\ell$). Therefore, the number of integers $j$ such that the sequence $(a_{1}, \ldots, a_{i})$ contains the number $j$ at least $k$ times is exactly equal to $\ell$. This shows the desired result.