login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A088218 Total number of leaves in all rooted ordered trees with n edges. 132
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*n-1,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 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

From Gus Wiseman, Jun 27 2021: (Start)

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:

  ()  (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)

REFERENCES

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

B. Dasarathy and C. Yang, A transformation on ordered trees, Comput. J. 23 (1980) 161-164. - Nachum Dershowitz, Sep 01 2016

T. Mansour and M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

A. Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311.

Mircea Merca, A Note on Cosine Power Sums, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv preprint arXiv:1108.2993 [hep-ph], 2011.

FORMULA

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(1-4*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by Wolfdieter Lang, Nov 22 2012.

G.f.: (1 + 1 / sqrt(1 - 4*x)) / 2. a(n) = binomial( 2*n - 1, n).

From Paul Barry, Nov 02 2004: (Start)

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

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

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

a(n) = A110556(n)*(-1)^n, central terms in triangle A110555. - Reinhard Zumkeller, Jul 27 2005

a(n) = Sum_{0<=k<=n} A094527(n,k)*(-1)^k. - Philippe Deléham, Mar 14 2007

From Paul Barry, Mar 29 2010: (Start)

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);

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

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

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

D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Dec 04 2012

a(n) = binomial(2*n-1, n). - Vincenzo Librandi, Aug 07 2014

a(n) = hypergeom([1-n,-n],[1],1). - Peter Luschny, Sep 22 2014

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

a(n) = A000984(n) + A001791(n). - Gus Wiseman, Jun 28 2021

E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2. - Ilya Gutkovskiy, Nov 03 2021

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

seq(binomial(2*n-1, n), n=0..24); # Peter Luschny, Sep 22 2014

MATHEMATICA

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

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

Table[Binomial[2 n - 1, n], {n, 0, 20}] (* Vincenzo Librandi, Aug 07 2014 *)

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+i-2, 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)

def A088218(n):

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

[A088218(n) for n in (0..24)]  # Peter Luschny, Nov 21 2012

(MAGMA) [Binomial(2*n-1, n): n in [0..30]]; // Vincenzo Librandi, Aug 07 2014

CROSSREFS

Same as A001700 modulo initial term and offset.

First differences are A024718.

Main diagonal of A071919 and of A305161.

A signed version is A110556.

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

A003242 counts anti-run compositions.

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

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

A106356 counts compositions by number of maximal anti-runs.

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/reverse-alternating sum k:

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

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

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

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

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

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

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

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

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

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

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

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

Cf. A000070, A000097, A008965, A058696, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.

Sequence in context: A318117 A110556 A001700 * A300975 A072266 A085282

Adjacent sequences:  A088215 A088216 A088217 * A088219 A088220 A088221

KEYWORD

nonn

AUTHOR

Michael Somos, Sep 24 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 11:13 EST 2021. Contains 349462 sequences. (Running on oeis4.)