0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like the shrinking analogy, it is very clear. Thank you. I didn't expect the formula to be so simple. $\endgroup$ – Xochipilli Nov 1 '12 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.