Ponder This

January 2001

<<December January February>>

We know that two segments can be arranged in 13 different ways. Let’s group those 13 cases conveniently.

First let’s call “pivots” the different vertices we get once the segments are placed on the line. The 13 cases can then be grouped into 3 different groups depending on the number of such pivots:


Two pivots (1 case):

......*-----------*......		A=X, B=Y (AB=XY)
Three pivots (6 cases):
......A-----X-----*......		B = Y, A < X
......X-----A-----*......		B = Y, X < A
......X-----*-----B......		Y = A = *
......*-----B-----Y......		A = X, B < Y
......*-----Y-----B......		A = X, Y < B
......A-----*-----Y......		X = B
Four pivots (6 cases):
......A---X---B---Y......		A < X < B < Y
......A---X---Y---B......		XY is a proper subset of AB
...A-----B.....X-----Y...		X > B (no intersection)
......X---A---B---Y......		AB is a proper subset of XY
......X---A---Y---B......		X < A < Y < B
...X-----Y.....A-----B...		Y < A (no intersection)



Notice that there cannot be more than 2N pivots. Also, since the segments have length greater than zero, then for N>0 we must always have at least 2 pivots.

We can then calculate the total number of combinations for N segments as the sum of the possible cases for 2, 3, 4 … up to 2N pivots.

F(N) = � _{p=2,...,2N} W (N, p)


W(N,p) will be the number of ways to arrange N segments having exactly p pivots.

Let’s define W(N,p) case by case:

First let’s discard the invalid cases:

If (p < 2) or (p > 2N) then W (N, p) = 0

There is only one way to arrange N segments having at the end exactly two pivots: all segments being equal. Therefore, for all N>0:

W(N, 2) = 1

The cases that are hard to count are those when p>2 and p<=2N

W(N, p) = ? where 2 < p <= 2N

Now, if we have N segments and p pivots, we could have only reached that configuration after having added one segment to a set of N-1 segments, and either:
a) There were already p pivots and we did not add any new one when adding this new segment, or
b) There were p-1 pivots and we added exactly one new pivot when adding this new segment, or
c) There were p-2 pivots and we added two new pivots when adding this new segment.

Those are the only possible ways to come up with a configuration with N segments and p pivots. So we can define the function W(N,p) recursively as follows:

W(N,p) = W(N-1, p) * NoMorePivots(p) +
W(N-1,p-1) * OneMorePivotAddedTo(p-1) +
W(N-1,p-2) * TwoMorePivotsAddedTo(p-2)

Now let’s analyze those functions on the right:

NoMorePivots(p) is the number of ways we can add a segment to a configuration that already has p pivots so that we end up still having p pivots. Notice that it doesn’t matter how many segments there are conforming those original p pivots. We just care about the number of ways in which we can add a new segment to that bunch with p pivots without creating any new pivot. To do this the segment has to be added so that both of its vertices overlap previous pivots. How many ways are there to do this?

Let’s say our new segment is AB, and the P pivots go from V1 to Vp. We can add the new segment the way we want by setting A to V1 and B to any V2, V3…or Vp (this yields p-1 cases), or A to V2 and B to V3, V4…Vp (p-2 cases) and so forth till the case in which A is set to Vp-1 and B to Vp. The total number of cases would then be:
NoMorePivots(p) = � _{i=1,...,p-1} (p-i) = (p - 1) * p / 2
OneMorePivotAddedTo(p) is the number of ways we can add a segment to a configuration that already has p pivots so that we end up having exactly p+1 pivots. We can do this if only one vertex of the new segment overlaps a previous pivot, and we make sure the other one does not overlap any pivot so that it becomes a new one. How many ways there are to do this?

CasesA: A overlaps, B doesn’t (so B becomes the new pivot).
A can be any pivot from V1 to Vp.
If A = Vi then B can be in any “space” j>=i, where space j is the interval (Vj ,Vj+1) if j<p, or the interval (Vj , ?) if j=p.
� _{i=1,...,p} (p-i+1) = p * (p + 1) / 2
CasesB: A doesn’t overlap (becomes the new pivot), B does overlap.
A can be set in any space i = 0 to p-1
In each of those cases B can be any pivot from Vi+1 to Vp.
� _{i=0,...,p-1} (p-i) = p * (p + 1) / 2
OneMorePivotAddedTo(p) = CasesA + CasesB = p * (p + 1)

TwoMorePivotsAddedTo(p) is the number of ways we can add a segment to a configuration that already has p pivots so that we end up having exactly p+2 pivots. We can do this if no vertex of the new segment overlaps any previous pivot so they both become new pivots. How many ways there are to do this?

A can be set at space i, where i can be 0, 1, 2… p.
In each case B can be at space i, i+1, … up to space p.
TwoMorePivotsAddedTo(p) = �_{i=0,...,p} (p – i + 1) = (p + 1) * (p + 2)/ 2

Now that we have those functions we can write the general recursive expression:

Part A:
F(N) = � _{p=0,...,2N} W (N, p)
Where:

W (N,p) = 0 if (p < 2) or (p > 2N);

1 if (p = 2);

(p-1)*p/2 *[W(N-1, p) + 2*W(N-1,p-1) +W(N-1,p-2)] if (2 < p <= 2N).


Part B: An output of a program calculating F(N) for N=0 to 10 is the following:


segments.java
By Raul Saavedra, Mar/11/2000

Cases for 0 segments=0
Cases for 1 segments=1
Cases for 2 segments=13
Cases for 3 segments=409
Cases for 4 segments=23917
Cases for 5 segments=2244361
Cases for 6 segments=308682013
Cases for 7 segments=58514835289
Cases for 8 segments=14623910308237
Cases for 9 segments=4659168491711401
Cases for 10 segments=1843200116875263613


Problem and solution provided by Raul Saavedra, March/11/2000
See also the references: