Counting the number of matrices with given properties Given positive integers $m, n$ such that $n \geq 2$ and $m \geq 2$, consider an $mn \times 2$ matrix. I wish to find the number of such matrices that satisfy:
1) The entries of the matrix must be from the set $\{1, 2, \cdots, n\}$.
2) Each of the above choices should occur exactly $2m$ times in the matrix.
3) If way consider any row of the matrix, the entries should be increasing from left to right.
4) If we consider any column of the matrix, the entries should be non-decreasing from top to bottom.
I tried solving the problem for small cases. When $n=2,3,4,5$, I could find the number of matrices by doing some casework. But I can't seem to find a method that would work in general.
 A: Clearly every such matrix is uniquely determined by $a_1,a_2\dots a_n$, where $a_i$ is the number of times $i$ appears in the left column.
in order for the matrix to work we need three things:


*

*$0\leq a_i\leq 2m$ for all $i\in \{1,2,3\dots n\}$

*$a_0+a_1+\dots + a_n=nm$

*$\sum_{i=1}^k a_i\geq km$ for all $k\in \{1,2,3\dots n\}$


So we try to count how many sequences satisfy this instead.
Denote by $F(n,m,x)$ the number of sequence $a_1,a_2\dots a_n$ such that:


*

*$0\leq a_i\leq 2m$ for all $i\in \{1,2,3\dots n\}$

*$a_0+a_1+\dots + a_n=x$

*$\sum_{i=1}^k a_i\geq km$ for all $k\in \{1,2,3\dots n\}$


The answer we are looking for is $F(n,m,nm)$.
But we can calculate $F(n,m,k)$ recursively by noting:
$F(n,m,x)=\sum_{i=0}^{2m}F(n-1,m,k-i)$ if $x\geq nm$ and $0$ otherwise.
Using this recursion we can obtain the rresult.
Here is some c++ code:
#include <bits/stdc++.h>
using namespace std;

const int MAX=20;
int F[MAX][MAX][MAX*MAX];

int main(){
    for(int n=1;n<MAX;n++){
        for(int m=1;m<MAX;m++){
            for(int x=1;x<MAX*MAX;x++){
                if(n==1){
                    if(x<=2*m && x>=m ) F[n][m][x]=1;
                }
                else{
                    for(int i=0;i<=2*m;i++){
                        F[n][m][x]+=F[n-1][m][x-i];
                    }
                }
            }
        }
    }

}

Here is a table with some values.
$$\begin{pmatrix}  1 &        1 &        1 &        1 &        1 &        1 &        1 & \\ 
   2 &        3 &        4 &        5 &        6 &        7 &        8 & \\ 
   5 &       12 &       22 &       35 &       51 &       70 &       92 & \\ 
  13 &       52 &      134 &      275 &      491 &      798 &     1212 & \\ 
  35 &      233 &      841 &     2220 &     4846 &     9310 &    16318 & \\ 
  96 &     1066 &     5391 &    18306 &    48857 &   110957 &   224442 & \\ 
 267 &     4943 &    35011 &   152894 &   498834 &  1339044 &  3125634 & \\ 
\end{pmatrix}$$
