A000891 -id:A000891 - cp's OEIS frontend

A358582 Number of rooted trees with n nodes, most of which are not leaves.

0, 0, 1, 1, 5, 7, 28, 48, 176, 336, 1179, 2420, 8269, 17855, 59832, 134289, 443407, 1025685, 3346702, 7933161, 25632265, 62000170, 198670299, 488801159, 1555187172, 3882403641, 12276230777, 31034921462, 97601239282, 249471619165, 780790439063, 2015194486878

Offset: 1

Gus Wiseman, Nov 23 2022

nonn

			The a(3) = 1 through a(6) = 7 trees:
  ((o))  (((o)))  (((oo)))   ((((oo))))
                  ((o)(o))   (((o)(o)))
                  ((o(o)))   (((o(o))))
                  (o((o)))   ((o)((o)))
                  ((((o))))  ((o((o))))
                             (o(((o))))
                             (((((o)))))

Andrew Howroyd, Table of n, a(n) for n = 1..200

For equality we have A185650 aerated, ranked by A358578.
The opposite version is A358581, non-strict A358583.
The non-strict version is A358584.
The ordered version is A358585, odd-indexed terms A065097.
A000081 counts rooted trees, ordered A000108.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
A358589 counts square trees, ranked by A358577, ordered A358590.
Cf. A000891, A034781, A109129, A342507, A358579, A358580, A358586, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{0,Infinity}][_],{0,Infinity}]&]],{n,0,10}]

\\ See A358584 for R(n).
seq(n) = {my(A=R(n)); vector(n, n, vecsum(Vecrev(A[n]/y)[1..(n-1)\2]))} \\ Andrew Howroyd, Dec 30 2022

A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=1..floor((n-1)/2)} A055277(n, k). - Andrew Howroyd, Dec 30 2022

Terms a(19) and beyond from Andrew Howroyd, Dec 30 2022

A358585 Number of ordered rooted trees with n nodes, most of which are leaves.

Original entry on oeis.org

1, 0, 1, 1, 7, 11, 66, 127, 715, 1549, 8398, 19691, 104006, 258194, 1337220, 3467115, 17678835, 47440745, 238819350, 659060677, 3282060210, 9271024542, 45741281820, 131788178171, 644952073662, 1890110798926, 9183676536076, 27316119923002, 131873975875180, 397407983278484

Offset: 1

Gus Wiseman, Nov 24 2022

nonn

			The a(1) = 1 through a(6) = 11 ordered trees:
  o  .  (oo)  (ooo)  (oooo)   (ooooo)
                     ((o)oo)  ((o)ooo)
                     ((oo)o)  ((oo)oo)
                     ((ooo))  ((ooo)o)
                     (o(o)o)  ((oooo))
                     (o(oo))  (o(o)oo)
                     (oo(o))  (o(oo)o)
                              (o(ooo))
                              (oo(o)o)
                              (oo(oo))
                              (ooo(o))

Andrew Howroyd, Table of n, a(n) for n = 1..1000

For equality we have A000891, unordered A185650.
Odd-indexed terms are A065097.
The unordered version is A358581.
The opposite is the same, unordered A358582.
The non-strict version is A358586, unordered A358583.
A000108 counts ordered rooted trees, unordered A000081.
A001263 counts ordered rooted trees by nodes and leaves, unordered A055277.
A080936 counts ordered rooted trees by nodes and height, unordered A034781.
A090181 counts ordered rooted trees by nodes and internals, unord. A358575.
A358590 counts square ordered trees, unordered A358589 (ranked by A358577).
Cf. A109129, A342507, A358371, A358579, A358580, A358584, A358588, A358590.

aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Count[#,{},{0,Infinity}]>Count[#,[_],{0,Infinity}]&]],{n,10}]

a(n) = if(n==1, 1, n--; (binomial(2*n,n)/(n+1) - if(n%2, binomial(n, (n-1)/2)^2 / n))/2) \\ Andrew Howroyd, Jan 13 2024

From Andrew Howroyd, Jan 13 2024: (Start)
a(n) = Sum_{k=1..floor((n-1)/2)} A001263(n-1, k) for n >= 2.
a(2*n) = (A000108(2*n-1) - A000891(n-1))/2 for n >= 1;
a(2*n+1) = A000108(2*n)/2 for n >= 1. (End)

a(16) onwards from Andrew Howroyd, Jan 13 2024

A358583 Number of rooted trees with n nodes, at least half of which are leaves.

Original entry on oeis.org

1, 1, 1, 3, 4, 13, 20, 67, 110, 383, 663, 2346, 4217, 15118, 27979, 101092, 191440, 695474, 1341974, 4893067, 9589567, 35055011, 69612556, 254923825, 511987473, 1877232869, 3807503552, 13972144807, 28585315026, 104955228432, 216381073935, 794739865822

Offset: 1

Gus Wiseman, Nov 23 2022

nonn

			The a(1) = 1 through a(6) = 13 trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)
                ((oo))  ((ooo))  ((oooo))
                (o(o))  (o(oo))  (o(ooo))
                        (oo(o))  (oo(oo))
                                 (ooo(o))
                                 (((ooo)))
                                 ((o)(oo))
                                 ((o(oo)))
                                 ((oo(o)))
                                 (o((oo)))
                                 (o(o)(o))
                                 (o(o(o)))
                                 (oo((o)))

