A005217 Number of unlabeled unit interval graphs with n nodes.

1, 2, 4, 9, 21, 55, 151, 447, 1389, 4502, 15046, 51505, 179463, 634086, 2265014, 8163125, 29637903, 108282989, 397761507, 1468063369, 5441174511, 20242989728, 75566702558, 282959337159, 1062523000005, 4000108867555, 15095081362907, 57088782570433

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

References

• S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
• R. W. Robinson, personal communication.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.

Links

• R. W. Robinson, Table of n, a(n) for n = 1..190
• Phil Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.

Programs

Mathematica

m = 30;
A[x_] = (-1 + Exp[Sum[psi[x^k]/k, {k, 1, m}]] /. psi[x_] -> (1 + 2 x - Sqrt[1 - 4 x] Sqrt[1 - 4 x^2])/(4 Sqrt[1 - 4 x^2])) + O[x]^m;
CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Oct 24 2019 *)

Formula

G.f. A(x) = x + 2x^2 + 4x^3 + 9x^4 + 21x^5 + ... satisfies 1 + A(x) = exp( Sum_{k >= 1} psi(x^k)/k ), where psi(x) = (1+2*x-sqrt(1-4*x)*sqrt(1-4*x^2))/(4*sqrt(1-4*x^2)) is the g.f. for A007123.

For asymptotics, see for example Finch.