# Geometrical combinatorics

This question was inspired by Rush Hour game:

You have a 6x6 grid, 12 pieces of size 2, and 4 pieces of size 3. A piece can be placed on the grid either horizontally or vertically. The pieces can't overlap. Note that when all the pieces are placed on the grid they take up all the space.

• Considering that pieces of the same size are identical, how many different ways are there to place all the pieces on the grid?

• What if the placements are considered identical up to a rotation/reflection?

• Is there a solution that can be easily generalized to grids and pieces of any size? If not, is there a good estimate (upper and lower bounds) for the general case?

-

Begin with a simpler problem: You have a $3\times{\mathbb N}$ infinite strip and you should tile it with $2\times1$-dominoes. Denote by $P_k(n)$ $\ (0\leq k\leq 7)$ the number of tilings of $3\times[n]$ such that at the right end we have an overlap by $1$ at positions $\emptyset$, $\{1\}$, $\{2\}$, $\ldots$, $\{ 1,2,3\}$. Initialize by putting $P_0(0)=1$ and $P_k(0)=0$ $\ (1\leq k\leq 7)$. Using the rules of the tiling you will be able to get a system of difference equations of the form $P_i(n+1)=\sum_{k=0}^7 a_{ik} P_k(n)$. Solve (meaning: "integrate") this system, and in the end you have a formula for $P_0(n)$.
The analoguous Rush-Hour problem can be dealt with in a similar manner, but the work to be done is much greater: A priori there are $3^6$ possible overlap-configurations ($0$, $1$, or $2$ at each of the six places), which can be reduced roughly by a factor of $2$ by symmetry considerations, and we have not yet dealt with the condition of having exactly $4$ pieces of size $3$ $\ldots$