Factoring dice

Required reading for this post: Generating functions

We have two normal six-sided dice. We roll both of them, and sum the number of pips. There is a certain probability that we get a 2, or a 3, or a 4, and so on all the way to 12. What we want is a new pair of six-sided dice with the exact same probabilities as the normal dice, but with different numbers of pips on the faces. Each side must have a positive integer number of pips. Can you create such a pair of dice?

To solve this problem, we must have a better understanding of generating functions. Each sequence generates a unique function. Each function corresponds to a unique sequence. If we add two generating functions together, the resulting function corresponds to the sum of their respective sequences. But what happens if we multiply generating functions together?

Let's say we have some arbitrary sequence {a₀, a₁, a₂, a₃, a₄, a₅, ...} and another arbitrary sequence {b₀, b₁, b₂, b₃, b₄, b₅, ...}. Let's see what happens when we multiply them together.

F = a₀ + a₁*x + a₂*x² + a₃*x³ + a₄*x⁴ + a₅*x⁵ + ...
G = b₀ + b₁*x + b₂*x² + b₃*x³ + b₄*x⁴ + b₅*x⁵ + ...
F*G = a₀*b₀ + (a₀*b₁ + a₁*b₀)*x + (a₀*b₂ + a₁*b₁ + a₂*b₀)*x² + ...

It might be a little difficult to make sense out of what's going on here. It's important to pay attention to the subscripts. Pay attention to the sum of the subscripts. I'll make this a bit more explicit.

All the sums in the first box add up to zero. All the sums in the next box add up to 1. The sums in the next box add up to 2. Note that every possible way sum to 2 with two non-negative integers is represented in that box. This pattern will continue. The next box would contain every possible way to sum to 3. The next box contains all the sums to 4. And so on.

Have you figured out yet how this might relate to the dice? The answer follows.

We can say that each sequence represents some sort of generalized dice. a_j represents the number of ways for dice "a" to roll the number j, and b_k represents the number of ways for dice "b" to roll the number k. If we multiply the functions generated by each sequence, then we get a new sequence {c₀, c₁, c₂, c₃, c₄, c₅, ...}. c_n represents the number of ways for dice "a" and "b" to have a sum of n.

We can prove that this is the case. If we take any term c_n, it can be represented by the following sum:

c_n = a_n*b₀ + a_n-1*b₁ + ... + a₁*b_n-1 + a₀*b_n

If we recall the definition of a_j and b_k, the proof becomes obvious. The first term "a_n*b₀" represents the number of ways to roll n on dice "a" and 0 on dice "b". The next term represents the number of ways to roll n-1 on dice "a" and 1 on dice "b". And so on.

So let's try it with normal six-sided dice!

We can easily get the generating function D for a normal six-sided dice, and the generating function D*D for two normal dice.

Sequence for normal dice: {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, ...}
Let D = generating function for normal dice
D = x + x² + x³ + x⁴ + x⁵ + x⁶
D = x * (1 + x) * (1 + x² + x⁴)
D = x * (1 + x) * (1 + x + x²) * (1 - x + x²)
D*D = x² * (1 + x)² * (1 + x + x²)² * (1 - x + x²)²

Now what we want are two new six-sided dice with generating functions A and B such that A*B = D*D. So what we have to do is split D*D into two groups of factors, one for A and one for B. Each group must have the factor x, because that ensures that each side has a nonzero number of pips. Each group must also have (1 + x) * (1 + x + x²), to ensure that they have exactly six sides. However, we can split the factor (1 - x + x²)² in any way we want.

A = x * (1 + x) * (1 + x + x²) * (1 - x + x²)²
B = x * (1 + x) * (1 + x + x²)
A = x + x³ + x⁴ + x⁵ + x⁶ + x⁸
B = x + 2x² + 2x³ + x⁴

These correspond to dice with sides {1, 3, 4, 5, 6, 8} and {1, 2, 2, 3, 3, 4}. There's your solution, right there.

Well, that was quite a mathematical adventure! I've been having fun factoring other kinds of dice as well.