What is a Domino?

What is a Domino?

For our purposes, a domino is a 2 x 1 rectangle:

• Numbers on the dominos don’t matter
• Arithmetic will be about something else (stay tuned)

Q. How many ways can we tile a 3 \(\times\) n rectangle
with 2 \(\times\) 1 dominoes?

Rules

• no overlap
• no gaps

Notation

• u(n) = number of ways to tile a 3 \(\times\) n rectangle
• U(n) = listing of all tilings of a 3 \(\times\) n rectangle
• u(n) = |U(n)|

Example: What is u(2)? What is U(2)?

u(2) = 3

Here’s U(2):

u(2) = 3

Here’s U(2):

How do we know there aren’t any more?

• “I couldn’t find any more” is not an acceptable answer.

Your Turn

How much of this table can you fill out?

Which values of u(n) are easy?

Which values of u(n) are easy?

If n is odd, then u(n) = 0.

• Area of 3 \(\times\) n rectangle is 3n, which is odd when n is odd.
• Area covered by dominos is 2d (d = number of dominos), which is even.
• So it isn’t possible to tile a 3 \(\times\) n rectangle with dominos when n is odd.

What is u(4)?

What is u(4)?

u(4) = 11

u(6) = ??

u(8) = ??

Filling out the table

These get hard fast… We need some help.

We need some help

To solve this problem, we need

• an easier problem to practice on
• a more systematic approach

Let’s try tiling 2 \(\times\) n rectangles

Notation

• t(n) = number of ways to tile a 2 \(\times\) n rectangle
• T(n) = listing of all tilings of a 2 \(\times\) n rectangle
• t(n) = |T(n)|

Example: What is t(2)? What is T(2)?

t(2) = 2

Here’s T(2):

Your Turn

How much of this table can you fill in?

T

A table for t

What is Arithmetic?

Wikipedia says:

Arithmetic is a branch of mathematics that consists of the study of numbers, especially the properties of the traditional operations on them – addition, subtraction, multiplication and division.

The primary operations are addition and multiplication.

What is Domino Arithmetic?

Domino arithmetic is a branch of mathematics that consists of the study of numbers domino tilings, especially the properties of the traditional operations on them – addition, subtraction, multiplication and division.

We need some operations on tilings

If A and B are tilings, what are

• A + B?
• A \(\cdot\) B = A * B = AB?

(Note: there is a little white lie on this slide that we will fix in a moment.)

Domino Algebra

We would like domino algebra to be

• useful
• somewhat familiar

Can you come up with definitions of addition and multiplication so that

(A+B) (C+D) = AC + AD + BC + BD

Examples:

Domino Algebra

Can you come up with definitions of addition and multiplication so that

(A+B) (C+D) = AC + AD + BC + BD

Examples:

( + ) ( + )	=	+ + +
( + ) ( + )	=	+ + +
	=	+ 2 +

Note:

• multiplication does not commute!
• addition does commute if we are not interested in the order of our list.

Equations for T(n)

T(n) = T(n-1) + T(n-2)

So t(n) = t(n-1) + t(n-2) [Fibonacci]

T Time

Let T be the list of all tilings of rectangles with 2 rows (and any number of columns).

Wait, what is T(0)? Tilings of a 2 \(\times\) 0 rectangle?

• How many are there? (What is t(0)?)
• How should we denote this?

The Fundamental Equation for T

Can you Solve for T?

Fundamental Equation

Solving for T

Technically, we need a left multiplicative inverse, but let’s stick with this notation.

Do you Recognize This?

T =

1 1 - -

=

1 1 - ( + )

Geometric Series!

T =

1 1 - ( + )

= 1 + ( + ) + ( + )2 + ( + )3 + \(\cdots\)

Using letters

\[ \begin{align} T &= \frac{1}{1 - (x + y^2)} = \sum_{k=0}^\infty (x + y^2)^k \\ & = \sum_{k,j \ge 0} \binom{k}{j} x^j y^{2(k-j)} \\ & = \sum_{m,j \ge 0} \binom{m+j}{j} x^j y^{2m} \tag{$m = k-j$} \end{align} \]

So the number of tilings with \(j\) and \(m\) is \(\binom{m+j}{j}\).

This gives us another way to compute t(n)

Example:

\[ \small \begin{align*} t(8) &= \binom{0+4}{0} + \binom{2 + 3}{2} + \binom{4 + 2}{4} + \binom{6 + 1}{6} + \binom{8 + 0}{8} \\ &= 1 + 10 + 15 + 7 + 1 \\ &= 34 \end{align*} \]

One more slight of hand

Now let \(x = y = z\) (a domino is a domino is a domino – ignore orientation).

\[ \begin{align} T &= 1 + zT + z^2 T \end{align} \]

So

\[ \begin{align} T &= \frac{1}{1 - z - z^2}\\ \end{align} \]

Geometric Series to the Rescue

We would like to write

\[ \begin{align} T &= \frac{1}{1 - z - z^2} = \sum_{n=0}^\infty t_n z^n \\ \end{align} \]

as

\[ \begin{align} T &= \frac{1}{1 - z - z^2} = \frac{A}{1 - \alpha z} + \frac{B}{1-\beta z}\\[5mm] & = A[1 + \alpha z + \alpha^2 z^2 + \cdots] + B[1 + \beta z + \beta^2 z^2 + \cdots]\\\\ \end{align} \]

So \(t_n = A \alpha^n + B \beta^n\).    We just need to determine \(\alpha\), \(\beta\), \(A\), and \(B\).

Finding \(\alpha\), \(\beta\), \(A\), and \(B\)

\[ \begin{align} T &= \frac{1}{1 - z - z^2} = \frac{A}{1 - \alpha z} + \frac{B}{1-\beta z} = \frac{A(1-\beta z) + B(1-\alpha z)}{(1-\alpha z)(1 - \beta z)} \\[5mm] \end{align} \]

Finding \(\alpha\), \(\beta\), \(A\), and \(B\)

\[ \begin{align} T &= \frac{1}{1 - z - z^2} = \frac{A}{1 - \alpha z} + \frac{B}{1-\beta z} = \frac{A(1-\beta z) + B(1-\alpha z)}{(1-\alpha z)(1 - \beta z)} \\[5mm] \end{align} \]

Denominator:

\[ \begin{align} 1 - z - z^2 & = 1 - (\alpha + \beta)z + \alpha\beta z^2 \\ 1 &= \alpha + \beta\\ -1 & = \alpha \beta \end{align} \]

Finding \(\alpha\), \(\beta\), \(A\), and \(B\)

\[ \begin{align} T &= \frac{1}{1 - z - z^2} = \frac{A}{1 - \alpha z} + \frac{B}{1-\beta z} = \frac{A(1-\beta z) + B(1-\alpha z)}{(1-\alpha z)(1 - \beta z)} \\[5mm] \end{align} \]

Denominator:

\[ \begin{align} 1 - z - z^2 & = 1 - (\alpha + \beta)z + \alpha\beta z^2 \\ 1 &= \alpha + \beta\\ -1 & = \alpha \beta \end{align} \]

Numerator:

\[ \begin{align} 1 &= A (1 -\beta z) + B (1-\alpha z) = (A + B) - (A \beta + B \alpha) z \\ 1 &= A+B \\ 0 &= A\beta + B \alpha \end{align} \]

Four equations, four unknowns

\[ \begin{align} \alpha + \beta & = 1 & \alpha \beta &= -1 \\ A + B &= 1 & A\beta + B \alpha &= 0 \end{align} \]

Finding \(\alpha\), \(\beta\)

\[ \begin{align} \alpha + \beta & = 1 & \alpha \beta &= -1 \\ \end{align} \]

From this we get

\[ \begin{align} -1 &= \alpha \beta = \alpha (1-\alpha) = \alpha - \alpha^2 & 0 & = \alpha^2 - \alpha - 1\\ \alpha &= \frac{1 + \sqrt{5}}{2} \approx 1.618 & \beta &= \frac{1 - \sqrt{5}}{2} \approx -0.618\\ \end{align} \]

Recall that \(t_n = A\alpha^n + B \beta^n\).

Since \(|\beta| < 1\), \(|\beta|^n \searrow 0\) as \(n \to \infty\), so we can basically ignore that part:

\[ \fbox{$t_n \approx A \alpha^n$} \]

Finding \(A\) (and \(B\))

\[ \begin{align} \alpha + \beta & = 1 & \alpha \beta &= -1 \\ A + B &= 1 & A\beta + B \alpha &= 0 \\[12mm] \end{align} \]

\[ \begin{align} 0 &= A \beta + (1-A) \alpha \\ 0 &= A \beta + \alpha - A \alpha \\ 0 &= A (\beta -\alpha) + \alpha \\[5mm] A &= \frac{\alpha}{\alpha - \beta} = \frac{\alpha}{\sqrt{5}}\\ B &= 1 - A = \frac{\alpha - \beta}{\alpha - \beta} - \frac{\alpha}{\alpha - \beta} = \frac{-\beta}{\sqrt{5}} \end{align} \]

Putting it all together