Andrew Howroyd, Table of n, a(n) for n = 1..200

For equality we have A185650 aerated, ranked by A358578.
The strict case is A358581.
The opposite version is A358584, strict A358582.
The ordered version is A358586, strict A358585.
A000081 counts rooted trees, ordered A000108.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
A358589 counts square rooted trees, ranked by A358577, ordered A358590.
Cf. A000891, A034781, A065097, A109129, A342507, A358579, A358580, A358586.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{0,Infinity}]>=Count[#,[_],{0,Infinity}]&]],{n,1,10}]

\\ See A358584 for R(n).
seq(n) = {my(A=R(n)); vector(n, n, my(u=Vecrev(A[n]/y)); vecsum(u[(n-1)\2+1..#u]))} \\ Andrew Howroyd, Dec 31 2022

A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=floor((n-1)/2)+1..n} A055277(n, k). - Andrew Howroyd, Dec 31 2022

Terms a(19) and beyond from Andrew Howroyd, Dec 31 2022

A010370 a(n) = binomial(2n, n)^2 / (1-2n).

Original entry on oeis.org

1, -4, -12, -80, -700, -7056, -77616, -906048, -11042460, -139053200, -1796567344, -23696871744, -317933029232, -4326899214400, -59605244280000, -829705000377600, -11654762427179100, -165021757273414800, -2353088020380174000, -33764531705178120000

Offset: 0

Joe Keane (jgk(AT)jgk.org)

Expansion of hypergeometric function F(-1/2, 1/2; 1; 16*x).

Expansion of E(m)/(Pi/2) in powers of m/16 = (k/4)^2, where E(m) is the complete elliptic integral of the second kind evaluated at m. - Michael Somos, Mar 04 2003

			G.f. = 1 - 4*x - 12*x^2 - 80*x^3 - 700*x^4 - 7056*x^5 - 77616*x^6 - ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 591.
J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 8.

Robert Israel, Table of n, a(n) for n = 0..835
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Cf. A000891, A000894, A002420, A002894

seq(binomial(2*n,n)^2/(1-2*n), n=0..30); # Robert Israel, Jul 10 2017

CoefficientList[Series[EllipticE[16x]2/Pi, {x, 0, 20}], x]
Table[Binomial[2n,n]^2/(1-2n),{n,0,30}] (* Harvey P. Dale, Mar 07 2013 *)

{a(n) = binomial(2*n, n)^2 / (1 - 2*n)}; /* Michael Somos, Dec 13 2002 */

a(n) ~ -1/2*Pi^-1*n^-2*2^(4*n). [corrected by Vaclav Kotesovec, Oct 04 2019]
a(n) = -4 * A000891(n-1), n>0. - Michael Somos, Dec 13 2002
G.f.: F(-1/2, 1/2; 1; 16x) = E(16*x) / (Pi/2). a(n) = binomial(2*n, n)^2 / (1 - 2*n). - Michael Somos, Mar 04 2003
E.g.f.: Sum_{n>=0} a(n) * (x/2)^(2n)/(2n)! = I0^2*(1-2*x^2) +2*x*I0*I1 +2*x^2*I1^2 where I0=BesselI(0, x), I1=BesselI(1, x). - Michael Somos, Jun 22 2005
n^2*a(n) -4*(2*n-1)*(2*n-3)*a(n-1)=0. - R. J. Mathar, Feb 15 2013
0 = a(n)*(+1048576*a(n+2) + 2695168*a(n+3) - 989568*a(n+4) + 65340*a(n+5)) + a(n+1)*(-8192*a(n+2) - 99840*a(n+3) + 52652*a(n+4) - 4236*a(n+5)) + a(n+2)*(-128*a(n+2) + 280*a(n+3) - 484*a(n+4) + 57*a(n+5)) for all n in Z. - Michael Somos, Jan 21 2017
a(n) = A002894(n) - 8 * A000894(n-1). - Michael Somos, Jul 10 2017

Additional comments from Michael Somos, Dec 13 2002

A145601 a(n) is the number of walks from (0,0) to (0,2) that remain in the upper half-plane y >= 0 using 2*n unit steps either up (U), down (D), left (L) or right (R).

Original entry on oeis.org

1, 15, 189, 2352, 29700, 382239, 5010005, 66745536, 901995588, 12342120700, 170724392916, 2384209771200, 33577620944400, 476432168185575, 6805332732133125, 97790670976838400, 1412830549632694500

Offset: 1

Peter Bala, Oct 15 2008

Cf. A000891, which enumerates walks in the upper half-plane starting and finishing at the origin. See also A145600, A145602 and A145603. This sequence is the central column taken from triangle A145597, which enumerates walks in the upper half-plane starting at the origin and finishing on the horizontal line y = 2.

			a(2) = 15: the 15 walks from (0,0) to (0,2) of four steps are:
UUUD, UULR, UURL, UUDU, URUL, ULUR, URLU, ULRU,RUUL, LUUR,
RLUU, LRUU, RULU, LURU and UDUU.

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

A000891, A145597, A145600, A145602, A145603.

with(combinat):
a(n) = 3/(2*n+1)*binomial(2*n+1,n+2)*binomial(2*n+1,n-1);
seq(a(n),n = 1..19);

a(n) = 3/(2*n+1)*binomial(2*n+1,n+2)*binomial(2*n+1,n-1).

A145602 a(n) is the number of walks from (0,0) to (0,3) that remain in the upper half-plane y >= 0 using 2*n +1 unit steps either up (U), down (D), left (L) or right (R).

Original entry on oeis.org

1, 24, 392, 5760, 81675, 1145144, 16032016, 225059328, 3173688180, 44986664800, 641087516256, 9183622822400, 132211882468575, 1912322889603000, 27781440618420000, 405248874740582400, 5933888308457316900

Offset: 1

Peter Bala, Oct 15 2008

Cf. A000891, which enumerates walks in the upper half-plane starting and finishing at the origin. See also A145600, A145601 and A145603. This sequence is the central column taken from the triangle A145598, which enumerates walks in the upper half-plane starting at the origin and finishing on the horizontal line y = 3.

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

A000891, A145598, A145600, A145601, A145603.

with(combinat):
a(n) = 2/(n+1)*binomial(2*n+2,n+3)*binomial(2*n+2,n-1);
seq(a(n),n = 1..19);

a(n) = 2/(n+1)*binomial(2*n+2,n+3)*binomial(2*n+2,n-1).

A145603 a(n) is the number of walks from (0,0) to (0,4) that remain in the upper half-plane y >= 0 using 2*n +2 unit steps either up (U), down (D), left (L) or right (R).

Original entry on oeis.org

1, 35, 720, 12375, 196625, 3006003, 45048640, 668144880, 9859090500, 145173803500, 2136958387520, 31479019635375, 464342770607625, 6861343701121875, 101583106970400000, 1507019252941540800

Offset: 1

Peter Bala, Oct 15 2008

Cf. A000891, which enumerates walks in the upper half-plane starting and finishing at the origin. See also A145600, A145601 and A145602. This sequence is the central column taken from the triangle A145599, which enumerates walks in the upper half-plane starting at the origin and finishing on the horizontal line y = 4.

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

A000891, A145599, A145600, A145601, A145602.

with(combinat):
a(n) = 5/(2*n+3)*binomial(2*n+3,n+4)*binomial(2*n+3,n-1);
seq(a(n),n = 1..19);

a(n) = 5/(2*n+3)*binomial(2*n+3,n+4)*binomial(2*n+3,n-1).

G.f.: x*hypergeom([5/2, 3, 3, 7/2], [1, 6, 6], 16*x). - Stefano Spezia, Aug 26 2025

A123617 Central terms of triangle A123610: a(n) = A123610(2*n,n).

Original entry on oeis.org

1, 2, 10, 68, 618, 6352, 71188, 841332, 10352618, 131328068, 1706742160, 22619741212, 304685855700, 4160480013848, 57476485976388, 802048167035968, 11290551106506218, 160168176177137896, 2287724464324213972

Offset: 0

Paul D. Hanna, Oct 03 2006

nonn

Related sequences: A123610(2n+1,n) = A000891(n); A123610(2n+2,n) = A123618(n); A123610(2n+2,n)/(n+1) = A123619(n).

G. C. Greubel, Table of n, a(n) for n = 0..830

Cf. A123610 (triangle); A000891, A123618.

T[, 0] = 1; T[n, k_] := 1/n DivisorSum[n, If[GCD[k, #] == #, EulerPhi[#]*Binomial[n/#, k/#]^2, 0] &];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* A123610 *)
Table[T[2*n, n], {n, 0, 50}] (* A123617 *)
Table[T[2*n + 2, n], {n, 0, 50}] (* A123618 *)
Table[T[2*n + 2,n]/(n+1), {n, 0, 50}] (* A123619 *)
(* G. C. Greubel, Oct 26 2017 *)

{a(n)=if(n==0,1,(1/2/n)*sumdiv(2*n,d,if(gcd(n,d)==d, eulerphi(d)*binomial(2*n/d,n/d)^2,0)))}

A123618 a(n) = A123610(2*n+2,n).

Original entry on oeis.org

1, 4, 39, 392, 4420, 52272, 644231, 8179600, 106376580, 1410528080, 19006875580, 259613952864, 3587352778256, 50068405195200, 704925148185495, 10001318622631200, 142866058397606500, 2053248549639210000

Offset: 0

Paul D. Hanna, Oct 03 2006

nonn

Related sequences: A123610(2n,n) = A123617(n); A123610(2n+1,n) = A000891(n); A123610(2n+2,n)/(n+1) = A123619(n). a(n) is divisible by (n+1): a(n)/(n+1) = A123619(n).

G. C. Greubel, Table of n, a(n) for n = 0..830

Cf. A123610 (triangle); A123617, A000891, A123619.

T[, 0] = 1; T[n, k_] := 1/n DivisorSum[n, If[GCD[k, #] == #, EulerPhi[#]*Binomial[n/#, k/#]^2, 0] &];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* A123610 *)
Table[T[2*n, n], {n, 0, 50}] (* A123617 *)
Table[T[2*n + 2, n], {n, 0, 50}] (* A123618 *)
Table[T[2*n + 2,n]/(n+1), {n, 0, 50}] (* A123619 *)
(* G. C. Greubel, Oct 26 2017 *)

{a(n)=if(n==0,1,(1/(2*n+2))*sumdiv(2*n+2,d,if(gcd(n,d)==d, eulerphi(d)*binomial((2*n+2)/d,n/d)^2,0)))}

A248045 (2(n-1))! (2n-1)! / (n (n-1)!^3).

Original entry on oeis.org

1, 6, 120, 4200, 211680, 13970880, 1141620480, 111307996800, 12614906304000, 1629845894476800, 236475822507724800, 38072607423743692800, 6735922851893114880000, 1299070835722243584000000, 271245990498804460339200000, 60962536364606302461235200000

Offset: 1

Reinhard Zumkeller, Sep 30 2014

nonn

Central terms in triangles of Lah numbers: a(n) = - A008297(2*n-1,n) = A105278(2*n-1,n) = A000891(n-1)*A000142(n) = A000894(n-1)*A000142(n-1).

a(n) = n * A204515(n-1). - Reinhard Zumkeller, Oct 19 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..250

Cf. A000142, A000891, A000894, A008297, A105278, A204515.

Cf. A187535 (Central Lah numbers).

Haskell
```
a248045 n = a000891 (n - 1) * a000142 n
```

n*a(n) = 4*(2*n-1)*(2*n-3)*a(n-1). - R. J. Mathar, Oct 07 2014

cp's OEIS Frontend

A358582 Number of rooted trees with n nodes, most of which are not leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358585 Number of ordered rooted trees with n nodes, most of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A358583 Number of rooted trees with n nodes, at least half of which are leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A010370 a(n) = binomial(2*n, n)^2 / (1-2*n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A145601 a(n) is the number of walks from (0,0) to (0,2) that remain in the upper half-plane y >= 0 using 2*n unit steps either up (U), down (D), left (L) or right (R).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A145602 a(n) is the number of walks from (0,0) to (0,3) that remain in the upper half-plane y >= 0 using 2*n +1 unit steps either up (U), down (D), left (L) or right (R).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A145603 a(n) is the number of walks from (0,0) to (0,4) that remain in the upper half-plane y >= 0 using 2*n +2 unit steps either up (U), down (D), left (L) or right (R).

Views

Author

Keywords

Comments

Links

Crossrefs

A010370 a(n) = binomial(2n, n)^2 / (1-2n).

A248045 (2(n-1))! (2n-1)! / (n (n-1)!^3).