Proving that the number of pairs of monotone sequences is equal to the number of partitions of $m$

Question

I have a problem from the book A Course in Enumeration by Aigner that I'm having trouble with. The problem is 1.63 in the book. It is as follows:

Let $b_m$ be the number of pairs $\lambda = \lambda_1\lambda_2 \ldots \lambda_k, \mu = \mu_1\mu_2\ldots\mu_k$ for some $k$ such that $\lambda_1 > \lambda_2 > \ldots > \lambda_k \geq 1, \mu_1 > \mu_2 > \ldots > \mu_k \geq 0$ and $\sum \lambda_j + \sum \mu_j = m$. Prove that $b_m = p(m)$. Hint: Use a clever decomposition of the Ferrers diagram.

Note that $p(m)$ is the number of integer partitions (e.g. $p(3)=3$ since $3$ can be partitioned into any of $\{3,21,111\}$).

I tried composing each $(\lambda_i,\mu_i)$ pair by rows in a Ferrers diagram, but I had trouble with that because each $\lambda_i$ must be strictly greater than $\lambda_{i+1}$ and likewise for $\mu$.

Answer 1

I think the following decomposition suffices, though I won't go so far as to claim a proof of the bijection. Consider a Ferrers diagram, and draw a $45^\circ$ line through it as shown below (for the integer partition $6+4+3+1+1=15$).

Then the lengths of columns below and rows above give the pairs $\lambda,\mu$ respectively, i.e. $\lambda=6\,3\,1$, $\mu=4\,1\,0.$ (The last possible row is the third, and it's empty). If I'm judging this correctly, the resulting pairing 1) is always strictly decreasing (the red line is always moving down and right), 2) has exactly as many lower columns as upper rows (if one allows the last upper row to be empty), and 3) the last lower column has at least one dot.

So it would appear that each pair counted by $b_m$ corresponds to some unique, well-defined Ferrers diagram counted by $p(m)$ and therefore $b_m=p(m)$.

Answer 2

I've solved my problem. The hint is correct; I used a decomposition of the Ferrers diagram.

Rather than post my full proof, I will give the best idea I can as the proof I wrote is quite messy.

I will show the idea by example.

Suppose we have this Ferrers diagram for $n=26$:

$$ \begin{array}{cccccc} \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & \bullet & & \\ \bullet & \bullet & \bullet & \bullet & & \\ \bullet & \bullet & \bullet & & & \\ \bullet & \bullet & & & & \\ \bullet & \bullet & & & & \end{array} $$

We now want to compose $\lambda = \lambda_1\lambda_2\ldots\lambda_k$.

For the first row, take all the elements. This is $\lambda_1$.

For the second row, take all the elements except for the element in the first column. This is $\lambda_2$.

For the third row, take all the elements except for the elements in the first and second column. This is $\lambda_3$.

Continue this pattern while $\lambda_i$ is nonzero.

Visually, we have this construction:

$$ \begin{array}{cccccc} \circ & \circ & \circ & \circ & \circ & \circ \\ \bullet & \circ & \circ & \circ & \circ & \\ \bullet & \bullet & \circ & \circ & & \\ \bullet & \bullet & \bullet & \circ & & \\ \bullet & \bullet & \bullet & & & \\ \bullet & \bullet & & & & \\ \bullet & \bullet & & & & \end{array} $$

$\lambda_1$ is the number of hollow dots in row $1$, $\lambda_2$ is the number of hollow dots in row $2$, and so on.

$\mu = \mu_1\mu_2\ldots\mu_k$ is composed of the solid dot columns of this diagram.

So for our example, we have $\lambda = (\lambda_1,\ldots,\lambda_4) = (6,4,2,1)$ and $\mu = (\mu_1, \ldots, \mu_4) = (6,5,2,0)$.

Hope this helps someone looking for this problem. Add a comment below if you want clarification.