login
A358586
Number of ordered rooted trees with n nodes, at least half of which are leaves.
17
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,4
LINKS
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)
EXAMPLE
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))
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}]
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 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).
Sequence in context: A047004 A030689 A080871 * A102666 A123801 A359706
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 24 2022
EXTENSIONS
a(16) onwards from Andrew Howroyd, Jan 13 2024
STATUS
approved