Python script for sequence A049463, Number of basic interval orders of length n.

a049463.py

# See https://oeis.org/A049463

from functools import lru_cache
  

@lru_cache(maxsize = None)
def binom(n, k):
    return 1 if k == 0 else n * binom(n - 1, k - 1) // k


@lru_cache(maxsize = None)
def o(n, k, l):
    if min(n, l, k) < 1: return 0
    if k == l == 1: return 1
    return (n - l) * o(n - 1, k - 1, l - 1) + k * o(n - 1, k, l) + sum(
        binom(j, k - 1) * o(n - 1, j, l - 1)
        for j in range(k + 1, l)
        if j != l - 2)


def a049463(n):
    if n == 2: return 1
    return sum(
        o(n - 1, k, l) * (2**k + (n - l) - 2)
        for k in range(1, n - 1)
        for l in range(k, n - 1)
        if k != l - 1)

if __name__ == '__main__':
    for n in range(2, 21):
        print(n, a049463(n))