# Kind of basic combinatorical problems and (exponential) generating functions

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.

• For your second question: There are precisely 0 ways, as each die will add at least 1 to the sum, hence the sum can never be finite. – Servaes Apr 18 '14 at 9:16
• Oh... I thought it's number of sequences $(a_1,a_2,a_3,\dots)$ such that $a_1+a_2+a_3+\dots = n$, so all the solutions, why i'm wrong? – Krzysztof Lewko Apr 18 '14 at 9:19
• For all $i\geq1$ you have $a_i\geq1$, so $a_1+\ldots+a_{n+1}\geq n+1$ and in particular $a_1+a_2+a_3+\ldots\neq n$. – Servaes Apr 18 '14 at 9:19
• Also, you need ordinary generating functions here, not exponential ones (at least, not in the way you wrote them). Although the dice are distinguishable, there is no ordering in the set of results. – ShreevatsaR Apr 18 '14 at 9:34
• Unless your dice have seven sides $0,1,2,3,4,5,6$, you shouldn't have the $1+$ in front of the $x+x^2/2+\cdots$. – Greg Martin Apr 18 '14 at 18:12

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$$

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.

• thank you! Im still wondering what would i count if i have used exponential generating functions here. Thanks in advance – Krzysztof Lewko Apr 19 '14 at 8:25
• I've added a note regarding your question in my answer. It's somewhat mystic, so, please don't take it too serious :-) Regards. – Markus Scheuer Apr 19 '14 at 16:26
• Thank you very much, i wish i could vote up your answer second time... – Krzysztof Lewko Apr 19 '14 at 18:39
• You're welcome! – Markus Scheuer Apr 19 '14 at 18:45
• @Antonin: On one hand powers greater $10$ do not contribute anything since we are looking for the coefficient of $x^{10}$. Therefore $[x^{10}](1-4x^6+6x^{12}-4x^{18}+x^{24})=[x^{10}](1-4x^6)=[x^{10}]-4[x^4]$. On the other hand we use the binomial identity: $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$. – Markus Scheuer Feb 25 '15 at 20:34

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

• Thanks for your answer, quite helpful. I have a problem with factorial. Maybe you know how to solve this: when I want to expand this expression, it works: d1 = expand(summation(x**(k-1)/(k-1)*(summation(x**(j-1)/(j-1),(j, 1, k))**2), (k, 0, 4))). If I add factorial (what I want to do), it does not anymore: d1 = expand(summation(x**(k-1)/factorial(k-1)*(summation(x**(j-1)/factorial(j-1),(j, 1, k))**2), (k, 0, 4))) gives the error: "File "sympy/core/expr.py", r = self.round(2) TypeError: <class 'sympy.core.add.Add'> is not a number" Any suggestion? – Antonin Feb 18 '15 at 12:01
• I found the answer here: stackoverflow.com/a/28583981/762435 – Antonin Feb 18 '15 at 14:11
• Yes, you can change the 3rd line from "from math import factorial" to "from sympy import factorial" and it should work and not bring up your error. – Stefan Gruenwald Feb 18 '15 at 20:57