How to calculate number of different combinations along a line?

Question

If I have a straight line consisting of n points, and I have to get from the first to the last point, using any combination of "hops" along points, how do I calculate how many possible combinations there are?

Example: a line with points A, B, C. I can either go from A -> C, or A -> B -> C. That's two possible combinations.

Can the hops be of any length? And do they all have to be "forward"? — JimmyK4542, Jun 28 '14 at 01:57
Yes, to both. As long as it takes you from start to finish, forward only. — Henri, Jun 28 '14 at 02:33

score 1 · Answer 1 · answered Jun 28 '14 at 01:59

1

Assuming the hops can be of arbitrary length and each hop must go forward:

Pick any subset of the $n-2$ points in the middle. Then hop from the first point to each of the points in that subset in order, and then to the last point. Each subset of the $n-2$ points in the middle yields a unique combination of hops, so we have $2^{n-2}$ combinations of hops.

answered Jun 28 '14 at 01:59

JimmyK4542

54,331

Thank you! Is there a name or terminology for this kind of combination-finding? I need to write it in a computer scripting language, to list all possible combinations of hops from start to finish. – Henri Jun 28 '14 at 02:32
You are looking for compositions. (The parameter is different by $1$.) – André Nicolas Jun 28 '14 at 03:10

How to calculate number of different combinations along a line?

1 Answers1