Number of cover relations on partition

Question

$L(m,n)$ is the set of partitions with length m and each part is in the set ${0,...n}$. Two partitions $a$ and $b$ in $L(m,n)$ with $a=(a_1,...,a_m)$ and $b=(b_1,...,b_m)$ are in relation: $a\leq b$ if $a_i\leq b_i$ for all $i$ and $a_i<b_i$ for at least one $i$.

$c(n,m)$ is the number of pairs $(a,b), \; a,b \in L(m,n)$ with $a\leq b$ and no partition $c$ with $a\leq c \leq b$.

I need to show that: $$c(m,n)=\frac {(m+n-1)!}{(n-1)!(m-1)!}$$

I already have the hint to watch the $a_1$ but do not progress to the solution. Any help apreciated! Thanks.

Answer 1

I am sure you are aware that $L(m,n)$ can be identified with the set of lattice paths from $(0,0)$ to $(m,n)$, as the set of unit squares below such a path is exactly a partition with $m$ parts whose sizes are all at most $m$. This means $|L(m,n)|=\binom{n+m}{m}$, as such a path has $n+m$ steps, and you must choose $m$ of the steps to be horizontal.

Similarly, the pairs $(a,b)$ counted by $c(m,n)$ can be viewed as a pair of paths from $(0,0)$ to $(m,n)$ which mostly overlap, yet enclose a region between then consisting of one unit square.

I will prove that $$ c(m,n)=(m+n-1)\cdot \binom{m+n-2}{m-1} $$ combinatorially. The factor $\binom{m+n-2}{m-1}$ counts the number of lattice paths from $(0,0)$ to $(m-1,n-1)$, such as the one in the first image below. Such a path will visit $m+n-1$ vertices in the integer lattice. Choose one of these vertices (the * in the image), in $m+n-1$ ways, and "expand" it into a box as shown below, increasing the width and height of the grid by one. The result is a pair of paths from $(0,0)$ to $(m,n)$ with a single box between them, as desired.

Before:

.   .   .   . _ . _ .   
            |
.   .   .   *   .   .   
            |
.   .   . _ .   .   .   
        |
. _ . _ .   .   .   .   

After:

.   .   .   .   . _ . _ .   
                |
.   .   .   . _ .   .   .
            |   |
.   .   .   . _ .   .   .
            |
.   .   . _ .   .   .   .
        |
. _ . _ .   .   .   .   .

Answer 2

That's very odd notation for a non-reflexive relation, but never mind.

What you're trying to count are pairs $(a, b)$ which agree on every part except one, and for that one part the difference is $1$. So either $a_1=b_1=k \le n$, in which case the remaining rows have $c(m-1,k)$ possibilities; or $a_1= b_1-1 = k<n$, in which case the remaining rows are equal to each other and have $|L(m-1,k)|$ possibilities.

Answer 3

So $$c(m,n)=\frac{(n+m-1)!}{(n-1)!(m-1)!}$$ can be written as $$c(m,n)=n\binom{m+n-1}{m-1}.$$ You can think as follows. First you can split your partitions into the following $$L(m,n)=\bigcup _{k=0}^m\bigcup _{\ell =1}^n L_{k,\ell}(m,n)$$ where $L_{k,\ell}(m,n)$ are the partitions that use exactly $m-k$ times the block $n.$ and there are $\ell$ types of blocks say $\{a_1,\cdots ,a_{\ell}\}\subseteq [n-1]\cup \{0\}$ and so $$c(m,n)=\sum _{k=0}^m\sum _{\ell =1}^n\ell |L_{k,\ell}(m,n)|,$$ because you can choose one of this type of blocks and add one. Now $$|L_{k,\ell}(m,n)|=\binom{n}{\ell}\binom{k-1}{\ell -1}$$ because we choose the $\ell$ types of blocks from $0,\cdots ,n-1$ and then we for the $k$ blocks remaining from these $\ell$ types. So $$c(m,n)=\sum _{k=0}^m\sum _{\ell =1}^n\ell \binom{n}{\ell}\binom{k-1}{\ell -1}=\sum _{\ell =1}^n\ell \binom{n}{\ell}\sum _{k=0}^m\binom{k-1}{\ell -1}=\sum _{\ell =1}^n\ell \binom{n}{\ell}\binom{m}{\ell }=n\sum _{\ell =1}^n\binom{n-1}{\ell -1}\binom{m}{m-\ell}=n\binom{m+n-1}{m-1}.$$