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

%I #188 Apr 21 2024 09:58:38

%S 1,1,3,10,35,126,462,1716,6435,24310,92378,352716,1352078,5200300,

%T 20058300,77558760,300540195,1166803110,4537567650,17672631900,

%U 68923264410,269128937220,1052049481860,4116715363800,16123801841550,63205303218876,247959266474052

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

%C Essentially the same as A001700, which has more information.

%C Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - _Michael Somos_, Jul 30 2011

%C Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - _Vladeta Jovovic_, Sep 15 2004

%C 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

%C 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

%C Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - _Paul Barry_, Sep 26 2009

%C 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

%C Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - _Wolfdieter Lang_, Nov 22 2012

%C (-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - _Wolfdieter Lang_, Nov 22 2012

%C From _Gus Wiseman_, Jun 27 2021: (Start)

%C Also the number of integer compositions of 2n with alternating (or reverse-alternating) 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:

%C () (11) (22) (33)

%C (121) (132)

%C (1111) (231)

%C (1122)

%C (1221)

%C (2112)

%C (2211)

%C (11121)

%C (12111)

%C (111111)

%C For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.

%C (End)

%C Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - _César Eliud Lozada_, Jan 08 2022

%D L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

%H Vincenzo Librandi, <a href="/A088218/b088218.txt">Table of n, a(n) for n = 0..200</a>

%H Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, <a href="https://arxiv.org/abs/2301.09765">Enumeration of multi-rooted plane trees</a>, arXiv:2301.09765 [math.CO], 2023.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

%H B. Dasarathy and C. Yang, <a href="http://dx.doi.org/10.1093/comjnl/23.2.161">A transformation on ordered trees</a>, Comput. J. 23 (1980) 161-164. - _Nachum Dershowitz_, Sep 01 2016

%H Toufik Mansour and Mark Shattuck, <a href="http://dx.doi.org/10.1007/s12044-014-0166-7">A statistic on n-color compositions and related sequences</a>, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

%H Anthony Mansuy, <a href="https://doi.org/10.1016/j.jalgebra.2014.04.017">Preordered forests, packed words and contraction algebras</a>, J. Algebra 411 (2014) 259-311.

%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a>, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

%H A. Vogt, <a href="http://arxiv.org/abs/1108.2993">Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation</a>, arXiv preprint arXiv:1108.2993 [hep-ph], 2011.

%F G.f.: (1 + 1 / sqrt(1 - 4*x)) / 2.

%F a(n) = binomial(2*n - 1, n).

%F a(n) = (n+1)*A000108(n)/2, n>=1. - B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Feb 05 2002 (in A060150)

%F a(n) = (0^n + C(2n, n))/2. - _Paul Barry_, May 21 2004

%F 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).

%F G.f.: 1 / (2 - C(x)) = (1 - x*C(x))/sqrt(1-4*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by _Wolfdieter Lang_, Nov 22 2012.

%F From _Paul Barry_, Nov 02 2004: (Start)

%F a(n) = Sum_{k=0..n} binomial(2n, k)cos((n-k)*Pi)};

%F a(n) = Sum_{k=0..n} binomial(n, (n-k)/2)(1+(-1)^(n-k))cos(k*Pi/2)/2} (with interpolated zeros);

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)cos((n-2k)Pi/2)} (with interpolated zeros); (End)

%F a(n) = A110556(n)*(-1)^n, central terms in triangle A110555. - _Reinhard Zumkeller_, Jul 27 2005

%F a(n) = Sum_{0<=k<=n} A094527(n,k)*(-1)^k. - _Philippe Deléham_, Mar 14 2007

%F From _Paul Barry_, Mar 29 2010: (Start)

