A058864 Number of labeled chordal graphs (connected or not) on n nodes with no induced path P_4.

1, 2, 8, 49, 402, 4144, 51515, 750348, 12537204, 236424087, 4967735896, 115102258660, 2915655255385, 80164472149454, 2377679022913612, 75674858155603353, 2572626389524849478, 93040490884813025684, 3566833833735159397963, 144485408698878208399296

Offset: 1

Author

Robert Castelo, Jan 06 2001

Keywords

• nonn

Comments

A subclass of chordal-comparability graphs.

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..398
• 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, A058863, A058865.

Cf. variants: A196555, A196556, A196557.

Programs

Mathematica

Rest[With[{nmax = 50}, CoefficientList[Series[Exp[-LambertW[Exp[-x] - 1]], {x, 0, nmax}], x]*Range[0, nmax]!]] (* G. C. Greubel, Nov 14 2017 *)
a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*(k+1)^(k-1), {k, 0, n}];
Array[a, 18] (* Jean-François Alcover, Dec 17 2017, after Vladeta Jovovic *)

PARI

{a(n)=polcoeff(sum(m=1, n, (m+1)^(m-1)*x^m/prod(k=1, m, 1+k*x+x*O(x^n))), n)} /* Paul D. Hanna, Jul 20 2011 */

PARI

for(n=1,10, print1(sum(k=0, n, (-1)^(n-k)*stirling(n,k,2)*(k+1)^(k-1)), ", ")) \\ G. C. Greubel, Nov 14 2017

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.

O.g.f.: Sum_{n>=1} (n+1)^(n-1) * x^n / Product_{k=1..n} (1+k*x). - Paul D. Hanna, Jul 20 2011

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

a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling2(n, k)*(k+1)^(k-1). - Vladeta Jovovic, Nov 12 2003

a(n) ~ sqrt(exp(1)-1) * exp(1-n) * n^(n-1) * (1-log(exp(1)-1))^(1/2-n). - Vaclav Kotesovec, Oct 18 2013

Extensions

Formulae edited and completed by Michel Marcus, Apr 07 2013