Dice problem for the n space

Question

There is a 6-faced dice and every time you roll it, you move forward the same number of spaces that you rolled. If the finishing point is “n” spaces away from the starting point, how many possible ways are there to arrive exactly at the finishing point?

Answer 1

Your questions deals with the number of ["compositions"](https://en.wikipedia.org/wiki/Composition_(combinatorics) of an integer.

Although there is almost surely no closed form formula for it, here is a general technique for obtaining results for a given $n$ by using generating functions.

I will present it through an example: assume you want to reach position $n=12$ in $k=3$ steps, doing for example : $6+5+1$ or $5+6+1$ or $6+4+2$, etc. A hand examination show that there are 28 of them.

Let us now consider the following polynomial expansion:

$$p(x)^3 \ \ \ \ \ \ \text{with} \ \ \ \ \ p(x):=x+x^2+x^3+x^4+x^5+x^6$$

Using a Computer Algebra System like Mathematica, we obtain:

$$1 + 3\,x + 6\,x^2 + 10\,x^3 + 15\,x^4 + 21\,x^5 + 28\,x^6 + 33\,x^7 + 36\,x^8 + 37\,x^9 + 36\,x^{10} + 33\,x^{11} + 28\,x^{12} + 21\,x^{13} + 15\,x^{14} + 10\,x^{15} + 6\,x^{16} + 3\,x^{17} + x^{18}.$$

The number of compositions of $n=12$ into $k$ parts is found directly as the coefficient 28 of $x^{12}$.

Explanation: The general term in the development of

$$(x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6)$$

is $x^{i+j+k},$ obtained by taking a $x^i$, a $x^j$, a $x^k$ in each of the three parentheses ; among all these $x^{i+j+k}$, keeping only those whose exponent $i+j+k$ is exactly $12$ amounts to "sweep" all "compositions" of $n=12$ into $k=3$ parts:

$$x^{6+5+1}+x^{5+6+1}+x^{6+4+2}+...$$

Keeping $n=12$ fixed, you now do these operations for all possible $k$, i.e., for all $k=3,4,...12$ (if course $k=1$ and $k=2$ are impossible).

Thus the answer is: the coefficient of $x^{12}$ in:

$$q(x)=p(x)^3+p(x)^4+\cdots+p(x)^{12}$$

which can also be written:

$$p(x)^3(1+p(x)+p(x)^2+\cdots+p(x)^9)=p(x)^3\dfrac{1-p(x)^{10}}{1-p(x)}$$

What has worked for $n=12$ will work of course for any other $n$...