Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-09-20 23:19:27

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Domino Tilings

In how many ways can a 3 x 100 chessboard be tiled with dominoes?

Last edited by Agnishom (2014-09-20 23:20:03)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#2 2014-09-21 01:53:58

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

Hi Agnishom;

What kind of tilings?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2014-09-21 01:59:05

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Domino Tilings

bobbym wrote:

What kind of tilings?

Dominoes.


Bassaricyon neblina

Offline

#4 2014-09-21 02:04:46

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

That looks like the right answer!

I am getting 31208688988045323113527764971.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2014-09-21 02:31:04

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

Why am I getting one less than that?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#6 2014-09-21 02:33:28

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

Because you should add one to your answer.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2014-09-21 03:02:19

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

And then add another one to it?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#8 2014-09-21 03:03:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

No, stop adding when it agrees with my answer.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2014-09-21 03:09:42

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

Did you use this formula: b214541715bc76427421e8b1230c2be0.png


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#10 2014-09-21 03:11:37

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

I used everything but that formula!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2014-09-21 03:14:18

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

Something mysterious happened four hours ago! Did you do it? Are you 193.11.79.67?

Last edited by Agnishom (2014-09-21 03:15:32)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#12 2014-09-21 03:20:27

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

That is a Swedish IP address and most likely a proxy or a VPN. I do not use such things. What happened?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2014-09-21 03:21:51

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

Somebody removed the formula I used from Wikipedia


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#14 2014-09-21 03:23:39

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

Where? Here?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#15 2014-09-21 03:32:22

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

No, while solving the problem.

Must be a wiki troll


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#16 2014-09-21 03:34:20

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

Where was it removed?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#17 2014-09-21 03:56:29

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

From the wikipedia


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#18 2014-09-21 03:59:35

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

There are numerous editors f\on Wikipedia, some of my stuff has been erased too.

Also, it appears your formula is getting the wrong answer so maybe it was a good idea to remove it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#19 2014-09-21 05:42:53

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,030

Re: Domino Tilings

I am getting the same number as bobbym.

The recurrence is:


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#20 2014-09-21 05:47:09

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

There are closed forms and gf's too!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#21 2014-09-21 05:59:15

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,030

Re: Domino Tilings

I thought there might be, but I was too lazy to try and find them.

It would be interesting to do this for larger tables (4xn, 5xn,...).


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#22 2014-09-21 06:01:00

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 108,752

Re: Domino Tilings

There is a good chance it has already been done. Tilings are very popular problems.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#23 2014-09-21 06:10:48

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,650
Website

Re: Domino Tilings

It has been done for m by n already. See the formula.

Can you please explain me the reccurence?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#24 2014-09-21 06:21:07

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,030

Re: Domino Tilings

Well, I derived it from a double recurrence:

where

is the number of ways to cover a 3xn board and
is the number of ways to cover a 3xn board with one more square appended.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

Board footer

Powered by FluxBB