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

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

Links

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

Formula

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)

Example

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

Mathematica

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}]

Prog

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

Crossrefs

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.

Sequence in context: A077411 A085016 A067690 * A196181 A177182 A061809

Adjacent sequences: A358582 A358583 A358584 * A358586 A358587 A358588

Keyword

nonn

Author

Gus Wiseman, Nov 24 2022

Extensions

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

Status

approved