|
%I #181 Mar 12 2023 04:21:17
%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)
%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. A000070, A000097, A001622, A008965, A058696, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.
%K nonn
%O 0,3
%A _Michael Somos_, Sep 24 2003
| 