|
%I #66 May 30 2019 16:57:30
%S 1,1,5,37,365,4501,66605,1149877,22687565,503589781,12420052205,
%T 336947795317,9972186170765,319727684645461,11039636939221805,
%U 408406422098722357,16116066766061589965,675700891505466507541
%N Number of 3-level labeled linear rooted trees with n leaves.
%C Lists of lists of sets.
%D T. S. Motzkin, Sorting numbers ...: for a link to an annotated scanned version of this paper see A000262.
%D T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
%H G. C. Greubel, <a href="/A050351/b050351.txt">Table of n, a(n) for n = 0..390</a>
%H Robert Gill, <a href="https://doi.org/10.1016/S0012-365X(97)00187-8">The number of elements in a generalized partition semilattice</a>, Discrete mathematics 186.1-3 (1998): 125-134. See Example 1.
%H S. Giraudo, <a href="http://arxiv.org/abs/1306.6938">Combinatorial operads from monoids</a>, arXiv preprint arXiv:1306.6938 [math.CO], 2013.
%H Marian Muresan, <a href="https://doi.org/10.1007/978-0-387-78933-0">A concrete approach to classical analysis</a>, CMS Books in Mathematics (2009) Table 10.2
%H Norihiro Nakashima, Shuhei Tsujie, <a href="https://arxiv.org/abs/1904.09748">Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species</a>, arXiv:1904.09748 [math.CO], 2019.
%H N. J. A. Sloane and Thomas Wieder, <a href="http://arXiv.org/abs/math.CO/0307064">The Number of Hierarchical Orderings</a>, Order 21 (2004), 83-89.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F E.g.f.: (2-exp(x))/(3-2*exp(x)).
%F a(n) is asymptotic to (1/6)*n!/log(3/2)^(n+1). - _Benoit Cloitre_, Jan 30 2003
%F For m-level trees (m>1), e.g.f. is (m-1-(m-2)*e^x)/(m-(m-1)*e^x) and number of trees is 1/(m*(m-1))*sum(k>=0, (1-1/m)^k*k^n). Here m=3, so a(n)=(1/6)*sum(k>=0, (2/3)^k*k^n) (for n>0). - _Benoit Cloitre_, Jan 30 2003
%F a(n) = Sum_{k=1..n} Stirling2(n, k)*k!*2^(k-1). - _Vladeta Jovovic_, Sep 28 2003
%F Recurrence: a(n+1) = 1 + 2*sum { j=1, n, (binomial(n+1, j)*a(j) }. - _Jon Perry_, Apr 25 2005
%F With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n)=sum_{i=1}^{p(n)}(n!/(prod_{j=1}^{p(i)}p(i, j)!))*(p(i)!/(prod_{j=1}^{d(i)} m(i, j)!))*2^(p(i)-1). - _Thomas Wieder_, May 18 2005
%F Let f(x) = (1+x)*(1+2*x). Let D be the operator g(x) -> d/dx(f(x)*g(x)). Then for n>=1, a(n) = D^(n-1)(1) evaluated at x = 1/2. Compare with the result A000670(n) = D^(n-1)(1) at x = 0. See also A194649. - _Peter Bala_, Sep 05 2011
%F E.g.f.: 1 + x/(G(0)-3*x) where G(k)= x + k + 1 - x*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - _Sergei N. Gladkovskii_, Jul 11 2012
%F a(n) = (1/6) * Sum_{k>=1} k^n * (2/3)^k for n>0. - _Paul D. Hanna_, Nov 28 2014
%F E.g.f. A(x) satisifes 0 = 2 - A'(x) - 7*A(x) + 6*A(x)^2. - _Michael Somos_, Nov 28 2014
%e G.f. = 1 + x + 5*x^2 + 37*x^3 + 365*x^4 + 4501*x^5 + 66605*x^6 + ...
%p with(combstruct); SeqSeqSetL := [T, {T=Sequence(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},labeled];
%t With[{nn=20},CoefficientList[Series[(2-E^x)/(3-2*E^x),{x,0,nn}],x] Range[0,nn]!] (* _Harvey P. Dale_, Feb 29 2012 *)
%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1/(2 - 1/(2 - Exp[x])), {x, 0, n}]]; (* _Michael Somos_, Nov 28 2014 *)
%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( 1/(2 - 1/(2 - exp(x + x * O(x^n)))), n))};
%o (PARI) {a(n)=if(n==0, 1, (1/6)*round(suminf(k=1, k^n * (2/3)^k *1.)))} \\ _Paul D. Hanna_, Nov 28 2014
%o (Sage)
%o A050351 = lambda n: sum(stirling_number2(n,k)*(2^(k-1))*factorial(k) for k in (0..n)) if n>0 else 1
%o [A050351(n) for n in (0..17)] # _Peter Luschny_, Jan 18 2016
%Y Cf. A000670, A050352-A050359.
%Y Equals 1/2 * A004123(n) for n>0.
%K nonn
%O 0,3
%A _Christian G. Bower_, Oct 15 1999
| 