What are the number of possible ways to build up a certain path?
----------------------------------------------------------------


I was working on a graph problem and was trying to find out in how many possible ways can you build/grow a given path. With building/growing a given path I mean selecting a random edge of the path and adding connected edges to it until the full path is grown. I was trying to find a general formula but can't seem to find one.


### For example the path with edges = {1,2,3}


[Path with 3 edges](https://i.stack.imgur.com/5ajkY.png)


I can start growing it from a random edge, so I have 3 possibilities in the first step: edge 1, 2 or 3:


* (1) If I picked edge 1 the path can only grow to 2 in the next step
	+ (12) In the next step the path can only grow to edge 3
		- (123)
* (2) If I picked edge 2 the path can grow to edge 1 or 3 in the next step
	+ (1) If I picked edge 1 the path can only grow to 3
		- (3)
	+ (3) If I picked edge 2 the path can only grow to 1
		- (1)
* (3) If I picked edge 3 the path can only grow to 2 in the next step
	+ (2) In the next step the path can only grow to edge 1
		- (1)


So there are $3 \* (\frac{1}{3}\*2 + \frac{2}{3}\*1) = 4$ possible ways to grow this graph.


### For example the path with edges = {1,2,3,4}


[Path with 4 edges](https://i.stack.imgur.com/XmyIQ.png)


There are 8 different ways to grow this path, you can see it as a group of permutations or orderings with the restriction that for $\forall x, \exists y: index(y) < index(x) \wedge (x = y +1 \vee x = y -1)$ 


* 1234
* 2134
* 2314
* 2341
* 3214
* 3241
* 3421
* 4321


Does anyone know a general formula to calculate this for paths of any length?



What are the number of possible ways to build up a certain path?
If I understand it correctly, the answer is $2^{n-1}$. Instead of "growing" think
of "shrinking". There only 2 ways to shrink a path from length $n$ to a path
of length $n-1$. 


Another way to see it is this: 
To get it for length 5, take your 8 paths above and add a 5:
12345,
21345,
23145,
etc.


then, to get the other 8, add one to all the numbers, for example,
change 1234 to 2345 and then add a 1 at the end. So we get
23451,
32451,
34251,
etc.


