## 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}

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)

- (12) In the next step the path can only grow to edge 3
- (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)

- (1) If I picked edge 1 the path can only grow to 3
- (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)

- (2) In the next step the path can only grow to edge 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}

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?