40 of 100: Domino Recursion

Let $F_n$ be the number of ways to tile a $n$ by 2 area, where $n>2$ . There are two ways to start your tiling from the leftmost edge:

A) You can place a domino vertically. Then there are $F_{n-1}$ ways to tile the rest of the area.

B) You can place two dominoes horizontally and there are $F_{n-2}$ ways to tile the rest of the area. Thus there are $F_n= F_{n-1} + F_{n-2}$ ways to tile a $n$ by 2 area. Its the Fibonacci sequence!

For the 5 by 2 area we have $F_5= F_4 + F_3=5+3=\boxed{8}$ .

I saw 1,2,3,5. I immediately recognized Fibonacci sequence. Also that domino example is an example from Concrete Math book by Knuth, Graham and Ptashnik.

Because this is only 5x2, we can draw this out and do not need a formula. The first layout is to have all five tiles arranged vertically. If we wish to rotate a tile horizontally, we will need to have two tiles rotated horizontally, which will leave three tiles vertical. The pair of horizontal tiles will need to be stacked with 0, 1, 2, or 3 of the vertical tiles to their left, which is four layouts. Because there is the possibility of rotating two pairs horizontally, that will leave one lone tile vertically oriented. That tile can be to the left, between, or to the right of the horizontal tiles, which gives three layouts. Adding them, we get 8 possible layouts.

Since we know all 5 ways to fill a 4x2 area, we just need to add one vertical 1x2 rectangle to the existing patterns. Here they are:

• 1st diagram -- add one vertical to either side (2 solutions)

• 2nd diagram -- add one vertical anywhere (1 solution)

• 3rd diagram -- add one vertical to either side (2 solutions)

• 4th diagram -- included in diagrams 1 and 3 (0 solutions)

• 5th diagram -- add one vertical to either end or middle (3 solutions)

Total -- 8 solution

The following formula generates an answer to the problem for any n (and, incidentally, the Fibonacci sequence):

$\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n-i}{i}$

Explanation: For a given n, the possible arrangements can be described as follows:

• All dominoes are vertical - 1 arrangement

• 1 pair of dominoes horizontal: The number of positions for this pair is equal to n-1, so the number of possible arrangements is $\binom{n-1}{1}$

• 2 pairs of dominoes horizontal: The number of positions for these pairs is equal to n-2, so the number of possible arrangements is $\binom{n-2}{2}$

• ... up to floor(n/2), because after that we run out of dominoes.

Noting that $\binom{n-0}{0} = 1$ , the sum of all possible arrangements can be expressed as the sum above.

The problem can be solved intuitively by looking at the "Note" portion -- 1, 2, 3, and 5 are the first terms of the Fibonacci sequence.

The Fibonacci number $F_{n+1}$ shows the number of ways $2\times 1$ dominos cover $2\times n$ area as illustrated above. Since $n=5\implies F_6=8$ . Thus, there are $8$ ways as shown.

The set of figures shows that the side length of 2 is either on the left or right side. Thus, rotations of rectangular "tiles" are not necessarily counted. Let's focus on the bottom part. There are cases:

(1) The tile is composed of 5 dominoes; thus, the bottom part comprises 5 bottom sides of dominoes each measuring 1: 1 way to construct a tile

(2) The tile is composed of 3 dominoes in vertical position (bottom side measuring 1) and 2 dominoes in horizontal position (bottom side measuring 2); thus, the bottom part comprises the combination of 3 bottom sides of dominoes in vertical position and 1 bottom side of domino in horizontal position: $\frac{4!}{3!} = 4$ ways to construct those tiles

(3) The tile is composed of 4 dominoes in horizontal position (bottom side measuring 2) and 1 domino in vertical position (bottom side measuring 1); thus, the bottom part comprises the combination of 2 bottom sides of dominoes in horizontal position and 1 bottom side of domino in vertical position: $\frac{3!}{2!} = 3$ ways to construct those tiles

Add all the results of these cases: 1 + 4 + 3 = 8 ways to construct 5 by 2 tiles

1, 2, 3, 5 is part of Fibonacci sequence. Next from Fibonacci sequence is 8

I got this because this is an example of the Fibonacci sequence where the numbers are: 1,1,2,3,5,8...

Either all tiles are vertical and there is 1 way of achieving this. Or you arrange 2 of the tiles horizontally, for which there is one block of horizontal tiles, which can start from the left side either at the 1st column, the 2nd column, the 3rd column or the 4th colomn. So 4 ways of achieving this. Or most of the tiles can be horizontal with only one block of vertical tiles, these vertical tiles can be in the 1st column, the 3rd column or the 5th column. So 3 ways of achieving one block of vertical tiles. So 1 + 4 + 3 = 8. | I am aware that this does not make any general way of calculating the number of ways of placing tiles on nx2 tiles, so maybe another solution will give this answer. But for the question posed this does what is needed. Regards, David Ps The very 1st solution gives the general answer, and is very lucid!

There is a pattern

${ x }_{ n }={ x }_{ n-1 }+{ x }_{ n-2 }$

Then, 3+5=8

The nuber of ways to tile an area goes up in the Fibonacci sequence which is 1, 1, 2, 3, 5, 8, etc. the number which you are on add the previous number will equal the next number so if there are 5 ways to tile a 4x2 area and 3 ways to tile a 3x2, it will be 5+3 ways which equal 8 ways to tile a 5x2 area

The general solution is $\phi^n$ + $\Phi^n$ , for n by 2 area.

Notice that horizontal dominoes have to come in pairs, if we use the condition that n 2x1 dominoes are needed to fill the 2xn area. Using an abstract notation where "1" represents one vertical domino and "2" represents a pair of horizontal dominoes, the solutions can be enumerated as:

11111 - 5 vertical dominoes only has 1 solution.

2111, 1211, 1121, 1112 - one pair of horizontal dominoes has 4 solutions.

221, 212, 122 - two pairs of horizontal dominoes has 3 solutions.

1 + 4 + 3 = 8.

Also notice that this notation enables us to enumerate the number of possible solutions using factorials: 11111 -> 5!/(5!•0!) = 1, 2111 -> 4!/(3!•1!) = 4, 221 -> 3!/(1!•2!) = 3.

With these tools, one can solve the bonus challenge by tapping into Pascal's triangle and how that leads to the Fibonacci sequence ... Try it!

Here's another challenge: use 3x1 dominoes in 3xn areas, what function characterizes the nth solution?

An even better challenge: use Hx1 dominoes in Hxn areas, what function characterizes the nth solution?

Using 1 x 2 area, there are 7 ways to tile 4 x 2 areas to make it a 5 x 2 area without repetition. Using 2 x 2 areas, there are 1 way to tile 3 x 2 areas to make it a 5 x 2 area without repetition. So total number is 7 + 1 = 8 ways.