A058863 Number of connected labeled chordal graphs on n nodes with no induced path P_4; also the number of labeled trees with each vertex replaced by a clique.

1, 1, 4, 23, 181, 1812, 22037, 315569, 5201602, 97009833, 2019669961, 46432870222, 1168383075471, 31939474693297, 942565598033196, 29866348653695203, 1011335905644178273, 36446897413531401020, 1392821757824071815641, 56259101478392975833333

Offset

1,3

Comments

A subclass of chordal-comparability graphs.

Links

Jon E. Schoenfield, Table of n, a(n) for n = 1..100

R. Castelo and N. C. Wormald, Enumeration of P4-free chordal graphs

R. Castelo and N. C. Wormald, Enumeration of P4-Free chordal graphs, Graphs and Combinatorics, 19:467-474, 2003.

M. C. Golumbic, Trivially perfect graphs, Discr. Math. 24(1) (1978), 105-107.

Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117.

T. H. Ma and J. P. Spinrad, Cycle-free partial orders and chordal comparability graphs, Order, 1991, 8:49-61.

E. S. Wolk, A note on the comparability graph of a tree, Proc. Am. Math. Soc., 1965, 16:17-20.

Formula

A058863 and A058864 satisfy:

1) c(n) = 1 + Sum_{k=1..n-2} binomial(n, k)*(t(n-k) - c(n-k))

2) t(n) = c(n) + Sum_{k=1..n-1} k*c(k)*binomial(n, k)*t(n-k))/n

where c(n) (A058863) is the number of connected graphs of this type and t(n) (A058864) is the total number of such graphs.

a(n) is asymptotic to sqrt(r*(e-1))/n*(n/(e*r))^n where r = 1 - log(e-1).

E.g.f.: -LambertW(exp(-x)-1). - Vladeta Jovovic, Nov 22 2002

a(n) = Sum_{k=0..n} Stirling2(n, k)*A060356(k). Also a(n) = Sum_{k=1..n} (-1)^(n-k)*Stirling2(n, k)*k^(k-1). - Vladeta Jovovic, Sep 17 2003

Maple

S:= series(-LambertW(exp(-x)-1), x, 101):
seq(coeff(S, x, j)*j!, j=1..100); # Robert Israel, Nov 30 2015

Mathematica

a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*k^(k-1), {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, Dec 17 2017, after Vladeta Jovovic *)

Prog

(PARI)
geta(n, va, vA) = {local(k); if (n==1, return(1)); if (n==2, return(1)); return(1 + sum(k=1, n-2, binomial(n, k)*(vA[n-k] - va[n-k]))); }
getA(n, va, vA) = {local(k); if (n==1, return(1)); if (n==2, return(2)); return ((va[n] + sum(k=1, n-1, k*va[k]*binomial(n, k)*vA[n-k])/n)); }
both(n) = {va = vector(n); vA = vector(n); for (i=1, n, va[i] = geta(i, va, vA); vA[i] = getA(i, va, vA); ); print("va_A058863=", va); print("vA_A058864=", vA); }
\\ Michel Marcus, Apr 03 2013

Crossrefs

Cf. A007134, A058864, A058865.

Cf. A048802.

Sequence in context: A220214 A106174 A056814 * A192840 A302189 A292971

Adjacent sequences: A058860 A058861 A058862 * A058864 A058865 A058866

Keyword

nonn

Author

Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001

Extensions

Formulae edited and completed by Michel Marcus, Apr 07 2013

Status

approved