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

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

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

• I used something like this. Thank you for the inspiration! – Tyler Durden Sep 13 '16 at 4:27
• No problem. It looks like the only difference between ours is that you, in effect, place the red line one dot lower than I did (and correspondingly took $\lambda,\mu$ to be rows and columns). But any of my diagrams can be turned into one of yours by flipping along the main diagonal, i.e. our Ferrers diagrams will be conjugate. – Semiclassical Sep 13 '16 at 4:32

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.