A358588 Number of n-node ordered rooted trees of height equal to the number of internal (non-leaf) nodes.

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

Andrew Howroyd, Table of n, a(n) for n = 1..200

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.

Cf. A065097, A342507, A358552, A358371, A358578, A358579, A358586, A358591.

Sequence in context: A342034 A304160 A133106 * A272843 A268997 A078797

Adjacent sequences: A358585 A358586 A358587 * A358589 A358590 A358591

Keyword

nonn,changed

Author

Gus Wiseman, Nov 25 2022

Extensions

Terms a(16) and beyond from Andrew Howroyd, Jan 01 2023

Status

approved