This was from google's interview question.

[adhiluhur]

So, Google recently interviewed one of my friend as an employee candidate.

How many ways can a two by n rectangular space be filled with one by one, two by one and two by two tiles?
Give your answer as an explicit formula in terms of n.​

 

[dacruick]

does orientation matter? If n =2, how many different ways can I place 2 2x1 tiles?

 

[karthik5]

If only the combination of the three are considered then it is,
1 + n/2 + n/2(n/2+1). i solved it as follows, assume n is even. when fully filled with 2*2 tiles then it is "1" combination. Removing one after the other and fill with 2*1 tiles gives "n/2" combinations. During each step in this removal process, instead of 2*1 we can use 1*1 --- this gives summation (i=1 to i=n/2) 2*i which is n/2(n/2+1).

 

[Bacle2]

How about the spatial configuration? Say I have a1 2x2's, a2 2x1's and a3 1x1's and we put the 2x2's in different positions, e.g., we permute/exchange the placing of a 2x2
with 2 1x1's , but the amount of each remains the same, is the configuration considered different?

 

[Robert1986]

Certainly this calls for a recurrence relation. The recurrence isn't that hard to come up with. It seems like the point of the question might have been whether or not your friend can solve a recurrence. This seems important for a programmer since a closed form solution is (probably) always better than a recurrence.

 

[pwsnafu]

1 + n/2 + n/2(n/2+1). i solved it as follows, assume n is even. when fully filled with 2*2 tiles then it is "1" combination. Removing one after the other and fill with 2*1 tiles gives "n/2" combinations.

Consider n = 4, and the case when we have one 2*2 and two 2*1. There's three ways: the 2*2 first, in the middle, and at the end. Does rotational symmetry matter?

Consider n= 6, and the case when we have two 2*2 and two 2*1. Let's suppose that we do have rotational symmetry. Then we have

1. 2*2, 2*2, 2*1, 2*1
2. 2*2, 2*1, 2*2, 2*1
3. 2*2, 2*1, 2*1, 2*2
4. 2*1, 2*2, 2*2, 2*1

which is not equal to n/2.

PS. If I was the assessor, I wouldn't be looking for the solution per se. But whether you completely write your assumptions down. The problem is currently ill-defined, and this is probably the common source of bugs.

 

[JHamm]

My attempt at a solution:

First I took the simpler problem of 'n' being even and assumed that each 2xn rectangle can be uniquely determined by a series of 2x2 blocks, each 2x2 block has 8 possible ways to be constructed which means that for even n the total number of combinations is
$$\sqrt{8^n}$$

Then if n is odd I took the rectangle of 2x(n-1) and calculated the combinations of that one, then I multiplied that by the possible ways to construct the remaining 2x1 rectangle (2) and multiplied this by the number of positions it can be placed in the sequence $\frac{n+1}{2}$ which gives the number of combinations if n is odd as

$$\sqrt{8^{n-1}}(n+1)$$

 

[karthik5]

Consider n = 4, and the case when we have one 2*2 and two 2*1. There's three ways: the 2*2 first, in the middle, and at the end. Does rotational symmetry matter?

Consider n= 6, and the case when we have two 2*2 and two 2*1. Let's suppose that we do have rotational symmetry. Then we have

1. 2*2, 2*2, 2*1, 2*1
2. 2*2, 2*1, 2*2, 2*1
3. 2*2, 2*1, 2*1, 2*2
4. 2*1, 2*2, 2*2, 2*1

which is not equal to n/2.

PS. If I was the assessor, I wouldn't be looking for the solution per se. But whether you completely write your assumptions down. The problem is currently ill-defined, and this is probably the common source of bugs.

i assume that the position and orientation of tiles does not matter. so if n=6
2*2, 2*2, 2*1, 2*1
2*2, 2*1, 2*1, 2*1, 2*1
2*1, 2*1, 2*1, 2*1, 2*1, 2*1
which is equal to n/2.

 

[D H]

If only the combination of the three are considered then it is,
1 + n/2 + n/2(n/2+1). i solved it as follows, assume n is even. when fully filled with 2*2 tiles then it is "1" combination. Removing one after the other and fill with 2*1 tiles gives "n/2" combinations. During each step in this removal process, instead of 2*1 we can use 1*1 --- this gives summation (i=1 to i=n/2) 2*i which is n/2(n/2+1).

A nicer way to write this: $(1+n/2)^2$. An even nicer way is $(n+2)^2/4$. This latter nicely generalizes to the case n is odd, $(n+2)^2- (n\;\text{mod}\;2))/4$.

However, were I doing the interview I would have stopped you early on in your reasoning process (assuming you were clear about your assumptions) and said that this is a tiling problem, not a how to fill a knapsack problem.

My attempt at a solution:

First I took the simpler problem of 'n' being even and assumed that each 2xn rectangle can be uniquely determined by a series of 2x2 blocks, each 2x2 block has 8 possible ways to be constructed which means that for even n the total number of combinations is
$$\sqrt{8^n}$$

This misses a whole bunch of solutions. This one, for example, for a 2x4 rectangle:

+--+------+--+
|  |      |  |
|  |      |  |
|  |      |  |
+--+------+--+

Ignoring symmetries, you are correct than a 2x2 block has eight possible layout patterns. Two of these have a 2x1 oriented vertically on the left and two more have a 1x1 stacked atop a 1x1 on the left. The remaining four cannot be split vertically down the middle without splitting a tile in half. So, one way to look at the number of layouts for a 2x2 block is

$$S_2 = 2S_1 + 4S_0$$

where S_n is the number of patterns of the 2xn problem. There is one way to solve the 2x0 problem, two ways to solve the 2x1 pattern: S₀=1, S₁=2.

This generalizes to larger values of N, but we are leaving something out:

$$S_N = 2S_{N-1} + 4S_{N-2} + \text{omitted terms}$$

What is being left out is an initial sequence on the left that forms a running bond pattern. For example, lay a 2x1 tile horizontally followed by a 1x1 tile. Atop this lay a 1x1 tile followed by a 2x1 tile, forming a 2x3 block. Reversing the order yields a distinct (but symmetric) pattern. There are two running bond patterns of length 3, two of length 5, etc. Adding these running bond patterns yields

$$S_N = 2S_{N-1} + 4S_{N-2} + \sum_{k=0}^{\lfloor{\frac{N-3}2}\rfloor} 2S_{N-3-2k}$$

The seeds to the recursion relation are $S_0=1,\;S_1=2$.

The first several values for this sequence are 1,2,8,26,298,1004,3394,11456,... I can't see a closed form solution to this recursion relationship.

 

[AlephZero]

Another way to attack this leading to recurrence relations would be:

Suppose the tiling for 2xn contains at least one 2x2 tile. Use the leftmost 2x2 tile to splits the rectangle into smaller rectangles 2xr and 2xs, where (r = 0, 1, ... n-2, r+s = n-2, and the 2xr rectangle contains no 2x2 tiles.

If there is no 2x2 tile but there is at least 2x1 tile orientated "across" the rectangle, that similarly splits the rectangle into two parts.

In the remaining cases the rectangle splits into two 1xn rectangles, and for each of those the number of tilings is the number of ways to arrange k 2x1 tiles and (n-2k) 1x1 tiles in a row.

Converting all that into an explicit formula seems hard. My first inclination would be to see what happens for a few small values of n, in the hope that something "interesting" will show up.