How many ways to reach $Nth$ number from starting point using any number steps between $1$ to $6$

Question

In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem is how many possible ways or combination of jump can be possible to reach start to end point of a board? For an example end point is 100:

1+2+6+...+1 = 100 -> 1 way
1+3+1+...+3 = 100 -> 2 ways
...
i+i+....+i  =  100 -> N ways

Is there any algorithm of recursion?

Answer 1

Suppose in the beginning, the pawn is at position $0$ and the end position is $N$. Let $f(i)$ denote the number of ways to reach position $i$. Then the following relationships hold. $$ f(i) = \begin{cases} f(i-1) + f(i-2) + f(i-3) + f(i-4) + f(i-5) + f(i-6)\ &\text{if }\ i \geq 6 \\ f(4) + f(3) + f(2) + f(1) + f(0) &\text{if }\ i = 5\\ f(3) + f(2) + f(1) + f(0) &\text{if }\ i = 4\\ f(2) + f(1) + f(0) &\text{if }\ i = 3\\ f(1) + f(0) &\text{if }\ i = 2\\ f(0) &\text{if }\ i = 1\\ 1 &\text{if }\ i = 0 \end{cases} $$ The rationale is as follows. Without loss of generality, suppose $i \geq 6$. To reach $i$-th position, you can

• first reach $(i-1)$-th position, and the result of dice roll is $1$;

• first reach $(i-2)$-th position, and the result of dice roll is $2$;

• $\cdots$

• first reach $(i-6)$-th position, and the result of dice roll is $6$.

---

Algorithm. Given the relationships, it is easy to compute $f(N)$. Starting with $i = 1$, you compute $f(i)$ in increasing order of $i$ using the formulas above.

Answer 2

If I understand correctly the problem, you want to know the number of paths $a_N$ getting from $0$ to $N$. This number verifies the recursion relation: $$a_N = \sum_{k=1}^6 a_{N-k}$$ provided we set $a_1=1$, $a_k=0$ for $k<0$. We simply partition paths according to the last dice result bringing them to $N$. You may get explicit formulae for this.

Answer 3

the recursion is as follows, let $F_N$ be the number of ways to get with $N$ rolls, then we have:

$F_0=1$ and $F_k=0$ for $k<0$.

For $k>0$ we have $F_k=F_{k-1}+F_{k-2}+F_{k-3}+F_{k-4}+F_{k-5}+F_{k-6}$

Some c++ code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=10010; //size of array
int F[MAX]; //stores results

int main(){
    F[0]=1;
    for(int i=1;i<MAX;i++){// we recursively fill the array
        for(int j=1; j<=6 && i-j>=0 ; j++){
            F[i]+=F[i-j];
        }
    }
    for(int i=0;i<10;i++) printf("%d\n",F[i]); // we print some values
}

The first ten values of $F_n$ starting with $F_0$:

0, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492