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

Question

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?

Answer 1

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.