Given a set of $n$ integers and a starting point, one has to collect all $n$ numbers moving at most a distance 1 from any number previous picked.
For example if $n=5$ one solution would be: $\{3,2,1,4,5\}$. Another would be $\{3,2,4,1,5\}$ or $\{2,3,4,5,1\}$. How many solutions are there?
Here are my initial thoughts:
If we start 1, there is only 1 possible solution. If we start at 2, we can either go back to 1 or move to 3. Once at 3 we can go back to one or move to 4 and so on. This would give $n-1$ solutions.
Starting at 3 is where it gets slightly more complex. If we move back to 2 we then get the $n-1$ solutions we had minus the solutions $\{2,1,3...\},\{2,3,1...\}$. This means that the 2 branch starting from 3 has n-3 solutions.
If we move instead to 4 after 3, we can then go either to 2, which this time would give us $n-4$ solutions, or move to 5. We can follow this recursion on but I am finding the maths too fiddly and can't quite get a solid grasp on the pattern.
Any other ways would be appreciated, I have a feeling there could be a graph theory approach but that has not borne fruit for me.
Start at position $m$ in a row of $n$ numbers.
You have $m-1$ moves to the left and $n-m$ moves to the right.
How many ways can you arrange them?
Sum over $m$ from $1$ to $n$