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!

  • 3
    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](http://math.stackexchange.com/questions/117835/how-many-sequence-of-integers-j-1-j-2-j-k-are-there-such-that-0/117900#117900).2012-03-15
  • 3
    Why should the answer be expressible as a determinant?2012-03-15
  • 0
    Can you do any special cases, maybe see some patterns?2012-03-23
  • 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