Permutations of a colored grid if columns and rows are freely swappable

51 Views Asked by At

It's my first time posting here, so I hope I manage to bring my thoughts across clearly and accurately.

A grid of the size x×y is given alongside a set of n numbers c1, c2, c3, ..., cc that added together equal x×y. The numbers represent sets of tiles to be placed on the grid that are indistinguishable within their appropriate set. For a simple analogy, let's think of them as colors of the tiles. For example, one could have a 3×3 grid with 6 red tiles, 2 orange tiles, and 1 yellow tile.

I need to calculate the amount of all the possible arrangements of those tiles. The catch is - two arrangements are considered equal, if you can change one into the other by performing any amount of row and/or column swaps.

The total amount of permutations, should all the tiles be unique, would be (x×y)!. To account for the fact that certain tiles are indistinguishable from others, we can just use multinomial coefficients like that: $$\frac{(x*y)!}{\prod_{i=1}^n c_n!}$$ This, however, does not factor in the column and row swapping. In total, there are x! ways to permutate the grid's columns and y! ways to permutate the rows. Naïvely, one could furter divide the above term by the amount of those permutations. $$\frac{(x*y)!}{(\prod_{i=1}^n c_n!)*x!*y!}$$ The problem is, that certain column and row swaps produce arrangements, already accounted for due to the indistinguishability of same-colored tiles.

Let us take a 2×2 grid with 2 red and 2 blue tiles for an example. The total amount of permutations when the same colors are mutually indistinguishable is 4!/(2!×2!)=6. There is, however, still the question, how many of those permutations are considered the same due to the column/row swapping rule. \begin{bmatrix}red&red\\blue&blue\end{bmatrix} By swapping the two rows, one gets a different arrangement of colors, which is to be considered the same permutation. \begin{bmatrix}blue&blue\\red&red\end{bmatrix} By swapping the two columns, however, the colors will not change at all. The two arrangements achieved by this column swap have already been accounted for by dividing the total amount of possible permutations by the permutations of the colored tiles. As such, the answer is not as simple as dividing the 6 remaining permutations by the amount of possible row and column swaps, which would lead to the result 1.5. The actual answer, due to the overlap between row/column swaps and different permutationts within the same color, is 3.

How can I account for this overlap in my equation? I was not able to find any papers or other ressources relevant to my issue. It's possible that I don't know the proper terminology to find such ressources. Since I'm willing to research this further, I'd appreciate a nudge in the right direction or a link to a paper that could be of interest to me just as much as a complete answer to this problem.