login
Number of unlabeled unit interval graphs with n nodes.
(Formerly M1186)
2

%I M1186 #24 Oct 27 2023 05:59:30

%S 1,2,4,9,21,55,151,447,1389,4502,15046,51505,179463,634086,2265014,

%T 8163125,29637903,108282989,397761507,1468063369,5441174511,

%U 20242989728,75566702558,282959337159,1062523000005,4000108867555,15095081362907,57088782570433

%N Number of unlabeled unit interval graphs with n nodes.

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.

%D R. W. Robinson, personal communication.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.

%H R. W. Robinson, <a href="/A005217/b005217.txt">Table of n, a(n) for n = 1..190</a>

%H Phil Hanlon, <a href="http://dx.doi.org/10.1090/S0002-9947-1982-0662044-8">Counting interval graphs</a>, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.

%F 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.

%F For asymptotics, see for example Finch.

%t m = 30;

%t 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;

%t CoefficientList[A[x], x] // Rest (* _Jean-François Alcover_, Oct 24 2019 *)

%K nonn

%O 1,2

%A _N. J. A. Sloane_