A050351 Number of 3-level labeled linear rooted trees with n leaves.
1, 1, 5, 37, 365, 4501, 66605, 1149877, 22687565, 503589781, 12420052205, 336947795317, 9972186170765, 319727684645461, 11039636939221805, 408406422098722357, 16116066766061589965, 675700891505466507541
Offset: 0
Keywords
Examples
G.f. = 1 + x + 5*x^2 + 37*x^3 + 365*x^4 + 4501*x^5 + 66605*x^6 + ...
References
- T. S. Motzkin, Sorting numbers ...: for a link to an annotated scanned version of this paper see A000262.
- T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..390
- Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics 186.1-3 (1998): 125-134. See Example 1.
- S. Giraudo, Combinatorial operads from monoids, arXiv preprint arXiv:1306.6938 [math.CO], 2013.
- Marian Muresan, A concrete approach to classical analysis, CMS Books in Mathematics (2009) Table 10.2
- Norihiro Nakashima, Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
- N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
- Index entries for sequences related to rooted trees
Programs
-
Maple
with(combstruct); SeqSeqSetL := [T, {T=Sequence(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},labeled]; -
Mathematica
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 *) a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1/(2 - 1/(2 - Exp[x])), {x, 0, n}]]; (* Michael Somos, Nov 28 2014 *) -
PARI
{a(n) = if( n<0, 0, n! * polcoeff( 1/(2 - 1/(2 - exp(x + x * O(x^n)))), n))}; -
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 -
Sage
A050351 = lambda n: sum(stirling_number2(n,k)*(2^(k-1))*factorial(k) for k in (0..n)) if n>0 else 1 [A050351(n) for n in (0..17)] # Peter Luschny, Jan 18 2016
Formula
E.g.f.: (2-exp(x))/(3-2*exp(x)).
a(n) is asymptotic to (1/6)*n!/log(3/2)^(n+1). - Benoit Cloitre, Jan 30 2003
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
a(n) = Sum_{k=1..n} Stirling2(n, k)*k!*2^(k-1). - Vladeta Jovovic, Sep 28 2003
Recurrence: a(n+1) = 1 + 2*Sum_{j=1..n} binomial(n+1, j)*a(j). - Jon Perry, Apr 25 2005
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
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
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
a(n) = (1/6) * Sum_{k>=1} k^n * (2/3)^k for n>0. - Paul D. Hanna, Nov 28 2014
E.g.f. A(x) satisfies 0 = 2 - A'(x) - 7*A(x) + 6*A(x)^2. - Michael Somos, Nov 28 2014
Comments