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

1, 0, 1, 1, 4, 5, 20, 28, 110, 169, 663, 1078, 4217, 7169, 27979, 49191, 191440, 345771, 1341974, 2477719, 9589567, 18034670, 69612556, 132984290, 511987473, 991391707, 3807503552, 7460270591, 28585315026, 56595367747, 216381073935, 432396092153

Offset

1,5

Links

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

Formula

A358581(n) + A358584(n) = A000081(n).

A358582(n) + A358583(n) = A000081(n).

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

Example

The a(1) = 1 through a(7) = 20 trees:
  o  .  (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)
                     ((ooo))  ((oooo))  ((ooooo))
                     (o(oo))  (o(ooo))  (o(oooo))
                     (oo(o))  (oo(oo))  (oo(ooo))
                              (ooo(o))  (ooo(oo))
                                        (oooo(o))
                                        (((oooo)))
                                        ((o)(ooo))
                                        ((o(ooo)))
                                        ((oo)(oo))
                                        ((oo(oo)))
                                        ((ooo(o)))
                                        (o((ooo)))
                                        (o(o)(oo))
                                        (o(o(oo)))
                                        (o(oo(o)))
                                        (oo((oo)))
                                        (oo(o)(o))
                                        (oo(o(o)))
                                        (ooo((o)))

Mathematica

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, 0, 10}]

Prog

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

Crossrefs

For equality we have A185650 aerated, ranked by A358578.

The opposite version is A358582, non-strict A358584.

The non-strict version is A358583.

The ordered version is A358585, odd-indexed terms A065097.

A000081 counts rooted trees, ordered A000108.

A034781 counts rooted trees by nodes and height, ordered A080936.

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, A109129, A342507, A358579, A358580, A358586, A358591.

Sequence in context: A133632 A163141 A182584 * A240860 A059182 A027958

Adjacent sequences: A358578 A358579 A358580 * A358582 A358583 A358584

Keyword

nonn

Author

Gus Wiseman, Nov 23 2022

Extensions

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

Status

approved