3
$\begingroup$

I'm curious as to how many matrices there are of size $m \times n$ with elements of the set $\{1, \ldots , k\}$ such that each row and column is weakly increasing?

The answer should be expressable as a determinant.

I'm thinking that this could be solved by counting non-intersecting lattice paths somehow and using Lindström–Gessel–Viennot lemma, however I'm unsure of how to construct the matrix.

Thanks!

  • 0
    @MarcvanLeeuwen could you please explain your idea more detailed? It is not clear how to keep constraint of increasing rows and columns while calculating the total number...2013-03-08

1 Answers 1

2

You're asking, essentially, about the number of plane partitions inside $m\times n\times(k-1)$ box.

The answer is given by MacMahon formula, $ \prod_{i=1}^m\prod_{j=1}^n\frac{i+j+k-2}{i+j-1} $ (sanity check: for $k=1$ this is $1$, for $k=2$ or $n=1$ this is a binomial coefficient).

This formula, indeed, can be derived using LGV to count the number of non-intersecting paths, say, from $s_i=(i-1,-n-i+1)$ to $t_j=(m+j-1,-j+1)$ or (equivalently) to $t'_j=(m+j-1,0)$ (where $1\leqslant i,j \leqslant k-1$); the corresponding determinant $ \det\Bigl(P(s_i \rightarrow t_j')\Bigr)=\det\Biggl(\binom{m+n+j-1}{n+i-1}\Biggr)=\det\begin{pmatrix} \binom{m+n}n & \binom{m+n+1}n& \ldots & \binom{m+n+k-2}n \\ \binom{m+n}{n+1} & \binom{m+n+1}{n+1} & \ldots & \binom{m+n+k-2}{n+1} \\ \ldots & \!\ldots & & \!\ldots \\ \binom{m+n}{n+k-2} &\binom{m+n+1}{n+k-2}& \ldots & \binom{m+n+k-2}{n+k-2} \end{pmatrix} $ can be computed using Vandermonde determinant.