Domino tilings

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 оценки

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 оценки

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

From the lesson

Linear recurrences. The Fibonacci sequence

We start with a well-known "rabbit problem", which dates back to Fibonacci. Using the Fibonacci sequence as our main example, we discuss a general method of solving linear recurrences with constant coefficients.

Fibonacci’s rabbit problem9:36

Fibonacci numbers and the Pascal triangle7:56

Domino tilings8:26

Vending machine problem10:07

Linear recurrence relations: definition7:53

The characteristic equation8:43

Linear recurrence relations of order 211:02

The Binet formula11:21

Sidebar: the golden ratio9:12

Linear recurrence relations of arbitrary order8:44

The case of roots with multiplicities12:10

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

One more combinatorial interpretation of Fibonacci numbers is as follows.

Suppose you have a rectangle of size 2 times n.

And you want to cover it with domino tiles of size 1 times 2.

And these tiles can be arranged horizontally or vertically.

Okay, so the question is,

in how many ways can you cover this rectangle by domino tiles?

Let's say, You can do something like this.

[COUGH] Okay, say, if you have a rectangle of size 2 times 3.

Well, you can split it into domino tiles in three ways.

Well, here they are.

And what is the answer for arbitrary n?

For n = 3, there are 3 tilings.

So what happens for n = 2?

There are just two of them.

And for n = 1, the problem is trivial.

There is just one domino tile.

So what happens for an arbitrary n?

The answer is as follows.

That number of tilings of this rectangle 2 times n,

Is equal to the Fibonacci number.

Number of tilings of 2 x n rectangle is equal

to the Fibonacci number, but not the nth one.

You need to shift it by 1,

F(n+1) as you see on this example.

Okay, why is it so?

Here's the explanation.

Suppose, That we have a tiling of a rectangle.

And let's take the upper left corner.

And it is covered by some domino.

And there are two possibilities.

It can be either, Covered by vertical domino like this.

And in this case, the remaining part is a rectangle of size 2x(n-1).

Or it can be covered horizontally.

This means that just below it, you also need to have a horizontal tile.

And the remaining part of the rectangle is

a smaller rectangle of size 2x(n-2).

So each tiling is either of this type or of that type.

So you see that, again, the number of tilings satisfies the same relation.

So if you denote the number of tilings by T(n),

then T(n) = T(n-1), which corresponds to this case.

So you put one domino and you need to cover the remaining part, +T(n-2).

First you put these two dominoes horizontally.

And then you need to cover the remaining part.

And you can do it in this many ways.

And the only difference from the Fibonacci sequence are the initial conditions.

So we have already seen that

T(1) = 1, and T(2) = 2.

So T(3) will be 3, T(4) will be 5, etc., etc.

So you see that in this case,

T(n) will be equal to the Fibonacci number F(n+1).

Okay, and alternatively,

you can look at this in the following way that,

The number F(n+1), Is the number of ways.

F(n+1) is the number of presentations of the number n as a sum of 2's and 1's.

So is the number of ways,

Of presenting, n

as a sum of 1's and 2's.

Where the order is important, so, Say,

1+2 and 2+1 are different presentations.

These are different compositions.

Their relation with this description is obvious.

So having a tiling, you can construct such a presentation.

Say, if you have a vertical tile, you replace it by sum of the 1.

And if you have a pair of horizontal tiles, you replace it by 2.

So here in this case,

we have 1+2+1+1.

These two guys are vertical.

These are horizontal.

So you have 2+1, and this gives you,

This gives you such a presentation of the number 8.

Okay, this description will be generalized in our next example.

[MUSIC]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play