How to count the number of different sequences possible? Lets consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $0$ and $K−1$ (inclusive). For each such matrix $A$, let's form a sequence $L[1],L[2],…,L[N+M]$ defined as follows.
For each $i$ ($1≤i≤N$), $L[i]$ is the maximum of all elements in the $i$-th row of $A$. For each $i$ ($1≤i≤M$), $L[N+i]$ is the maximum of all elements in the $i$-th column of $A$. Find the number of different sequences formed this way. My approach is simple brute-force.
Example: $N=2;M=2;K=2$
Answer: $10$
All $16$ different possible matrices are as follows:
$\pmatrix{0&0\\ 0&0} \to (0, 0, 0, 0)$ (sequence generated)
$\pmatrix{0&0\\ 0&1} \to (0, 1, 0, 1)$
$\pmatrix{0&0\\ 1&0} \to (0, 1, 1, 0)$
$\pmatrix{0&1\\ 0&0} \to (1, 0, 0, 1)$
$\pmatrix{1&0\\ 0&0} \to (1, 0, 1, 0)$
$\pmatrix{1&0\\ 1&0} \to (1, 1, 1, 0)$
$\pmatrix{1&1\\ 0&0} \to (1, 0, 1, 1)$
$\pmatrix{0&0\\ 1&1} \to (0, 1, 1, 1)$
$\pmatrix{0&1\\ 0&1} \to (1, 1, 0, 1)$
$\pmatrix{1&0\\ 0&1} \to (1, 1, 1, 0)$
$\pmatrix{0&1\\ 1&0} \to (1, 1, 1, 1)$
$\pmatrix{1&1\\ 1&0} \to (1, 1, 1, 1)$
$\pmatrix{1&0\\ 1&1} \to (1, 1, 1, 1)$
$\pmatrix{1&1\\ 0&1} \to (1, 1, 1, 1)$
$\pmatrix{0&1\\ 1&1} \to (1, 1, 1, 1)$
$\pmatrix{1&1\\ 1&1} \to (1, 1, 1, 1)$
 A: As the other answer points out, you get all sequences such that the maximum of the first $N$ positions coincides with the maximum over the remaining $M$ positions, and that maximum $l$ can be any number in $\{0,1,\ldots,K-1\}$. Given such $l$, we can independently choose the first $N$ and last $M$ positions, to be any of the $(l+1)^N-l^N$ sequences in $\{0,1,\ldots,l\}^N\setminus\{0,1,\ldots,l-1\}^N$, respectively the same with $M$ replacing $N$. So the total number is
$$
  \sum_{l=0}^{K-1}((l+1)^N-l^N)((l+1)^M-l^M)
$$
For instance, in your example $K=N=M=2$ this gives $(1^2-0^2)(1^2-0^2)+(2^2-1^2)(2^2-1^2)=1^2+3^2=10$. As another example for $K=3,N=4,M=5$ one gets $1*1+15*31+65*211=14181$; it does not look like a simple closed formula for that sum exists.
A: Clearly the maximum of the matrix must appear in both halves of the sequence, since it is the maximum of both its row and its column. In fact this is the only restriction: if $L$ is a sequence such that $L[i]$ is the maximum of $L[1], \ldots, L[N]$ and $L[N + j]$ is the maximum of $L[N + 1], \cdots, L[N + M]$, and $L[i] = L[N + j]$, then $L$ appears as the sequence of the matrix
$$
\begin{pmatrix}
0 & \cdots & 0 & L[1] & 0 & \cdots & 0\\
0 & \cdots & 0 & L[2] & 0 & \cdots & 0\\
\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots\\
0 & \cdots & 0 & L[i-1] & 0 & \cdots & 0\\
L[N+1] & \cdots & L[N+j-1] & L[i] = L[N+j] & L[N+j+1] & \cdots & L[N+M]\\
0 & \cdots & 0 & L[i+1] & 0 & \cdots & 0\\
\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots\\
0 & \cdots & 0 & L[N-1] & 0 & \cdots & 0\\
0 & \cdots & 0 & L[N] & 0 & \cdots & 0
\end{pmatrix}.
$$
