the sample space of one toss of three dice is:
$\Omega = \left \{ (1,1,1), …, (6,6,6) \right \}$
so there are $6^3 = 216$ possible outcomes.
What is the probability to obtain an outcome where the sum of its three components is equal to 11?
I've considered the possible value can assume dice without a particular position and then I have considered the permutations to include every position:
$(6,4,1), 3! = 6 \\ (6,3,2), 3! = 6 \\ (5,5,1), \frac{3!}{2!} = 3 \\ (5,4,2), 3! = 6 \\ (5,3,3), \frac{3!}{2!} = 3 \\ (4,4,3), \frac{3!}{2!} = 3$
so I've summed up obtaining $27$ and the probability would be $\frac{27}{216}$
Now, consider if I have to do this same passages for sums from 3 to 18, it is very exhausting.
So, my question is: Is there any "faster" way to do that?
Best Answer
The generating function approach is to ask for the coefficients of $x^{n}$ in the expansion of:
$$(x+x^2+x^3+x^4+x^5+x^6)^{3}=x^3\left(\frac{1-x^6}{1-x}\right)^3$$
Now, $$\frac{1}{(1-x)^3}=\sum_{k=0}^{\infty}\binom{k+2}{2}x^k$$
And $$(1-x^6)^3=1-3x^6+3x^{12}-x^{18}$$
So the product of these and $x^3$ has, for the coefficient $x^n$:
$$\binom{n-1}{2}-3\binom{n-7}{2}+3\binom{n-13}{2}-\binom{n-19}{2}$$
Trick is to treat $\binom{j}{2}=0$ when $j<2.$
So, for example, when $n=11$, you get $\binom{10}{2}-3\binom{4}{2}=45-18=27$.
This also gives you a hint of the value when dealing with $k$ dice. Then:
$$c_n = \sum_{i=0}^{k}(-1)^i\binom{k}{i}\binom{n-(1+6i)}{k-1}$$
If you don't like generating functions, this can be proven via inclusion-exclusion.
There's another approach that is a little faster for computing all values.
If $(1+x+x^2+\cdots+x^5)^3=a_0+a_1x+\cdots+a_nx^n+\cdots$ then you get that:
$$(a_0+a_1x+\cdots+a_nx^n+\cdots)(1-3x+3x^2-x^3)=(1-x^6)^3=1-3x^6+3x^{12}-x^{18}$$
What this means is that (setting $a_n=0$ when $n<0$: $$a_{n}-3a_{n-1}+3a_{n-2}-a_{n-3}=\begin{cases} 1&n=0\\ -3&n=6\\ 3&n=12\\ -1&n=18\\ 0&\text{otherwise} \end{cases}$$
or:
$$a_{n}=3\left(a_{n-1}-a_{n-2}\right)+a_{n-3}+\begin{cases} (-1)^k\binom{3}{k}&n=6k\\ 0&\text{otherwise} \end{cases}$$
Then the final coefficient of $x^n$, after we multiply by $x^3$ again, is $a_{n-3}$.
So you get:
$$\begin{align}a_0&=0+(-1)^{0}\binom{3}{0}=1\\ a_1&=3\left( a_0-a_{-1}\right)=3\\ a_2&=3\left( a_1 - a_0\right)=6\\ a_3&=3\left(a_2 - a_1\right)+a_0=10\\ a_4&=3\left(a_3-a_2\right)+a_1=15\\ a_5&=3\left(a_4-a_3\right)+a_2=21\\ a_6&=3\left(a_5-a_4\right)+a_3+(-1)^{1}\binom{3}{1}=25\\ &\cdots \end{align}$$
There's a special trick that can be applied here: $a_{n}=3a_{n-1}-3a_{n-2}+a_{n-3}$ is known to be a quadratic polynomial in $n$. So, when $n$ is not a multiple of $6$, you get that:
$$a_{n-2}-a_{n-3},a_{n-1}-a_{n-2},a_{n}-a_{n-1}$$ must be an arithmetic progression for any $n$ not a multiple of $6$.
So we have that $a_5-a_4 = 6, a_6-a_5=4$ and thus $a_7-a_6=2$, or $a_7=a_6+2=27.$ $a_8=27+0=27, a_9=27-2=25,a_{10}=25-4=21,a_{11}=21-6=15,a_{12}=15-8+(-1)^2\binom{3}{2}=10$.