# 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)$$

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}.$$
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.
• +1, was editing something like this into my answer but that seems redundant now. Is there a nice closed form for this (no summation)? Nothing obvious comes to mind. Maybe if $N = M$. – Mees de Vries Jun 13 at 10:12
• @Guhfggehlthon As I said, it does not like it does. Even in the special case $M=N$ I don't really see much. I can do $N=1$ or $M=1$ though ;-) – Marc van Leeuwen Jun 13 at 12:43