The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 5
 1, 1, 4, 23, 181, 1812, 22037, 315569, 5201602, 97009833, 2019669961, 46432870222, 1168383075471, 31939474693297, 942565598033196, 29866348653695203, 1011335905644178273, 36446897413531401020, 1392821757824071815641, 56259101478392975833333 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 24 09:52 EDT 2021. Contains 346273 sequences. (Running on oeis4.)