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

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

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

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?

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$.