I'm writing a piece of software, however, my math skills are VERY rusty at the moment. The problem is as follows: There is a journey consisting of 256 steps The person, can either i) walk, or ii) hop The person can choose what to do at each step I want to compute a list of all possible journey I'm wondering if my attempt is futile.... As the search-space may be too huge if this problem is indeed exponential. My specific question is, how many ways are there through this journey? How many combinations of "walk" and "hop"? I'm hoping that I'm wrong and the answer is not 2^256 (or around that area...). Otherwise I will have to abandon my simplistic brute force algorithm :D Thank you!