Old Problem With Generating Functions – Mattia Giuri's bizarre blog

A similar problem to this one is the one that initiated me to the art of using the generating functions, I’ll tell you a version which has less calculations to make.

If you roll a complete set of DnD dice, in how many ways can you obtain 13 as sum of their results?

Just for you to know, a complete set of DnD dice is made up of 6 components: 4-faced die, 6-faced die, 8-faced die, 10-faced die, 12-faced die, 20-faced die. Each of them has, on its faces, all the numbers in a range that goes from 1 to the number of its faces.

Now, let’s write its generating function. Keep in mind we have to find its 13th degree coefficient.

Each die can be written as:

$x+x^2+...+x^n = \frac{x-x^{n+1}}{1-x}$

where n is the number of its faces.

If we multiply all the polynomials we get a roll of all the 6 dice:

$\frac{1}{(1-x)^6}(x-x^5)(x-x^7)(x-x^9)(x-x^{11})(x-x^{13})(x-x^{21})$

It may seem a difficult polynomial division to perform, but there’s actually a trick which simplifies calculations. By a very straightforward use of derivatives, one notices this series expansion

$\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} {{n+k-1} \choose {k-1}}x^n$

That’s how we’ll write $\frac{1}{(1-x)^6}$ , but now we have to expand the rest of the polynomial (actually we can try to only find the terms of degree less than or equal to 13 but I’ll show the complete one).

$x^{66} - x^{62} - x^{60} - x^{58} + 2 x^{52} + 2 x^{50} + x^{48} - x^{46} - x^{44} - x^{42} - x^{40} + x^{38} + x^{34} - x^{32} - x^{30} - x^{28} - x^{26} + x^{24} + 2 x^{22} + 2 x^{20} - x^{14} - x^{12} - x^{10} + x^6$

This must be multiplied by the series expansion we previously discussed.

Now, to reach 13, we need to consider to consider the terms of degree 6, 10 and 12 of the expanded polynomial and, hence, the terms of degree 7, 3 and 1 of the series expansion.

The result is:

${12 \choose 5} - {8 \choose 5} - {6 \choose 5} = 730$

This is a very nice trick to employ in your combinatorics problems.