login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058864 Number of labeled chordal graphs (connected or not) on n nodes with no induced path P_4. 13
1, 2, 8, 49, 402, 4144, 51515, 750348, 12537204, 236424087, 4967735896, 115102258660, 2915655255385, 80164472149454, 2377679022913612, 75674858155603353, 2572626389524849478, 93040490884813025684 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
A subclass of chordal-comparability graphs.
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
LINKS
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.
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
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 *)
PROG
(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
CROSSREFS
Cf. variants: A196555, A196556, A196557.
Sequence in context: A183070 A032116 A088181 * A332237 A136226 A046165
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:33 EDT 2024. Contains 371235 sequences. (Running on oeis4.)