# Clash of Clans Permutations

I'm not an expert mathematician (I'm 16) and I'm Italian, so please try to understand my question and forgive my poor language. Thank you.

When I play Clash of Clans, I ask me "How many buildings permutation there are in a village?" For those who don't know the game, it's based on set up your own village, the space in your disposal is a grid $40\times 40$ and every building fill a square space ($1 \times 1$, $2 \times 2$, $3 \times 3$, $4 \times 4$ or $5 \times 5$) And there is a maximum number for each of this. The most important thing is that the buildings MUST NEVER overlap themselves. I've immediately realized the difficulty of the problem, so I've decided to simplify it.

"How many $1$ square $5 \times 5$ permutations there are in a grid $40 \times 40$?" Obviously there are $(40-5+1)^2=1296$.

Then "How many $2$ SAME square $5 \times 5$ permutations there are in a grid $40 \times 40$?" I've computed it in two different ways and I got the same result: $793600$. I think that the most elegant and simplest way to reach this result is $$\frac {((40-5+1)^2)^2-\text{#overlaps}} {2!}$$

Now I want to know if there is a formula for number of $n$ SAME square $a \times a$ permutation in a grid $b \times b$. For give you a better idea, if there are $64$ same squares $5 \times 5$ in a grid $40 \times 40$, there is $1$ single permutation.

I've started working on a method for this, but maybe it already exist... The problem is that I can not find it on the internet.

• anyways see (this)[meta.math.stackexchange.com/questions/5020/… – RE60K Aug 13 '14 at 19:02
• Ahahah yes... $$(((40-5+1)^2)^2- #overlaps))/2!$$ – Domenico Modica Aug 13 '14 at 19:03
• $$(((40-5+1)^2)^2- #overlaps))/2!$$ Instead you should use $$\frac {((40-5+1)^2-\text{#overlaps})^2} {2}$$ for $$\frac {((40-5+1)^2-\text{#overlaps})^2} {2}$$ – RE60K Aug 13 '14 at 19:06
• @Aditya I rewrote the question in correct form using latex, so, can you help me? – Domenico Modica Aug 14 '14 at 23:16
• I was just helping you present your question, this does not necessarily mean I would solve it. It is a good question, so wait for the answer from anyone, or even after a long time,if you don't get an answer, you can put up a bounty on it provided you get some reputation – RE60K Aug 15 '14 at 3:21