This is similar to flight of staircase problem, but can't be solved with Fibonacci sequence. Therefore I am trying to a derive the formula.
Problem:
Grasshopper begins his journey from cell 0 and can jump a distance of 1 to J cells. Jumping is possible only on an integer number of cells and only forward. Count the number of ways that a grasshopper can get on the cell F(finish).
Example:
J (jump) = 2
F (finish) = 3
Result = 3 (0->1->2->3, 0->1->3, 0->2->3)
I've calculated sequences for J = 4 & and J = 5 like this:
sum of elements in (sequence from 0 to J) + (sequence from J to F).
But it feels clumsy. Moreover I don't understand the complete logic behind this, this was just a brute-force solution.
Although I've noticed that:
sequence from 0 to J is a sequence of power of 2 (from 0 to N)
sequence from J to F is a Fibonacci-like sequence F(n) = F(n-1) + F(n-2) ... + F(n-n) - ???
J = 4, F = 1, Res = 1,
J = 4, F = 2, Res = 2
J = 4, F = 3, Res = 4
J = 4, F = 4, Res = 8
J = 4, F = 5, Res = 16
J = 4, F = 6, Res = 31
J = 4, F = 7, Res = 61
J = 4, F = 8, Res = 120
J = 5, F = 1, Res = 1
J = 5, F = 2, Res = 2
J = 5, F = 3, Res = 4
J = 5, F = 4, Res = 8
J = 5, F = 5, Res = 15
J = 5, F = 6, Res = 29
J = 5, F = 7, Res = 56
J = 5, F = 8, Res = 108
Please help to derive a formula. I know that this is a combinatoric problem. Also feel free to point out where I can read about most common combinatoric problems with explanation of how to approach them.
Solution
UPD: scratch all that. The problem is simple as is a solution. Basically it goes like: in how many ways you can combine numbers of {1...Jump} to get a [Finish]. This is a composition:
A composition of an integer n is a way of writing n as the sum of a sequence of (strictly) positive integers.
And the answer can be calculated as Fibonacci numbers of higher order. For example if Jump is 4 it's Tetranacci, 7 - Heptanacci and so on. You only need to get the n-th number of the sequence.