Number of different sequences in a matrix of $N{\times} M$

Question

Consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $1$ and $K $(inclusive). For each such matrix , say $A$, let’s form a sequence $L_{\mathrm{1}},L_{\mathrm{2}},…,L_{\mathrm{N+M}}$:

For each $i$ ($1≤i≤N$), $L_{\mathrm{i}}$ is the maximum of all elements in the $i^{\mathrm{th}}$ row of $A$. Lets call these $N$ elements as sequence $B$. For each $i$ ($1≤i≤M$), $L_{\mathrm{N+i}}$ is the maximum of all elements in the $i^{\mathrm{th}}$ column of $A$. Let's call these $M$ elements as sequence $C$.

Find the number of different sequences formed in this way.

Example: When $N=2$ , $M=2$ & $K=2$ , the number of sequences are $10$.

The 10 sequences are : $(0,0,0,0), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,1,0), (1,0,1,1), (0,1,1,1), (1,1,0,1)$ and $(1,1,1,1).$

I haven't found a way to prove that the number of sequences is a polynomial of degree $N+M-1$.

A detailed proof and explaining the intuition behind it would be really appreciated.

This is the original Problem link

Answer 1

So, the solution is $$\sum_{i=0}^{K-1} ((i+1)^M - i^M)((i+1)^N - i^N)$$ For the intuition part,
Assume L_i is the maximum of L₁, L₂.....L_N. Now L_i should be the maximum of L_N+1, L_N+2.....L_N+M.

Short proof for this claim - Assume this is not true, then there exists an element in L_N+1, L_N+2.....L_N+M which is greater than L_i then it must appear in any of the row. But, it doesn't, therefore it produces a contradiction.

Now, if $L_i$ is the maximum element for both the part of the sequence as their maximum. So, numbers of distinct sequences for a row if $L_i$ is the maximum is $L_i^N - (L_i-1)^N$ which equals to placing every element from $0$ to $L_i$ at every position and then removing sequence when the element $L_i$ doesn't appear.
Example: For n = 3 and $L_i$ = 2
Possible sequences $(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)$

Valid sequences $(0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)$
and counts $=2^3-(2-1)^3$

Now, put $0$ in every entry except for the column corresponding to the $L_i$. Now the matrix is valid as long as there exists the maximum element in it. So, every sequence can be formed from the column as long as that contains the $L_i$. So the same formula applies. And count is $L_i^M - (L_i-1)^M$. As we have used every possible sequence, we do not undercount by filling other entries as 0. You can prove there is no other possible sequence. Now, we iterate over every possible maximum which is $1$ to $k-1$. Hence follows the summation.

First Test Case
For N=M=K=2 $$((0+1)^2 - 0^2)((0+1)^2 - 0^2))+((1+1)^2 - 1^2))((1+1)^2 - 1^2)) = 10$$
Second Test case
For N=2, M=3, K=2
$$((0+1)^3 - 0^3)((0+1)^2 - 0^2))+((1+1)^3 - 1^3))((1+1)^2 - 1^2)) = 22$$