IBM Ponder This #033 · 2001 年 1 月

Raul Saavedra 提出了这个时间关系计数问题。给定 N 个有标号、长度非零的区间，忽略具体端点距离，只区分端点的先后和重合关系，它们在一条直线上共有多少种排列方式？

例如，两个区间 AB 与 XY 满足 A < B、X < Y，共有以下 13 种关系：

...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)

A 部分：给出计算总数 F(N) 的方法，其中 F(1)=1、F(2)=13。

B 部分：计算 N=3,4,…,10 时的 F(N)。

附加问题：Lyle Ramshaw 指出，如果允许区间长度为零，即左右端点重合，关系总数恰好翻倍。例如 N=2 时从 13 种变成 26 种。给出一个简单的组合解释。

解答

认真尝试后再打开

待补充。