Let there be a matrix A of size NxM.
In how many ways can the matrix be partitioned in regions of maximum K adjacent cells? 1<=K<N*M.
A few examples for N=M=3, K=5
$\begin{pmatrix}1&1&1\\1&2&4\\1&2&3\end{pmatrix}$, $\begin{pmatrix}1&1&1\\1&3&1\\2&3&3\end{pmatrix}$, $\begin{pmatrix}1&2&3\\1&2&3\\1&2&3\end{pmatrix}$, $\begin{pmatrix}1&1&1\\2&3&4\\5&6&6\end{pmatrix}$...
This question can be broken into:
Given an integer partition X of N*M, in how many ways can the matrix A be partitioned in regions of size Xi?
For N=M=3 and X=3+3+3, we have:
$\begin{pmatrix}1&1&1\\2&2&2\\3&3&3\end{pmatrix}$, $\begin{pmatrix}1&2&3\\1&2&3\\1&2&3\end{pmatrix}$ <- 1 unique + 1 symmetry
$\begin{pmatrix}1&1&2\\1&2&2\\3&3&3\end{pmatrix}$, $\begin{pmatrix}1&2&2\\1&1&2\\3&3&3\end{pmatrix}$, $\begin{pmatrix}1&1&3\\1&2&3\\2&2&3\end{pmatrix}$, $\begin{pmatrix}1&1&3\\2&1&3\\2&2&3\end{pmatrix}$... <- 1 unique + 7 symmetries
Therefore given the partition X of 3*3 there are 2 unique partitions for the matrix A and 10 partitions when considering symmetries.
What I'm interested in, is a formula for the number of partitions of a matrix (either unique or not -> 2 or 10 in case above) and if such formula doesn't exist, a constructive algorithm that determines/generates that number.
Thank you!