Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.