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

1, 1, 1, 4, 7, 31, 66, 302, 715, 3313, 8398, 39095, 104006, 484706, 1337220, 6227730, 17678835, 82204045, 238819350, 1108202513, 3282060210, 15195242478, 45741281820, 211271435479, 644952073662, 2971835602526, 9183676536076, 42217430993002, 131873975875180, 604834233372884

Offset: 1

Author

Gus Wiseman, Nov 24 2022

Keywords

• nonn

Examples

			The a(1) = 1 through a(5) = 7 ordered trees:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                ((oo))  ((oo)o)
                (o(o))  ((ooo))
                        (o(o)o)
                        (o(oo))
                        (oo(o))
		

Links

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

Crossrefs

For equality we have A000891, unordered A185650.

Odd-indexed terms appear to be A065097.

The unordered version is A358583.

The opposite is the same, unordered A358584.

The strict case is A358585, unordered A358581.

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, A358582, A358584, A358588.

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,1,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/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