Counting interval orders (Q1098864)

In interval order is a set with an irreflexive binary relation \(\prec\) satisfying \(a\prec b\wedge c\prec d\Rightarrow a\prec d\vee c\prec b\). The authors treat the problem of computing the number f(t) of interval orders (up to isomorphism) of cardinality t and develop a polynomial time algorithm for the solution. Their algorithm is based on the formula \[ f(t)\quad =\sum^{t}_{s=1}\left( \begin{matrix} t-1\\ t-s\end{matrix} \right)\quad h(s) \] where h(s) is the number of interval orders of cardinality s without duplicated holdings. The authors have computed f(t) for \(t\leq 60\) on an 8088-based personal computer.