2
$\begingroup$

I hope this is the correct place to post this, as I don’t study maths. But I do need help calculating the possible permutations of a grid based game I’m currently programming. This isn’t to help out with the game logic, but rather to help me understand how many different combinations of each puzzle I can get by randomising the placement of the tiles.

I think that to someone with a good understanding of maths, this should be a pretty basic problem to solve. I would give it a shot myself, but I didn’t study further maths and I really want a correct answer/algorithm.

Okay so this is the scenario:

I have a 5x5 grid of coloured tiles. There are 5 different colours of tiles. By default, the tiles are ordered into rows of 5. My question is, if every tile can go to any position in the 5x5 grid, how many possible permutations of the grid are there? (also taking into account that tiles of the same colour count as the same tile, so 'red tile A’ is exactly the same as ‘red tile B’ as far as the game mechanics are concerned)

It would be useful to know what you think the permutations figure is for this specific grid but also the calculation you used to arrive at that answer. The reason for this is that the size of the grid may change in the future and I’d like to be able to use the same algorithm to calculate its permutations. It's also likely that I will have other layouts which aren't arranged into rows, and may have different quantities of each block, so if anyone could point me in the right direction with this, it would be greatly appreciated!

Thanks for any advice!!

Below is an example screenshot of what I mean, you can ignore the numbers as they are just for debugging purposes.

enter image description here

$\endgroup$
  • $\begingroup$ This is just the multinomial coefficient: 25! / (5!)^5 $\endgroup$ – Coolwater Feb 27 '15 at 10:51
4
$\begingroup$

If the tiles were distinguishable, we could permute them in $25! $ ways, since for the first tile there would be $25 $ places, for the second one $24 $ etc... But now we can still interchange tiles of a given color with themselves (and leave the permutation "the same"). For instance the red tiles can be permuted between eachother in $5!$ ways. Therefore the final answer should be (divide by $5!$ for each color):

$$\frac {25!}{5! 5! 5! 5! 5!}=\frac{(5^2)!}{(5!)^5}=623360743125120$$

Usind the same reasoning, for an $n \times n$ grid we get:

$$\frac {(n^2)!}{(n!)^n}$$

Now note that the total number of permutations has nothing to do with the grid being a square, so we can generalise even further, to a grid with $k$ tiles and number of tiles per colour $n_1,\cdots,n_m$ (with $n_1+\cdots+n_m=k$). Then we get:

$$\frac{k!}{n_1!*\cdots *n_m!}$$ different permutations.

$\endgroup$
  • $\begingroup$ +1 Good answer. Maybe point out that the fact the "grid" is square has no bearing on the number of combinations (this sort of comes across from the calculations though I guess). $\endgroup$ – DRF Feb 27 '15 at 11:23
  • $\begingroup$ +1. This is called the multinomial coefficient. $\endgroup$ – Martin Thoma Feb 27 '15 at 11:25
  • $\begingroup$ @DRF Sure, I'll add that in. $\endgroup$ – Uncountable Feb 27 '15 at 11:34
  • $\begingroup$ Thank you for the fast, detailed response. I'm at work at the moment so I can't run through your solution properly until later tonight. At a glance though, can I ask if this answer excludes permutations in which the same type of tile fills the same grid space? I'm not sure if i was clear about that requirement. For example, in the diagram, if the only change to the grid was to swap tiles 1 and 2, that would not count as a new grid permutation as those two tiles are of the same type. It may well be that you did understand that point but I have to revise the use of ! in maths later on $\endgroup$ – Swankzilla Feb 27 '15 at 14:31
  • 1
    $\begingroup$ @Swankzilla Yes, this does take into account that we shouldn't doublecount configurations that only have tiles with the same colour swapped. Just to be sure that you know: The factorial function $!$ is defined as $$n!=n*(n-1)*\cdots*2*1$$ which can be easily programmed with the recursive relation $$n!:=n*(n-1)!, \;\;\;\;\; 0!:=1$$ $\endgroup$ – Uncountable Feb 27 '15 at 14:52

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.