IBM Ponder This #033 · January 2001

This month's puzzle comes from Raul Saavedra.

Imagine you have N events of non-zero duration, in how many different ways could those events overlap in time? (This combinatorial problem shows up within the context of temporal reasoning).

Let’s formulate the problem more precisely. Imagine you have two non-null segments, AB and XY (A < B and X < Y always). If you wanted to put them on a line, you could arrange those 2 segments in exactly 13 different ways:

Graphical representation Constraints

...A-----B.....X-----Y... X > B (no intersection)
......A-----*-----Y...... X = B
......A---X---B---Y...... A < X < B < Y
......*-----B-----Y...... A = X, B < Y
......*-----Y-----B...... A = X, Y < B
......A---X---Y---B...... XY is a proper subset of AB
......*-----------*...... A=X, B=Y (AB=XY)
......X---A---B---Y...... AB is a proper subset of XY
......A-----X-----*...... B = Y, A < X
......X-----A-----*...... B = Y, X < A
......X---A---Y---B...... X < A < Y < B
......X-----*-----B...... Y = A = *
...X-----Y.....A-----B... Y < A (no intersection)

Part A) Derive a method for computing the function F(N) which given the number of segments N returns the total number of ways in which those N segments can be arranged on a line: F(1) = 1 F(2) = 13 : F(N) = ???

Part B) Find F(N) for N=3,4,… up to 10.

Bonus question: Lyle Ramshaw remarks that, if we allow zero-length intervals (left endpoint = right endpoint), the number of allowable configurations becomes exactly twice as large. (For n=2 there would be 26 possibilities instead of 13.) Can you find a simple combinatorial explanation for that?

Solution

Best opened after a real attempt

To be added.