\[ \begin{align} t_n &= A \alpha^n + B \beta^n = \frac{\alpha^{n+1}}{\sqrt{5}} - \frac{\beta^{n+1}}{\sqrt{5}} \\[5mm] t_n &\approx A \alpha^n = \frac{\alpha^{n+1}}{\sqrt{5}} \\[12mm] \end{align} \]

where

\[ \begin{align*} \alpha &= \frac{1 + \sqrt{5}}{2} \approx 1.618 & \beta &= \frac{1 - \sqrt{5}}{2} \approx -0.618\\ \end{align*} \]

Computation

t <- function(n) {
  alpha <- (1 + sqrt(5))/2
  beta  <- (1 - sqrt(5))/2
  A <-   alpha / sqrt(5)
  B <- - beta  / sqrt(5)
  A * alpha^n + B * beta^n
}  

t(0:20)

 [1]     1     1     2     3     5     8    13    21    34    55    89   144
[13]   233   377   610   987  1597  2584  4181  6765 10946

Fundamental Equation for U

Fundamental Equation for U

Fundamental Equations for U

Algebra

We start with 3 equations and 3 unknowns, \(U\), \(V\), and \(\Lambda\).

\[ \begin{align} U &= 1 + z^3 U + z^2 V + z^2 \Lambda \\ V &= z U + z^3 V \\ \Lambda &= z U + z^3 \Lambda \\ \end{align} \]

We can use these to express \(V\) and \(\Lambda\) in terms of \(U\).

\[ \begin{align} V &= (1 - z^3)^{-1} z U\\ \Lambda &= (1 - z^3)^{-1} z U\\ \end{align} \]

Plugging these in, we now have just one equation with one unknown.

\[ \begin{align} U &= 1 + z^3 U + z^2 (1 - z^3)^{-1} z U + z^2 (1 - z^3)^{-1} z U \end{align} \]

Solving for \(U\)

\[ \begin{align} U &= 1 + z^3 U + z^2 (1 - z^3)^{-1} z U + z^2 (1 - z^3)^{-1} z U \end{align} \]

\[ \begin{align} 1 &= U - z^3 U - z^2 (1 - z^3)^{-1} z U - z^2 (1 - z^3)^{-1} z U \\ 1 &= \left[1 - z^3 - z^2 (1 - z^3)^{-1} z - z^2 (1 - z^3)^{-1} z\right] U \\ U &= \frac{1}{\left[(1 - z^3) - z^2 (1 - z^3)^{-1} z - z^2 (1 - z^3)^{-1} z\right]} \\ U &= \frac{1 - z^3}{\left[(1 - z^3)^2 - 2z^3\right]} \\ \end{align} \]

Let \(w = z^3\) (dominoes come in threes)

\[ \begin{align} U &= \frac{1 - z^3}{\left[(1 - z^3)^2 - 2z^3\right]} = \frac{1 - w}{\left[(1 - w)^2 - 2w\right]} \\ &= \frac{1 - w}{\left[1 -2w + w^2 - 2w\right]} \\ &= \frac{1 - w}{\left[1 - 4w + w^2 \right]} \\ & = \frac{A}{1 - \alpha w} + \frac{B}{1-\beta w}\\ & = A[1 + \alpha w + \alpha^2 w^2 + \cdots] + B[1 + \beta w + \beta^2 w^2 + \cdots]\\\ &= \sum A \alpha^n w^n + B \beta^n w^n \end{align} \]

Same story as before (but different constants)

\[ \begin{align} u_n &= A \alpha^n + B \beta^n \\ & = \mbox{number of ways to tile $3 \times 2n$ with $3n$ dominoes} \end{align} \]

We just need to determine \(\alpha\), \(\beta\), \(A\), and \(B\).

Using algebra similar to the \(2 \times n\) case, we get

\[ \begin{align} \alpha &= 2 + \sqrt{3} & \beta &= 2 - \sqrt{3} \\ A &= \frac{1}{2} + \frac{\sqrt{3}}{6} & B &= \frac{1}{2} - \frac{\sqrt{3}}{6}\\ \end{align} \]

Computation

u <- function(n) {
  alpha <- 2 + sqrt(3)
  beta  <- 2 - sqrt(3)
  A <-   1/2 + sqrt(3) / 6
  B <-   1/2 - sqrt(3) / 6
  A * alpha^n + B * beta^n
}
u(0:20)

 [1]            1            3           11           41          153
 [6]          571         2131         7953        29681       110771
[11]       413403      1542841      5757961     21489003     80198051
[16]    299303201   1117014753   4168755811  15558008491  58063278153
[21] 216695104121

Inquire within

https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf

You can find these slides at…

https://rpruim.github.io/talks/domino-arithmetic/domino-arithmetic-slides.html