|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=1..floor((n-1)/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(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
|
The opposite is the same, unordered A358582.
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
|
|
|
|