login
A358588
Number of n-node ordered rooted trees of height equal to the number of internal (non-leaf) nodes.
13
0, 0, 0, 0, 1, 8, 41, 171, 633, 2171, 7070, 22195, 67830, 203130, 598806, 1743258, 5023711, 14356226, 40737383, 114904941, 322432215, 900707165, 2506181060, 6948996085, 19207795836, 52944197508, 145567226556, 399314965956, 1093107693133, 2986640695436
OFFSET
1,6
LINKS
FORMULA
Conjectures from Chai Wah Wu, Apr 14 2024: (Start)
a(n) = 9*a(n-1) - 32*a(n-2) + 58*a(n-3) - 58*a(n-4) + 32*a(n-5) - 9*a(n-6) + a(n-7) for n > 7.
G.f.: x^5*(-x^2 + x - 1)/((x - 1)^3*(x^2 - 3*x + 1)^2). (End)
EXAMPLE
The a(5) = 1 and a(6) = 8 ordered trees:
((o)(o)) ((o)(o)o)
((o)(oo))
((o)o(o))
((oo)(o))
(o(o)(o))
(((o))(o))
(((o)(o)))
((o)((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}]==Depth[#]-1&]], {n, 1, 10}]
PROG
(PARI) \\ Needs R(n, f) defined in A358590.
seq(n) = {Vec(R(n, (h, p)->polcoef(subst(p, x, x/y), -h, y)), -n)} \\ Andrew Howroyd, Jan 01 2023
CROSSREFS
For leaves instead of height we have A000891, unordered A185650 aerated.
The unordered version is A358587, ranked by A358576.
For leaves instead of internal nodes we have A358590, unordered A358589.
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.
Sequence in context: A342034 A304160 A133106 * A272843 A268997 A078797
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 25 2022
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Jan 01 2023
STATUS
approved