1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Matthew Conroy Nov 4 '16 at 22:06
  • $\begingroup$ 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. $\endgroup$ – Guacho Perez Nov 4 '16 at 22:25
  • $\begingroup$ Have you tried your method with two dice? $\endgroup$ – Matthew Conroy Nov 4 '16 at 23:25
  • $\begingroup$ 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$. $\endgroup$ – LutzL Nov 5 '16 at 0:28
1
$\begingroup$

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*}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.