This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.
Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ thru $12$ inclusive. Each cell in this grid can be in any of $k$ states (where $k$ ranges from $2$ thru $20$).
The problem is to find the total number of distinct (non-equivalent) state configurations of this grid.
Definition: Two configurations of a grid, $c_1$ and $c_2$, are deemed "equivalent" if it is possible to change $c_1$ to $c_2$ by swapping any pair of rows and/or any pair of columns (you can perform the swap operation as many times as you want).
To take an example, let's consider a grid with $w=2$, $h=2$, and $k=2$. We will represent each of the two states as $0$ and $1$ respectively.
One possible configuration of the grid is one where all the cells are in state $0$:
You could swap any rows and/or columns without changing anything. So the above counts as 1 configuration.
Another configuration is where only 1 cell is in state $1$. There are 4 possible arrangements:
01 10 00 00
00 00 01 10
But note that all of the 4 arrangements are "equivalent", because you can get any of the arrangements by swapping rows and/or columns. So the above counts as 1 configuration.
Next, exactly 2 cells are in state $1$:
Another (non-equivalent) way in which 2 cells are in state $1$:
And yet another:
So there are 3 non-equivalent configurations in which exactly 2 cells are in state $1$.
Next, exactly 3 cells are in state $1$:
10 01 11 11
11 11 10 01
1 configuration, just as in the case where only 1 cell was in state $1$.
Finally, all 4 cells are in state $1$:
1 configuration, just as in the case where all 4 cells were in state $0$.
So, counting them up, there are exactly $7$ distinct configurations for the case where $w=2, h=2, k=2$.
For reference, here are some brute-force test cases I ran on some additional examples (where the w,h,k values are fairly small):
w=2,h=1,k=1 Answer: 1
w=2,h=1,k=2 Answer: 3
w=2,h=1,k=3 Answer: 6
w=2,h=1,k=4 Answer: 10
w=2,h=1,k=5 Answer: 15
w=2,h=1,k=6 Answer: 21
So at least when w, h are fixed at 1,2 (or at 2,1), the pattern seems pretty obvious as k increases. Here is another suite of test cases for w=2, h=2:
w=2,h=2,k=1 Answer: 1
w=2,h=2,k=2 Answer: 7
w=2,h=2,k=3 Answer: 27
w=2,h=2,k=4 Answer: 76
w=2,h=2,k=5 Answer: 175
w=2,h=2,k=6 Answer: 351
This is much less obvious to me. If there is a pattern, I'm unsure how to find it.
One more suite of test cases for good measure:
w=2,h=3,k=1 Answer: 1
w=2,h=3,k=2 Answer: 13
w=2,h=3,k=3 Answer: 92
w=2,h=3,k=4 Answer: 430
w=2,h=3,k=5 Answer: 1505
yep I'm lost as to what insight if any can be gained.
So, for some arbitrary $w,h,k$, I'm wondering whether there is some type of closed-form formula or perhaps a way to get the answer via dynamic programming/recursion or perhaps divide-and-conquer? I've tried a few of these approaches and didn't really see any obvious breakthrough. The answers get very large very quickly (for example, for $w=2,h=3,k=4$, the answer is 430). I can only imagine how large the answer would be for, say, $w=12,h=12,k=20$.
I would appreciate any help on this. Thanks!