# Counting the number of ways three dice can sum to $n$

I want to count in how many ways three dice can sum to a given number without brute forcing it. In fact, I would like to do it using generating functions and without having to expand out the product.
To do this, I have thought of making a differential equation out of $y=(x+x^2+x^3+x^4+x^5+x^6)^3$ and then solving the equation through the use of power series, or getting the $n$th taylor coefficient from the equation.
What I attempted was: $$y=(x+x^2+x^3+x^4+x^5+x^6)^3$$ $$y'=3y^{2/3}(1+2x+3x^2+4x^3+5x^4+6x^5)$$ Then, by setting $x=0$ we see $y(0)=0$ and $y'(0)=0$, which is what I want, however, when trying to obtain $y''(0)$ by differentiating both sides, I get division by $0$ on the RHS.
Am I making a mistake in the set up or is calculating the expression through the use of a differenrial equation impossible?

• I don't understand your question. Let $f(x)=g(x)^3$, where $g(x)=x+x^2+\cdots+x^6$. Then $f''(x)=6g(x)g'(x)^2+3g(x)^2g''(x)$. Evaluate at $x=0$ to get $f''(0)=0$. – Matthew Conroy Nov 4 '16 at 22:06
• I am trying to get to the coefficients faster by using a power series method on the differential equation instead of just extracting the coefficients through derivatives. – Guacho Perez Nov 4 '16 at 22:25
• Have you tried your method with two dice? – Matthew Conroy Nov 4 '16 at 23:25
• You get $f'(x)=3g(x)^2g'(x)$. Multiply with $g(x)$ to obtain $g(x)f'(x)=3f(x)g'(x)$ which is now linear in the coefficients of $f$. – LutzL Nov 5 '16 at 0:28

Here is an alternate approach. We could at first transform $y(x)$ so that an expansion after that becomes less cumbersome. Maybe this variant is also useful for your needs.

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We also use Iverson brackets \begin{align*} [[P(x)]]=\begin{cases} 1&\qquad P(x) \ \text{ true}\\ 0&\qquad P(x) \ \text{ false} \end{cases} \end{align*} This way we can treat multiple cases in one expression.

We obtain \begin{align*} [x^n]y(x)&=[x^n](x+x^2+x^3+x^4+x^5+x^6)^3\\ &=[x^n]x^3(1+x+x^2+x^3+x^4+x^5)^3\\ &=[x^{n-3}][[n\geq 3]]\left(\frac{1-x^6}{1-x}\right)^3\tag{1}\\ &=[x^{n-3}][[n\geq 3]](1-3x^6+3x^{12}-x^{18})\sum_{j=0}^\infty\binom{-3}{j}(-x)^j\tag{2}\\ &=\left([x^{n-3}][[n\geq 3]]-3[x^{n-9}][[n\geq 9]]\right.\\ &\qquad\quad\left.+3[x^{n-15}][[n\geq 15]-[x^{n-21}][[n\geq 21]\right) \sum_{j=0}^\infty\binom{j+2}{2}x^j\tag{3}\\ &=\binom{n-1}{2}[[n\geq 3]]-3\binom{n-7}{2}[[n\geq 9]]\\ &\qquad\quad+3\binom{n-13}{2}[[n\geq 15]]-\binom{n-19}{2}[[n\geq 21]]\tag{4} \end{align*}

Comment:

• In (1) we apply the coefficient of rule \begin{align*} [x^p]x^qA(x)=[x^{p-q}]A(x) \end{align*} and we use the formula for the finite geometric series. Since there is no contribution to the coefficient of $x^n$ if $n<3$ we respect this by using $[[n\geq 3]]$.

• In (2) we expand the binomial and we also expand $\frac{1}{(1-x)^3}$ using the binomial series expansion.

• In (3) we use the linearity of the coefficient of operator and we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (4) we select the coefficient of $x^{n-k}, k\in\{3,9,15,21\}$.

Note: The usage of the Iverson brackets covers the general case. If we need to calculate a specific case only, the calculation becomes even more straight forward.

Example: $[x^{10}]y(x)$

We obtain \begin{align*} [x^{10}]y(x)&=[x^{10}](x+x^2+x^3+x^4+x^5+x^6)^3\\ &=[x^7]\left(\frac{1-x^6}{1-x}\right)^3\\\ &=[x^7](1-3x^6)\sum_{j=0}^\infty\binom{-3}{j}(-x)^j\\ &=\left([x^7]-3[x]\right)\sum_{j=0}^\infty\binom{j+2}{2}x^j\\ &=\binom{9}{2}-3\binom{3}{2}\\ &=27 \end{align*}

• In $(3)$ why do we get the binomial between $(j+2,2)$ and not $(j+2,j)$? – Guacho Perez Nov 5 '16 at 16:55
• @GuachoPerez: Recall the symmetry $\binom{n}{k}=\binom{n}{n-k}$. See the extended comment (3). Regards, – Markus Scheuer Nov 5 '16 at 16:59
• Very neat solution, I like the use of the coefficient of operator. – Guacho Perez Nov 5 '16 at 17:02
• @GuachoPerez: Great! Good to see the answer is useful! :-) – Markus Scheuer Nov 5 '16 at 17:04
• @GuachoPerez: You might want to see this MSE answer for a somewhat more challenging usage of the coefficient of operator. – Markus Scheuer Nov 5 '16 at 17:10