%F G.f.: 1/(1-x/(1-2x/(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);

%F E.g.f.: (of aerated sequence) (1 + Bessel_I(0, 2*x))/2. (End)

%F a(n + 1) = A001700(n). a(n) = A024718(n) - A024718(n - 1).

%F 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

%F a(n) = Sum_{k=0..n}(-1)^k*binomial(2*n,n+k). - _Mircea Merca_, Jan 28 2012

%F a(n) = rf(n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial. - _Peter Luschny_, Nov 21 2012

%F D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) = 0. - _R. J. Mathar_, Dec 04 2012

%F a(n) = hypergeom([1-n,-n],[1],1). - _Peter Luschny_, Sep 22 2014

%F 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

%F a(n) = A000984(n) + A001791(n). - _Gus Wiseman_, Jun 28 2021

%F E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2. - _Ilya Gutkovskiy_, Nov 03 2021

%F From _Amiram Eldar_, Mar 12 2023: (Start)

%F Sum_{n>=0} 1/a(n) = 5/3 + 4*Pi/(9*sqrt(3)).

%F Sum_{n>=0} (-1)^n/a(n) = 3/5 - 8*log(phi)/(5*sqrt(5)), where phi is the golden ratio (A001622). (End)

%F a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - _Stefano Spezia_, Apr 17 2024

%e G.f. = 1 + x + 3*x^2 + 10*x^3 + 35*x^4 + 126*x^5 + 462*x^6 + 1716*x^7 + ...

%e The five rooted ordered trees with 3 edges have 10 leaves.

%e ..x........................

%e ..o..x.x..x......x.........

%e ..o...o...o.x..x.o..x.x.x..

%e ..r...r....r....r.....r....

%p seq(binomial(2*n-1, n),n=0..24); # _Peter Luschny_, Sep 22 2014

%t a[ n_] := SeriesCoefficient[(1 - x)^-n, {x, 0, n}];

%t c = (1 - (1 - 4 x)^(1/2))/(2 x);CoefficientList[Series[1/(1-(c-1)),{x,0,20}],x] (* _Geoffrey Critzer_, Dec 02 2010 *)

%t Table[Binomial[2 n - 1, n], {n, 0, 20}] (* _Vincenzo Librandi_, Aug 07 2014 *)

%t 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 *)

%o (PARI) {a(n) = sum( i=0, n, binomial(n+i-2,i))};

%o (PARI) {a(n) = if( n<0, 0, polcoeff( (1 + 1 / sqrt(1 - 4*x + x * O(x^n))) / 2, n))};

%o (PARI) {a(n) = if( n<0, 0, polcoeff( 1 / (1 - x + x * O(x^n))^n, n))};

%o (PARI) {a(n) = if( n<0, 0, binomial( 2*n - 1, n))};

%o (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))};

%o (Sage)

%o def A088218(n):

%o return rising_factorial(n,n)/falling_factorial(n,n)

%o [A088218(n) for n in (0..24)] # _Peter Luschny_, Nov 21 2012

%o (Magma) [Binomial(2*n-1, n): n in [0..30]]; // _Vincenzo Librandi_, Aug 07 2014

%Y Same as A001700 modulo initial term and offset.

%Y First differences are A024718.

%Y Main diagonal of A071919 and of A305161.

%Y A signed version is A110556.

%Y A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.

%Y A003242 counts anti-run compositions.

%Y A025047 counts wiggly compositions (ascend: A025048, descend: A025049).

%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).

%Y A106356 counts compositions by number of maximal anti-runs.

%Y A124754 gives the alternating sum of standard compositions.

%Y A345197 counts compositions by sum, length, and alternating sum.

%Y Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:

%Y - k = 0: counted by A088218 (this sequence), ranked by A344619/A344619.

%Y - k = 1: counted by A000984, ranked by A345909/A345911.

%Y - k = -1: counted by A001791, ranked by A345910/A345912.

%Y - k = 2: counted by A088218 (this sequence), ranked by A345925/A345922.

%Y - k = -2: counted by A002054, ranked by A345924/A345923.

%Y - k >= 0: counted by A116406, ranked by A345913/A345914.

%Y - k <= 0: counted by A058622(n-1), ranked by A345915/A345916.

%Y - k > 0: counted by A027306, ranked by A345917/A345918.

%Y - k < 0: counted by A294175, ranked by A345919/A345920.

%Y - k != 0: counted by A058622, ranked by A345921/A345921.

%Y - k even: counted by A081294, ranked by A053754/A053754.

%Y - k odd: counted by A000302, ranked by A053738/A053738.

%Y Cf. A000027, A000070, A000097, A000108, A001622, A006232, A008965, A039599, A045992, A058696, A094527, A097070, A110162, A110555, A180662, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.

%K nonn

%O 0,3

%A _Michael Somos_, Sep 24 2003