Kind of basic combinatorical problems and (exponential) generating functions

Question

I have a pretty straightforward combinatorical problem which is an exercise to one paper about generating functions.

1. How many ways are there to get a sum of 14 when 4 distinguishable dice are rolled?

So, one die has numbers 1..6 and as dice are distinguishable then we should use exponential generating functions (we count sequences of rolled dice), because $3,4,3,4$ differs from $3,3,4,4$. So, we end up with answer $$[\frac{x^{14}}{14!}](x+\frac{x^2}{2}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!})^4$$ How can we nicely calculate the coefficient of $\frac{x^{14}}{14!}$? I don't want to do this brutally, because next task is

2 Find generating function for the number of ways a sum of n can occur when rolling a die an infinite (or at least n) number of times.

I'd appreciate some help on such problems and how to "wrap" such limited exponential series.

Answer 1

As ShreevatsaR pointed out it's sufficient to consider ordinary generating functions, since they already take into account that $3,4,3,4$ and $3,3,4,4$ are different. The first is coded as the coefficient of $x^3x^4x^3x^4$, while the second as the coefficient of $x^3x^3x^4x^4$ when considering the ogf $(x^1+\cdots+x^6)^4$.

Therefore we get for the first part

\begin{align*} [x^{14}]&(x^1+\cdots+x^6)^4\\ &=[x^{14}]x^4(1+\cdots+x^5)^4\\ &=[x^{10}](1+\cdots+x^5)^4\\ &=[x^{10}]\left(\frac{1-x^6}{1-x}\right)^4\\ &=[x^{10}](1-4x^6+6x^{12}-4x^{18}+x^{24})\sum_{k\geq0}\binom{-4}{k}(-x)^k\\ &=([x^{10}]-4[x^{4}])\sum_{k\geq0}\binom{k+3}{k}x^k\\ &=\binom{13}{10}-4\binom{7}{4}\\ &=146 \end{align*}

For the second part we observe that each roll contributes at least $1$ to the value $n$. We can therefore restrict ourselves to the bracketed formulation: A die will be rolled at least $n$ number of times since all further rolls will not contribute to $n$.

An ordinary generating function in this case is

$$x^n\left(\frac{1-x^6}{1-x}\right)^n$$

Added 2014-04-19: Supplement - Using exponential generating functions instead.

This is admittedly a rather simple minded attempt to answer the question of Chris from the comment below: What do we count, if we would have used exponential generating functions here? Please feel free, to provide better examples with four dice, if you like.

If we use exponential instead of ordinary generating functions, we could imagine that we also have the pips of the faces of the dies distinguishable. Let's assume we have four magic dice $(M_1,M_2,M_3,M_4)$ (M for magic) and we are asking what's the contribution of a roll $(3,4,3,4) \rightarrow 14$ with respect to

$$\left[\frac{x^{14}}{14!}\right](x+\frac{x^2}{2}+\cdots+\frac{x^6}{6!})^4$$

The contribution is the multinomial coefficient

$$\left[\frac{x^{14}}{14!}\right]\frac{x^3}{3!}\frac{x^4}{4!}\frac{x^3}{3!}\frac{x^4}{4!}=\binom{14}{3,4,3,4}=\frac{14!}{3!^{2}4!^{2}}=4204200$$

and the explanation: In this case (namely roll with $14$ pips) the magic dice can choose for the resulting pips from $14$ different colors. $M_1$ chooses $3$ colors, $M_2$ chooses $4$ from the remaining $11$ colors, $M_3$ takes $3$ from the remaining $7$ and the rest of $4$ colors is used by $M_4$. So, we have

$$\binom{14}{3}\binom{11}{4}\binom{7}{3}\binom{4}{4} = \binom{14}{3,4,3,4}$$

different possibilities to see the magic dice colorized with $14$ different colors.

Answer 2

You can do it quite easily with Python:

    from sympy.abc import x
    from sympy import expand
    from math import factorial
    d1 = expand((1+x+x**2/2+x**3/factorial(3)+x**4/factorial(4)+x**5/factorial(5)+x**6/factorial(6))**4).as_coefficients_dict()
    print d1[x**14]

It returns:

169/64800