|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=1..floor(n/2)} A001263(n-1, k) for n >= 2.
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
|
Odd-indexed terms appear to be A065097.
The opposite is the same, unordered A358584.
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|