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

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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