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

Author

Robert Castelo, Jan 06 2001

Keywords

• nonn

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.

Crossrefs

Cf. A007134, A058864, A058865.

Cf. A048802.

Programs

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 *)

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

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

Extensions

Formulae edited and completed by Michel Marcus, Apr 07 2013