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

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?

• This is equivalent to asking how many solutions there are to the equation $\sum_{i=1}^6 a_i i=N$ for $a_i \in \mathbb{N}_0$ (if we start at the zeroth square), if that somehow helps somebody solve this. – Bobson Dugnutt Aug 17 '16 at 14:30

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.

• Thanks NP-hard. Would you please let me know in detail of the formula you given. As I am not so good in math, I need to learn it. – Iqbal Aug 19 '16 at 3:48
• @Iqbal Enumerate all possible ways to reach the $i$-th position. There are six possibilities for the last but one position, namely, the $(i-6)$-th, the $(i-5)$-th, the $(i-4)$-th, the $(i-3)$-th, the $(i-2)$-th and the $(i-1)$-th positions. Therefore, $f(i)$ equals to "# of ways to reach the $i$-th position whose last but one position is $(i-6)$" plus "# of ways to reach the $i$-th position whose last but one position is $(i-5)$" plus $\cdots$ plus "# of ways to reach the $i$-th position whose last but one position is $(i-1)$". That is, $f(i) = f(i-6) + f(i-5) + \cdots + f(i-1)$. – PSPACEhard Aug 19 '16 at 4:33
• NP-hard, I am sorry for taking a while to respond to your answer to my question here, but it's a good answer now that I have looked at it. Why did you delete it? – 6005 Aug 19 '16 at 18:27
• @Yikai I understand from the formula you have ways to reach 100 = reach 99 + reach 98 + ... reach 94 but what about the extra case in which after reaching say 95 I still have 5 more places to go so the combination of that would be still 16 more ways to reach 100, am I missing something? likewise after reaching 99 I still have to reach 100 by rolling the dice one more time, so some value should get added to this sequence I suppose – Vihar Jun 20 '17 at 10:16
• @Vihar It is not the number of combinations here. Note that to reach position $4$ from position $0$, the sequence $1$, $2$, $1$ is different from the sequence $2$, $1$, $1$. – PSPACEhard Jun 21 '17 at 2:18

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

• This is the pentanacci sequence (OEIS A001591). – Parcly Taxel Aug 17 '16 at 15:10
• @Jorge, (C#) I got 0, 1, 2, 4, 8, 16, 32, 64, 127, 252, 500 ... why ? – Hassan Tareq Jun 11 '17 at 6:17
• I know this is a bit old, but can you explain the  F[i]+=F[i-j]; part a bit? I fail to comprehend the logic behind this line. – Tasos Anesiadis Jun 24 '18 at 13:48
• sure, since we have the formula $F[i] = F[i-1] + .... + F[i-6]$ and all of the values of $F[i]$ are initialized as $0$ all we have to do is add $F[i-1]... F[i-6]$ to the initial value. – Jorge Fernández Hidalgo Jun 24 '18 at 14:04
• Seems f(0) should also be 1, not 0. – Eric Wang Oct 10 '18 at 20:34

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.