How many possibilities to get to N spaces away from starting point by rolling 6-faced dice?

After a lot of calculation I found a solution that it creates a Hexanacci series. Now let me explain Hexanacci series a little bit. In the Hexanacci series each element is the summation of previous 6 elements. So I achieved this in Objective-C by just using a for loop which can be easily convert to any language:

-(void)getPossibleWaysFor:(NSInteger)number
 {
  static unsigned long ways;

  unsigned long first = 0;
  unsigned long second = 0;
  unsigned long third = 0;
  unsigned long fourth = 0;
  unsigned long fifth = 0;
  unsigned long sixth = 1;

  for (int i = 0; i<= number; i++) {

    ways = first + second + third + fourth + fifth + sixth;

    if (i>0) {
        first = second;
        second = third;
        third = fourth;
        fourth = fifth;
        fifth = sixth;
        sixth = ways;
    }

    NSLog(@"%d : -> %ld",i,ways);
}
return ways;}

// Result:

[self getPossibleWaysFor:20];

0 : -> 1
1 : -> 1
2 : -> 2
3 : -> 4
4 : -> 8
5 : -> 16
6 : -> 32
7 : -> 63
8 : -> 125
9 : -> 248
10 : -> 492
11 : -> 976
12 : -> 1936
13 : -> 3840
14 : -> 7617
15 : -> 15109
16 : -> 29970
17 : -> 59448
18 : -> 117920
19 : -> 233904
20 : -> 463968

Sorry i'm not expert in python but Java can solve this, you can easily transform it to language you want :

First idea using recursion :

The idea is to create all possible combinaisons in a GameTree after calculate the sum requested and increment out counter.

public class GameTree {
public int value;
public GameTree[] childs;

public GameTree(int value) {
    this.value = value;
}

public GameTree(int value, GameTree[] childs) {
    this.value = value;
    this.childs = childs;
}

}

For Memory issue i'll ignore the subtree superior to our sum (Like Alpha–beta pruning algorithm)

    static void generateGameTreeRecursive(String path, GameTree node, int winnerScore, int currentScore) throws InterruptedException {

    // Build the path
    if(node.value != 0)// We exclude the root node
        path += " " + String.valueOf(node.value);

    if (winnerScore <= currentScore) {
        // lierate the current node (prevent for Java heap space error)
        node = null;
        // Add the winner route
        count++;
        // Finish for this node
        return;
    } else{
        // cerate the childs
        node.childs = new GameTree[6];
        for (int i = 0; i < 6; i++) {
            // Generate the possible values to the childs
            node.childs[i] = new GameTree(i+1);             
            // Recursion for each child
            generateGameTreeRecursive(path, node.childs[i], winnerScore, currentScore + i + 1);
        }
    }
}

Second idea using iteration :

This solution is more elegant just dont ask me how i found it :)

// Returns number of ways to reach score n
static int getCombinaison(int n)
{
    int[] table = new int[n+1];
    // table[i] will store count of solutions for

    // Base case (If given value is 0)
    table[0] = 1;

    // One by one consider given 3 moves and update the table[]
    // values after the index greater than or equal to the
    // value of the picked move
    for (int j=1; j<7; j++) {
        for (int i=j; i<=n; i++)
           table[i] += table[i-j];
    }

    return table[n];
}

Im not really good in python but I can help you using ruby ;)

def ways(n)
  return ways(n-1) + ways(n-2) + ways(n-3) + ways(n-4) + ways(n-5) + ways(n-6) if n >= 6
  return ways(4) + ways(3) + ways(2) + ways(1) + ways(0) if n == 5
  return ways(3) + ways(2) + ways(1) + ways(0) if n == 4
  return ways(2) + ways(1) + ways(0) if n == 3
  return ways(1) + ways(0) if n == 2
  return ways(0) if n == 1
  return 1 if n == 0
end