Dominoes, combinations, sums and reductions

Jun122023

When in Cuba, and leaving behind iPad and all, I was idling around how many Domino stones there are in a game of Dominoes that goes from 0 to 9.

Basically, we have all combinations of numbers 0-9 plus a doubled stone for each number, i.e.

{10 \choose 2} + 10 = \frac{10!}{2!(10 - 2)!} + 10 = 55

There are 55 domino stones in a game of dominoes

With my son we arrived at the number by thinking:

For number 0, 0 can be combined with all other numbers: 10 dominoes
For number 1, it can be combined with all others, however, 1 combination (0,1) is already present: 9 dominoes
For each subsequent number, you add the missing combinations - it is always 1 less than the previous one.

Mathematically, you can express this as

\sum_{n=1}^{10} n = 55

The numbers, when written out, would be reversed compared to the textual description

Now, if you arrange the numbers in pairs, where you take the left and right boundary of the remaining sequence of numbers you end up with

1+2+3+4+5+6+7+8+9+10

\Rightarrow (10+1) + (9+2) + (8+3) + (7+4) + (6+5)

If you generalize this pattern you get that the sum of the pair is always one more than the biggest number, and you can form pairs up to the half of the biggest number:

\sum_{n=1}^{z} n = (z+1)\frac{z}{2}

Intuitively, this seems to work out for any sequence starting with 1 up to some arbitrary number n.

At this point I attempted a proof by induction (and I’m pretty sure I got the details wrong, but I was happy at the end), which I hadn’t done for several decades at this point.

Let’s establish the baseline, and settle that the equation works for n = 1:

\sum_{n=1}^{1} n = (1+1)\frac{1}{2} = 2 * 0,5 = 1

That is correct.

Now, for the next step we get that

\sum_{n=1}^{x+1} n = \sum_{n=1}^{x} n + (x+1)

by the very definition of a sum. Substituting our equation on both sides, we get

((x+1)+1)\frac{x+1}{2} = (x+1)\frac{x}{2} + (x+1)

Let’s multiply both sides by 2:

(x+2)(x+1) = x(x+1) + 2(x + 1)

Let’s expand!

x^2+3x+2 = x^2 + 3x + 2

The point being that this holds true for any x, we can expand the solution for the previous step into the solution for the next step, coming all the way down to our baseline. Looking chill from this side of the screen!

See, there is no boredom with a pen and a piece of paper :)