4
$\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$
1
  • 1
    $\begingroup$ This is just the multinomial coefficient: 25! / (5!)^5 $\endgroup$
    – Coolwater
    Feb 27, 2015 at 10:51

2 Answers 2

Reset to default
8
$\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$
7
  • $\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, 2015 at 11:23
  • $\begingroup$ +1. This is called the multinomial coefficient. $\endgroup$
    – Martin Thoma
    Feb 27, 2015 at 11:25
  • $\begingroup$ @DRF Sure, I'll add that in. $\endgroup$
    – Uncountable
    Feb 27, 2015 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, 2015 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, 2015 at 14:52
-1
$\begingroup$

Let's start with a blank grid of 25 possible places. At this point there are twenty five possible permutations of any given block. We'll say that this starting point is block 1, after this we have to fill up twenty four more so multiply twenty five by twenty four and get six hundred. This means that there is a one in six hundred chance that a randomly generated sequence would have put this as the space filled. Then multiply six hundred by twenty three because there are twenty three possible places left. Hopefully you understand the process so just repeat this until you finish filling up the grid and take the chance that you got that sequence and that is how many possible permutations there are of that grid with one by one blocks. I see that uncountable has already answered but I thought it might be useful.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .