|
%I #38 Dec 17 2017 08:05:59
%S 1,1,4,23,181,1812,22037,315569,5201602,97009833,2019669961,
%T 46432870222,1168383075471,31939474693297,942565598033196,
%U 29866348653695203,1011335905644178273,36446897413531401020,1392821757824071815641,56259101478392975833333
%N 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.
%C A subclass of chordal-comparability graphs.
%H Jon E. Schoenfield, <a href="/A058863/b058863.txt">Table of n, a(n) for n = 1..100</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 a(n) is asymptotic to sqrt(r*(e-1))/n*(n/(e*r))^n where r = 1 - log(e-1).
%F E.g.f.: -LambertW(exp(-x)-1). - _Vladeta Jovovic_, Nov 22 2002
%F 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
%p S:= series(-LambertW(exp(-x)-1), x, 101):
%p seq(coeff(S,x,j)*j!, j=1..100); # _Robert Israel_, Nov 30 2015
%t a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*k^(k-1), {k, 1, n}];
%t Array[a, 20] (* _Jean-François Alcover_, Dec 17 2017, after _Vladeta Jovovic_ *)
%o (PARI)
%o 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])));}
%o 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));}
%o 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);}
%o \\ _Michel Marcus_, Apr 03 2013
%Y Cf. A007134, A058864, A058865.
%Y Cf. A048802.
%K nonn
%O 1,3
%A Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
%E Formulae edited and completed by _Michel Marcus_, Apr 07 2013
|
