HMMT 2014 T9

For integers $m, n \geq 1$, let $A(n, m)$ be the number of sequences $\left(a_{1}, \cdots, a_{n m}\right)$ of integers satisfying the following two properties: (a) Each integer $k$ with $1 \leq k \leq n$ occurs exactly $m$ times in the sequence $\left(a_{1}, \cdots, a_{n m}\right)$. (b) If $i, j$, and $k$ are integers such that $1 \leq i \leq n m$ and $1 \leq j \leq k \leq n$, then $j$ occurs in the sequence $\left(a_{1}, \cdots, a_{i}\right)$ at least as many times as $k$ does.

For example, if $n=2$ and $m=5$, a possible sequence is $\left(a_{1}, \cdots, a_{10}\right)=(1,1,2,1,2,2,1,2,1,2)$. On the other hand, the sequence $\left(a_{1}, \cdots, a_{10}\right)=(1,2,1,2,2,1,1,1,2,2)$ does not satisfy property (2) for $i=5, j=1$, and $k=2$. Prove that $A(n, m)=A(m, n)$.