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!

$\endgroup$
  • 3
    $\begingroup$ Hint: you can view a weakly increasing sequence of numbers $0\leq j_1\leq j_2\leq\ldots j_n$ as corresponding to a lattice path that has level $j_i$ above its starting point when it first attains the line $i$ places to the right of its starting point, as described in this answer. $\endgroup$ – Marc van Leeuwen Mar 15 '12 at 10:48
  • 3
    $\begingroup$ Why should the answer be expressible as a determinant? $\endgroup$ – Michael Hardy Mar 15 '12 at 12:51
  • $\begingroup$ Can you do any special cases, maybe see some patterns? $\endgroup$ – Gerry Myerson Mar 23 '12 at 11:33
  • $\begingroup$ @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... $\endgroup$ – Pavel Podlipensky Mar 8 '13 at 0:24
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.