

A088218


Total number of leaves in all rooted ordered trees with n edges.


180



1, 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Essentially the same as A001700, which has more information.
Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention.  Michael Somos, Jul 30 2011
Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n1,n) = a(n) = essentially A001700.  Vladeta Jovovic, Sep 15 2004
Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4.  Philippe Deléham, Apr 13 2007
a(n) is the number of functions f:[n]>[n] such that for all x,y in [n] if x<y then f(x)<=f(y). So 2*a(n)n = A045992(n).  Geoffrey Critzer, Apr 02 2009
Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,...  Paul Barry, Sep 26 2009
The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662.  Johannes W. Meijer, Apr 20 2011
Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula.  Wolfdieter Lang, Nov 22 2012
(2)*a(n) is the Zsequence for the Riordan triangle A110162. For the notion of Z and Asequences for Riordan arrays see the W. Lang link under A006232 with details and references.  Wolfdieter Lang, Nov 22 2012
Also the number of integer compositions of 2n with alternating (or reversealternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:
() (11) (22) (33)
(121) (132)
(1111) (231)
(1122)
(1221)
(2112)
(2211)
(11121)
(12111)
(111111)
For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.
(End)
Number of terms in the expansion of (x_1+x_2+...+x_n)^n.  César Eliud Lozada, Jan 08 2022


REFERENCES

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 3346.


LINKS



FORMULA

G.f.: (1 + 1 / sqrt(1  4*x)) / 2.
a(n) = binomial(2*n  1, n).
a(n) = (n+1)*A000108(n)/2, n>=1.  B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Feb 05 2002 (in A060150)
a(n) = (0^n + C(2n, n))/2.  Paul Barry, May 21 2004
a(n) is the coefficient of x^n in 1 / (1  x)^n and also the sum of the first n coefficients of 1 / (1  x)^n. Given B(x) with the property that the coefficient of x^n in B(x)^n equals the sum of the first n coefficients of B(x)^n, then B(x) = B(0) / (1  x).
G.f.: 1 / (2  C(x)) = (1  x*C(x))/sqrt(14*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by Wolfdieter Lang, Nov 22 2012.
a(n) = Sum_{k=0..n} binomial(2n, k)cos((nk)*Pi)};
a(n) = Sum_{k=0..n} binomial(n, (nk)/2)(1+(1)^(nk))cos(k*Pi/2)/2} (with interpolated zeros);
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)cos((n2k)Pi/2)} (with interpolated zeros); (End)
G.f.: 1/(1x/(12x/(1(1/2)x/(1(3/2)x/(1(2/3)x/(1(4/3)x/(1(3/4)x/(1(5/4)x/(1... (continued fraction);
E.g.f.: (of aerated sequence) (1 + Bessel_I(0, 2*x))/2. (End)
E.g.f.: E(x) = 1+x/(G(0)2*x) ; G(k) = (k+1)^2+2*x*(2*k+1)2*x*(2*k+3)*((k+1)^2)/G(k+1); (continued fraction).  Sergei N. Gladkovskii, Dec 21 2011
a(n) = Sum_{k=0..n}(1)^k*binomial(2*n,n+k).  Mircea Merca, Jan 28 2012
a(n) = rf(n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial.  Peter Luschny, Nov 21 2012
Dfinite with recurrence: n*a(n) +2*(2*n+1)*a(n1) = 0.  R. J. Mathar, Dec 04 2012
G.f.: 1 + x/W(0), where W(k) = 4*k+1  (4*k+3)*x/(1  (4*k+1)*x/(4*k+3  (4*k+5)*x/(1  (4*k+3)*x/W(k+1) ))) ; (continued fraction).  Sergei N. Gladkovskii, Nov 13 2014
E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2.  Ilya Gutkovskiy, Nov 03 2021
Sum_{n>=0} 1/a(n) = 5/3 + 4*Pi/(9*sqrt(3)).
Sum_{n>=0} (1)^n/a(n) = 3/5  8*log(phi)/(5*sqrt(5)), where phi is the golden ratio (A001622). (End)


EXAMPLE

G.f. = 1 + x + 3*x^2 + 10*x^3 + 35*x^4 + 126*x^5 + 462*x^6 + 1716*x^7 + ...
The five rooted ordered trees with 3 edges have 10 leaves.
..x........................
..o..x.x..x......x.........
..o...o...o.x..x.o..x.x.x..
..r...r....r....r.....r....


MAPLE



MATHEMATICA

a[ n_] := SeriesCoefficient[(1  x)^n, {x, 0, n}];
c = (1  (1  4 x)^(1/2))/(2 x); CoefficientList[Series[1/(1(c1)), {x, 0, 20}], x] (* Geoffrey Critzer, Dec 02 2010 *)
a[ n_] := If[ n < 0, 0, With[ {m = 2 n}, m! SeriesCoefficient[ (1 + BesselI[0, 2 x]) / 2, {x, 0, m}]]]; (* Michael Somos, Nov 22 2014 *)


PROG

(PARI) {a(n) = sum( i=0, n, binomial(n+i2, i))};
(PARI) {a(n) = if( n<0, 0, polcoeff( (1 + 1 / sqrt(1  4*x + x * O(x^n))) / 2, n))};
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / (1  x + x * O(x^n))^n, n))};
(PARI) {a(n) = if( n<0, 0, binomial( 2*n  1, n))};
(PARI) {a(n) = if( n<1, n==0, polcoeff( subst((1  x) / (1  2*x), x, serreverse( x  x^2 + x * O(x^n))), n))};
(Sage)
return rising_factorial(n, n)/falling_factorial(n, n)


CROSSREFS

Same as A001700 modulo initial term and offset.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A003242 counts antirun compositions.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A106356 counts compositions by number of maximal antiruns.
A124754 gives the alternating sum of standard compositions.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reversealternating sum k:
Cf. A000027, A000070, A000097, A000108, A001622, A006232, A008965, A039599, A045992, A058696, A094527, A097070, A110162, A110555, A180662, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.


KEYWORD

nonn


AUTHOR



STATUS

approved



