|
%I #44 Dec 25 2018 22:35:58
%S 1,2,8,49,402,4144,51515,750348,12537204,236424087,4967735896,
%T 115102258660,2915655255385,80164472149454,2377679022913612,
%U 75674858155603353,2572626389524849478,93040490884813025684
%N Number of labeled chordal graphs (connected or not) on n nodes with no induced path P_4.
%C A subclass of chordal-comparability graphs.
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
%H G. C. Greubel, <a href="/A058864/b058864.txt">Table of n, a(n) for n = 1..398</a>
%H R. Castelo and N. C. Wormald, <a href="http://www.math.uwaterloo.ca/~nwormald/papers/chordal.pdf">Enumeration of P4-free chordal graphs</a>.
%H R. Castelo and N. C. Wormald, <a href="http://dx.doi.org/10.1007/s00373-002-0513-9">Enumeration of P4-Free chordal graphs</a>, Graphs and Combinatorics, 19:467-474, 2003.
%H M. C. Golumbic, <a href="http://dx.doi.org/10.1016/0012-365X(78)90178-4">Trivially perfect graphs</a>, Discr. Math. 24(1) (1978), 105-107.
%H Venkatesan Guruswami, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00022-9">Enumerative aspects of certain subclasses of perfect graphs</a>, Discrete Math. 205 (1999), 97-117.
%H T. H. Ma and J. P. Spinrad, <a href="http://dx.doi.org/10.1007/BF00385814">Cycle-free partial orders and chordal comparability graphs</a>, Order, 1991, 8:49-61.
%H E. S. Wolk, <a href="http://dx.doi.org/10.1090/S0002-9939-1965-0172274-5">A note on the comparability graph of a tree</a>, Proc. Am. Math. Soc., 1965, 16:17-20.
%F A058863 and A058864 satisfy:
%F 1) c(n) = 1 + Sum_{k=1..n-2} binomial(n, k)*(t(n-k) - c(n-k))
%F 2) t(n) = c(n) + Sum_{k=1..n-1} k*c(k)*binomial(n, k)*t(n-k))/n
%F where c(n) (A058863) is the number of connected graphs of this type and t(n) (A058864) is the total number of such graphs.
%F 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
%F E.g.f.: exp(-LambertW(exp(-x)-1)). - _Vladeta Jovovic_, Nov 22 2002
%F a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling2(n, k)*(k+1)^(k-1). - _Vladeta Jovovic_, Nov 12 2003
%F 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
%t Rest[With[{nmax = 50}, CoefficientList[Series[Exp[-LambertW[Exp[-x] - 1]], {x, 0, nmax}], x]*Range[0, nmax]!]] (* _G. C. Greubel_, Nov 14 2017 *)
%t a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*(k+1)^(k-1), {k, 0, n}];
%t Array[a, 18] (* _Jean-François Alcover_, Dec 17 2017, after _Vladeta Jovovic_ *)
%o (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 */
%o (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
%Y Cf. A007134, A058863, A058865.
%Y Cf. variants: A196555, A196556, A196557.
%K nonn
%O 1,2
%A Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
%E Formulae edited and completed by _Michel Marcus_, Apr 07 2013
|
