2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ Yes,but you haven't answered the question. For given values of N,M,K , what will be the answer? $\endgroup$ – Firex Firexo Jun 13 at 9:42
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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$. $\endgroup$ – Mees de Vries Jun 13 at 10:12
  • $\begingroup$ Can this summation be solved and reduced to a small formula ? $\endgroup$ – Firex Firexo Jun 13 at 11:56
  • $\begingroup$ @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 ;-) $\endgroup$ – Marc van Leeuwen Jun 13 at 12:43
  • $\begingroup$ @MarcvanLeeuwen Check this link:- math.stackexchange.com/questions/3260945/… Might help you to create the formula. $\endgroup$ – Firex Firexo Jun 13 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.