9
$\begingroup$

I know I can use generating functions. Each of the die has a generating function $x+x^2+x^3+x^4+x^5+x^6$, and so I need to find the coefficient of $x^9$ in the generating function of their sum, $(x+x^2+x^3+x^4+x^5+x^6)^3$. I am not sure how to do this, however, short of expanding it all out.

(I'm not just trying to get the answer but also the method behind it. Thanks a lot.)

$\endgroup$
3
  • $\begingroup$ The best way to do it in this case probably is to expand it all out. The advantage of generating functions in problems such as this is that you already know how to expand out a polynomial and you can use that to solve your counting problem, instead of having to derive a whole new recurrence for your counting problem. $\endgroup$
    – Michael Lugo
    Feb 8, 2017 at 19:19
  • $\begingroup$ This is called partitioning. You want to partition the number 9 into 3: en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$
    – it's a hire car baby
    Feb 8, 2017 at 19:28
  • $\begingroup$ In fact my apologies, since the dice are different colours the order matters so it's a composition: en.wikipedia.org/wiki/Composition_(combinatorics) $\endgroup$
    – it's a hire car baby
    Feb 8, 2017 at 19:31

3 Answers 3

Reset to default
10
$\begingroup$

The number of compositions of $n$ into exactly $k$ parts is $\binom{n-1}{k-1}=\binom{8}{2}=28$

Since a composition assumes each dice carries at least the number $1$ (no zeroes), this would permit a $7$ on any of the 3 dice. So we must exclude the three possibilities in which the red dice, the yellow dice or the black dice might have a 7 on (i.e. $\{7,1,1\},\{1,7,1\},\{1,1,7\}$).

$28-3=25$

$\endgroup$
5
$\begingroup$

Robert Frost's approach is probably the simplest, but here's a way to do it with generating functions.

We could just multiply it out. But we can save a bit of work by noticing that $(x + x^2 + x^3 + x^4 + x^5 + x^6)^3 = \left(\frac{x(1 - x^6)}{1 - x}\right)^3 = \frac{x^3 - 3x^9 + 3x^{15} - x^{21}}{(1 - x)^3}$.

We can drop the $x^{15}$ and $x^{21}$ terms because the powers are larger than 9, so we're left with finding the coefficient of $x^9$ in $(x^3 - 3x^9)(1-x)^{-3}$.

That's $\left[x^6\right](1 - x)^{-3} - 3 \left[x^0\right](1 - x)^{-3} = \left(\binom{3}{6}\right) - 3 \left(\binom{3}{0}\right) = 25$.

$\endgroup$
0
$\begingroup$

If you're doing this by hand, you can simplify things a bit by realizing that the coefficient of $x^9$ in $(x+x^2+x^3+x^4+x^5+x^6)^3$ is the sum of the coefficients of $x^3$ to $x^8,$ inclusive, in $(x+x^2+x^3+x^4+x^5+x^6)^2,$ and the coefficients of those terms are easily obtained by long multiplication of the polynomial by itself.

Or you can use more sophisticated methods of generating functions such as in Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin. The application to your problem is that each of your dice has to show at least the value $1$; identify each bin with a die, and then the number of balls in the bin represents the amount of "extra" value that shows on that die, so that $5$ balls represent rolling a $6.$ So you want to count the number of ways to put $6$ unlabeled balls (the "extra value" on all three dice, which have a minimum sum of $3$) in $3$ bins (one for each die) with a maximum of $5$ in each bin.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .