I am studying now the concept of generating function, and I have a solved question in my book which I don't understand, completely. There it is:

What is the number of options to roll 10 different dice, so the sum
of the results will be 25?

Now for the solution:

f(x) = (x+x^2+x^3+x^4+x^5+x^6)^10

I believe this is because we have 6 options in each dice, and 10 different dice.


Here the professor took out the Common factor x^10 (I think by taking out x^6 and some more)

=x^10(1-x^6)^10 * (1+x+x^2....)^10

The "...." sign is a sign for an infinite arithmetic progression or until x^5? I don't know.

Now we have to find the "base" of x^25, which is the basic of a generatic function or so I believe. Now he makes so permutations here:

C(10+15-1,15) - 10*C(10+9-1,9) + C(10,2)*C(10+3-1,3) =
=1,307,504 - 486,200+720 = 822,040

I believe it has to be related to this concept, that the book shows for Derivative. For example, f'(x)=n/(1-x)^(n+1); f''(x)=n(n+1)/(1-x)^n+2 Now he shows for the k-th Derivative that: 1/k! * f'(x) in the k-th time, if we set x=0:

n(n+1)....(n+k-1) / k! = C(n+k-1,k)

I am sorry for the long, not so understandable question, but It's really hard for me to understand his methods.

Thank you!


Since you have 10 dice, and each die can be any integer from 1 to 6, your generating function is

$f(x)=(x+x^2+x^3+x^4+x^5+x^6)^{10}=(x(1+x+x^2+x^3+x^4+x^5))^{10}=x^{10}(1+x+x^2+x^3+x^4+x^5)^{10}$ $=\displaystyle x^{10}\big(\frac{1-x^6}{1-x}\big)^{10}=x^{10}(1-x^6)^{10}(1-x)^{-10}.$

Now we have to find the coefficient of $x^{25}$, and we can use the Binomial Formula in the second factor and the formula $(1-x)^{-n}=\sum_{k=0}^{\infty}\binom{n-1+k}{k}x^k$ in the third factor.

This gives $f(x)=x^{10}(1-10x^6+45x^{12}+\cdots)\big(\sum_{k=0}^{\infty}\binom{9+k}{k}x^k\big)$, so the coefficient of $x^{25}$ will be the coefficient of $x^{15}$ in $(1-10x^6+45x^{12}+\cdots)\big(\sum_{k=0}^{\infty}\binom{9+k}{k}x^k\big)$, which is

$\;\;\binom{24}{15}-10\binom{18}{9}+45\binom{12}{3}=831, 204.$


Between your third gray and fourth gray, you should recognize that $1+x+x^2+x^3+x^4+x^5=\frac{1-x^6}{1-x}$, so you have $f(x)=x^{10}\left(\frac{1-x^6}{1-x}\right)^{10}$. Then $\frac 1{1-x}=1+x+x^2+x^3 \dots$ where the dots go on forever, getting you to the fourth gray. I can't help beyond there.


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.