Domino Functions | Programmer Luddite

At Gram and Gramp’s this weekend we played dominos, and the question came up of counting a set of dominos. In particular, Gramps wanted to know how many dominos there were in a set with double twelves.

After we were done playing, we lined them all up in the “domino triangle” with and Emery and I figured it out. The domino triangle is simply an arrangement of dominos with double zero in one corner, the zero-one next to it, followed by zero-two (etc.), and with the double one at the end, followed by the double two (etc.). Here is a partial rendering of the triangle for our double nine set:

+-+   +-+         +-+
|0|   |0|         |0|
+-+   +-+   ...   +-+
|0|   |1|         |9|
+-+   +-+         +-+

+-+         +-+
|1|         |1|
+-+   ...   +-+
|1|         |9|
+-+         +-+

...

+-+
|9|
+-+
|9|
+-+

To start, let $n$ equal the number of the largest double (twelve, if our case). We’re looking for $f(n)$ , which is the number of dominos in a set with largest double $n$ . Simply counting the dominos in the triangle gives us a values for our function, but not the one we want:

  n  | f(n)
-----+-------
  0  |   1
  6  |  28
  9  |  55
 12  |  ??

Before dealing with $f(n)$ , let $g(n)$ denote the number of doubles in the set. A quick glance at the triangle will show that the formula for this function is

$g(n)=n+1$

because there is one double for each

$[0, n] = \{x \in \mathbb{N} \,|\,0 \le x \le n\}$

Now thinking back to the “domino triangle”, it’s easy to see that $g(n)$ is both the width (base) and the height of the triangle. If you recall from planar geometry, the area of a triangle is half it’s base times height:

$\frac{base \times height}{2}$

So a first guess at $f(n)$ would be this:

$f(n)=\frac{(g(n))^2}{2}$

But that isn’t correct. Thinking back to the domino triangle quickly shows why. If you were to take two copies of the triangle to make a rectangle (the reason the triangle area formula works), you’d see that you’d have to offset them by one domino in one direction, so the rectangle is actually $g(n)$ by $g(n) + 1$ . So the right formula is this:

$f(n)=\frac{g(n)\,(g(n) + 1)}{2}$

Simplifying by inlining the formula for $g(n)$ yields:

$f(n)=\frac{(n + 1)(n + 2)}{2}$

This turns out to be the correct formula, and yields 91 when its argument is twelve. Thus a set of double twelve dominos will have 91 dominos.

What was particularly striking as Emery and I worked through the formulas, is that Emery had more trouble with the larger multiplication (which he hasn’t done in school) than following the function notation, doing the step-wise evaluation of the functions, and even the function nesting.

One thought on “Domino Functions”

Bill Beers on June 25, 2013 at 10:04 pm said:
As I read this post, I had a flashback to one of my college math courses(Number Theory), where my professor told us of a German math prodigy named, Carl Friedrich Gauss.

There is a well known story about Karl Friedrich Gauss when he was in
elementary school. His teacher got mad at the class and told them to
add the numbers 1 to 100 and give him the answer by the end of the
class. About 30 seconds later Gauss gave him the answer.

Looking at your triangle it clicked.
1 + 2 + 3 + … + n

If you take the sequence and add it to the reverse sequence, shown below…
```
1      2    3    4    5    6    7    8    9   10   11   12
+    +    +    +    +    +    +    +   +     +    +     +
12   11  10   9    8    7    6    5    4     3     2     1
=
13   13   13   13   13   13   13   13   13   13   13 =  12(13) = 156 or n(n+1)
```
which is double the total, so take 1/2 of that to find the total = 78
78 != 91 so this made me go, hmmm
But, since the dominos are 0 based, it really is 1+…+13 so plug in 13 for n
```
13(14)
--------      =  182/2 = 91
2
```
Math is cool.

Comments are closed.