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

Author

Gus Wiseman, Nov 24 2022

Keywords

• nonn

Examples

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

Links

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

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.

Programs

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

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

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)

Extensions

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