|
|
A050351
|
|
Number of 3-level labeled linear rooted trees with n leaves.
|
|
26
|
|
|
1, 1, 5, 37, 365, 4501, 66605, 1149877, 22687565, 503589781, 12420052205, 336947795317, 9972186170765, 319727684645461, 11039636939221805, 408406422098722357, 16116066766061589965, 675700891505466507541
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Lists of lists of sets.
|
|
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
|
|
|
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) satisifes 0 = 2 - A'(x) - 7*A(x) + 6*A(x)^2. - Michael Somos, Nov 28 2014
|
|
EXAMPLE
|
G.f. = 1 + x + 5*x^2 + 37*x^3 + 365*x^4 + 4501*x^5 + 66605*x^6 + ...
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|