login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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, 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.

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

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

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

Cf. A001700, A024718, A110556.

Main diagonal of A071919 and of A305161.

Sequence in context: A318117 A110556 A001700 * A300975 A072266 A085282

Adjacent sequences:  A088215 A088216 A088217 * A088219 A088220 A088221

KEYWORD

nonn,changed

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 03:06 EDT 2018. Contains 313904 sequences. (Running on oeis4.)