IBM Research | Ponder This | January 2001 solutions
Skip to main content

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):
    B = Y, A < X
    B = Y, X < A
    Y = A = *
    A = X, B < Y
    A = X, Y < B
    X = B
    Four pivots (6 cases):
    A < X < B < Y
    XY is a proper subset of AB
    X > B (no intersection)
    AB is a proper subset of XY
    X < A < Y < 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)

              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:

                  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:
            S. R. Schwer, Dependances temporelles: les mots pour le dire. Journees Intelligence Artificielle, 1998.
            S. R. Schwer, Enumerating and generating Allen's algebra, in preparation

            Dr. Jack Kennedy points out that the sequence is "A" number 055203 and can be referenced from

            Answer to Bonus Question:
            Call a "well-formed instance" one in which each interval has nonzero length, and "ill-formed instance" where at least one interval has zero length (endpoints equal). We set up a correspondence between well-formed instances with n intervals and k+1 distinct points, and ill-formed instances with n intervals and k distinct points. Given a well-formed instance (n,k+1), the rightmost point is the right endpoint of one or more intervals. Move each of those right endpoints to coincide with their corresponding left endpoint. This gives an ill-formed instance (n,k). The reverse mapping is clear: in an ill-formed instance, take each interval of zero length, and move all those right endpoints to a new rightmost point.
            The well-formed instance (A) ---(B) --- (A) --- (C) --- (BC) corresponds to the ill-formed instance (A)---(BB)---(A)---(CC).
            This establishes the fact that there are exactly as many ill-formed instances as well-formed instances, so that by allowing both kinds, we exactly double the number of allowable instances.

            If you have any problems you think we might enjoy, please send them in. All replies should be sent to: