|
%I M3648 #107 May 30 2022 12:28:36
%S 1,4,32,416,7552,176128,5018624,168968192,6563282944,288909131776,
%T 14212910809088,772776684683264,46017323176296448,2978458881388183552,
%U 208198894960190160896,15631251601179130462208,1254492810303112820555776,107174403941451434687463424,9711022458989438255300083712
%N Number of labeled rooted trees of subsets of an n-set.
%C Each node is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have at least two children.
%C _John W. Layman_ observes that this is the Stirling transform of A005264.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.
%H T. D. Noe and Vaclav Kotesovec, <a href="/A005172/b005172.txt">Table of n, a(n) for n = 1..240</a> (terms 1..30 from T. D. Noe)
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H F. Chapoton, F. Hivert, and J.-C. Novelli, <a href="http://arxiv.org/abs/1307.0092">A set-operad of formal fractions and dendriform-like sub-operads</a>, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a>, arXiv:math/0501052 [math.CA], 2005.
%H L. R. Foulds and R. W. Robinson, <a href="http://dx.doi.org/10.1007/BFb0088905">Determining the asymptotic number of phylogenetic trees</a>, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lect. Notes in Math., 829. Springer, 1980.
%H L. R. Foulds and R. W. Robinson, <a href="/A005172/a005172_1.pdf">Determining the asymptotic number of phylogenetic trees</a>, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
%H J. P. Hayes, <a href="http://dx.doi.org/10.1145/321978.321988">Enumeration of fanout-free Boolean functions</a>, J. ACM, 23 (1976), 700-709.
%H F. R. McMorris and T. Zaslavsky, <a href="http://dx.doi.org/10.1016/0025-5564(81)90071-7">The number of cladistic characters</a>, Math. Biosciences, 54 (1981), 3-10.
%H F. R. McMorris and T. Zaslavsky, <a href="/A005172/a005172.pdf">The number of cladistic characters</a>, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
%H István Mezo, Victor H. Moll, José L. Ramírez, and Diego Villamizar, <a href="https://arxiv.org/abs/2103.04151">On the r-Derangements of type B</a>, arXiv:2103.04151 [math.CO], 2021.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F E.g.f.: -1/2 - LambertW ( - exp( -1/2 + x) / 2 ).
%F E.g.f.: A(x) = 1 + Integral A(x)*(1 + A(x))^2 dx. - _Paul D. Hanna_, Sep 06 2008
%F From _Peter Bala_, Sep 06 2011: (Start)
%F The generating function A(x) = x+4*x^2/2!+32*x^3/3!+... satisfies the autonomous differential equation A'(x) = (1+2*A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = Integral_{t = 0..x} (1-2*t)/(1+2*t) dt = log(1+2*x)-x.
%F The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+2*x)/(1-2*x)*g(x)). Compare with A032188.
%F Applying [Bergeron et al., Theorem 1] to the result x = Integral_{t = 0..A(x)} 1/phi(t) dt, where phi(t) = (1+2*t)/(1-2*t) = 1+4*t+8*t^2+16*t^3+32*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >= 1 can be colored in 2^(k+1) ways. An example is given below. (End)
%F a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (-1)^j/(k-j)!*Sum_{i=0..j} (-1)^i* 2^(n-i+j-1)*Stirling1(n-i+j-1,j-i)/((n-i+j-1)!*i!), n>1, a(1)=1. - _Vladimir Kruchinin_, Jan 30 2012
%F Let p(n,w) = w*Sum_{k=0..n-1}((-1)^k*E2(n-1,k)*w^k)/(1+w)^(2*n-1), E2 the second-order Eulerian numbers as defined by Knuth, then a(n) = -p(n,-1/2). - _Peter Luschny_, Nov 10 2012
%F a(n) ~ (2/(2*log(2)-1))^(n-1/2)*n^(n-1)/exp(n). - _Vaclav Kotesovec_, Jan 05 2013
%F G.f.: 1/Q(0), where Q(k)= 1 - 2*(k+1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 01 2013
%F a(n) = 2*a(n-1) + Sum_{j=1..n-1} binomial(n,j)*a(j)*a(n-j) for n>1, a(1) = 1. - _Peter Luschny_, May 24 2017
%F a(1) = 1; a(n) = n! * [x^n] exp(x + Sum_{k=1..n-1} a(k)*x^k/k!). - _Ilya Gutkovskiy_, Oct 18 2017
%e x + 4*x^2 + 32*x^3 + 416*x^4 + 7552*x^5 + 176128*x^6 + 5018624*x^7 + ...
%e D^3(1) = 32*(12*x^2+28*x+13)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 416.
%e From _Peter Bala_, Sep 06 2011: (Start)
%e a(3) = 32: The 32 increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k+1) colors are
%e .
%e 1(x4 colors) 1(x8 colors) 1(x8 colors)
%e | / \ / \
%e 2(x4 colors) 2 3 3 2
%e |
%e 3
%e .
%e Totals: 16 + 8 + 8 = 32. (End)
%p with(combinat); A005172 := n -> add(eulerian2(n-1,k)*2^(2*n-k-2),k=0..n-1): seq(A005172(n), n=1..16); # _Peter Luschny_, Nov 10 2012
%p A005172_list := proc(len) local A, n; A[1] := 1; for n from 2 to len do
%p A[n] := 2*A[n-1] + add(binomial(n,j)*A[j]*A[n-j], j=1..n-1) od:
%p convert(A,list) end: A005172_list(19); # _Peter Luschny_, May 24 2017
%t max = 16; g[x_] := -1/2 - ProductLog[-E^(-1/2 + x)/2]; Drop[ CoefficientList[ Series[ g[x], {x, 0, max}], x]*Range[0, max]!, 1](* _Jean-François Alcover_, Nov 17 2011, after 1st e.g.f. *)
%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ -1/2 - ProductLog[ -Exp[ -1/2 + z] / 2], {z, 0, n}]] (* _Michael Somos_, Jun 07 2012 *)
%t a[1] = 1; a[n_] := (Sum[(n + k - 1)!*Sum[(-1)^j/(k - j)!*Sum[(-1)^i*2^(n - i + j - 1)*StirlingS1[n - i + j - 1, j - i]/((n - i + j - 1)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, n - 1}]);
%t Array[a, 20] (* _Jean-François Alcover_, Jun 24 2018, after _Vladimir Kruchinin_ *)
%t Eulerian2[n_, k_] := Eulerian2[n, k] = If[k == 0, 1, If[k == n, 0, Eulerian2[n-1, k] (k + 1) + Eulerian2[n - 1, k - 1] (2n - k - 1)]]; A005172[n_] := Sum[Eulerian2[n - 1, k] 2^(2 n - k - 2), {k, 0, n - 1}]; Table[A005172[n], {n, 19}] (* _Peter Luschny_, Jun 24 2018 *)
%o (PARI) {a(n)=local(A=1+x);for(i=0,n,A=1+intformal(A*(1+A+x*O(x^n))^2));n!*polcoeff(A,n)} \\ _Paul D. Hanna_, Sep 06 2008
%o (Maxima) a(n):=if n=1 then 1 else (sum((n+k-1)!*sum((-1)^j/(k-j)!*sum((-1)^i*2^(n-i+j-1)*stirling1(n-i+j-1,j-i)/((n-i+j-1)!*i!),i,0,j),j,1,k),k,1,n-1)); /* _Vladimir Kruchinin_, Jan 30 2012 */
%o (Sage)
%o @CachedFunction
%o def eulerian2(n, k):
%o if k==0: return 1
%o elif k==n: return 0
%o return eulerian2(n-1, k)*(k+1)+eulerian2(n-1, k-1)*(2*n-k-1)
%o A005172 = lambda n: add(eulerian2(n-1,k)*2^(2*n-k-2) for k in (0..n-1))
%o [A005172(n) for n in (1..16)] # _Peter Luschny_, Nov 10 2012
%o (PARI) N=66; x='x+O('x^N);
%o Q(k)=if(k>N,1,1-2*(k+1)*x-2*x*(k+1)/Q(k+1));
%o gf=1/Q(0); Vec(gf) \\ _Joerg Arndt_, May 01 2013
%Y Cf. A005640, A032188.
%Y See A225170 for another version.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_
|
