COMBINATORICS at its PEAK...

A "domino" is a 1 by 2 or a 2 by 1 rectangle.
A 'domino tiling' of a region of the plane is a way of covering it (and only it) completely by non-overlapping dominoes. For example: There's 1 domino tiling of a 2 by1 rectangle & 2 tilings of a 2 by 2 rectangle. (1 consisting of 2 horizontal dominoes & 1 containing of 2 vertical ones) How many domino tilings of a 2 by 10 rectangle are there?


The answer is 89.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Ivander Jonathan
Feb 1, 2015

There are 2 ways to arrange the dominoes in general, horizontal and vertical. Horizontal fills 2 spaces horizontally using 2 dominoes and vertical fills a space horizontally using a domino. Assuming A is horizontally and B is vertically.

We must count arrangements of:

A A A A A AAAAA has 1 arrangement.

B B A A A A BBAAAA has 15 arrangements.

B B B B A A A BBBBAAA has 35 arrangements.

B B B B B B A A BBBBBBAA has 28 arrangements.

B B B B B B B B A BBBBBBBBA has 9 arrangements.

B B B B B B B B B B BBBBBBBBBB has 1 arrangement.

So, in total, the number of arrangements is 89 \boxed{89}

That was a good 1... But u could've directly managed it without taking cases by using recursion.

SOURAV MISHRA - 6 years, 4 months ago

Let a n a_n be the number of ways to tile a 2 by n rectangle.

We can either start off with a vertical tile, which leaves a 2 × ( n 1 ) 2 \times (n-1) rectangle, or a horizontal tile, which leaves a 2 × ( n 2 ) 2 \times (n-2) rectangle. There are a n 1 a_n-1 ways to arrange a 2 x (n-1) rectangle and a n 2 a_n-2 ways to arrange a 2 x (n-2) rectangle.

Hence a n = a n 1 + a n 2 a_n = a_n-1 + a_n-2 .

There is one way to tile a 1 × 1 1 \times 1 rectangle and 2 ways to tile a 2 × 2 2 \times 2 rectangle, so a 1 = 1 a_1 = 1 and a 2 = 2 a_2 = 2 .

a 3 = 3 a_3 = 3

a 4 = 5 a_4 = 5

a 5 = 8 a_5 = 8

a 6 = 13 a_6 = 13

a 7 = 21 a_7 = 21

a 8 = 34 a_8 = 34

a 9 = 55 a_9 = 55

a 10 = 89 a_{10}= \boxed{89}

Sourav Mishra
Jan 15, 2015

Hint. USE THE CONNECTION OF THE PROBLEM WITH THE FIBONACCI SEQUENCE'S TERM I'll try to post the solution in the near future.

I wonder what your near future is...

Peter van der Linden - 4 years, 8 months ago

Studying the domino tilings of 2xN rectangles, we first note that A 2x1 rectangle has 1 DT A 2x2 rectangle has 2 DT Say Xn is the number of DT's on an 2xn rectangle. We can check that all DT's on a rectangle can either be done by adding one final vertical domino, or two final horizontal dominos. The number of ways of tiling the 2xN rectangle with one final domino is equal to the number of ways of tiling a 2x(N-1) rectangle. For the last two horizontal dominos, the number of ways of tiling that particular family of rectangles is equal to the number of ways of tiling a 2x(N-2) rectangle. So we find the recurrence Xn = X(n-1) + X(n-2), X1=1 , X2=2 so Xn is the (n+1)th Fibonacci number, therefore X10=89

Enzo Iubini - 1 year, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...