login
A358585
Number of ordered rooted trees with n nodes, most of which are leaves.
9
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
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).
Sequence in context: A077411 A085016 A067690 * A196181 A177182 A061809
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 24 2022
EXTENSIONS
a(16) onwards from Andrew Howroyd, Jan 13 2024
STATUS
approved