A358590 Number of square ordered rooted trees with n nodes.

1, 0, 1, 0, 6, 5, 36, 84, 309, 890, 3163, 9835, 32979, 108252, 360696, 1192410, 3984552, 13276769, 44371368, 148402665, 497072593, 1665557619, 5586863093, 18750662066, 62968243731, 211565969511, 711187790166, 2391640404772, 8045964959333, 27077856222546

Offset

1,5

Comments

We say that a tree is square if it has the same height as number of leaves.

Links

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

Example

The a(1) = 1 through a(6) = 5 ordered trees:
  o  .  (oo)  .  ((o)oo)  ((o)(o)o)
                 ((oo)o)  ((o)(oo))
                 ((ooo))  ((o)o(o))
                 (o(o)o)  ((oo)(o))
                 (o(oo))  (o(o)(o))
                 (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}]==Depth[#]-1&]], {n, 1, 10}]

Prog

(PARI) \\ R(n, f) enumerates trees by height(h), nodes(x) and leaves(y).
R(n, f) = {my(A=O(x*x^n), Z=0); for(h=1, n, my(p = A); A = x*(y - 1  + 1/(1 - A + O(x^n))); Z += f(h, A-p)); Z}
seq(n) = {Vec(R(n, (h, p)->polcoef(p, h, y)), -n)} \\ Andrew Howroyd, Jan 01 2023

Crossrefs

For internals instead of height we have A000891, unordered A185650 aerated.

For internals instead of leaves we have A358588, unordered A358587.

The unordered version is A358589, ranked by A358577.

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, A109129, A358371, A358552, A358579, A358586.

Sequence in context: A283980 A288211 A038259 * A393349 A302750 A268000

Adjacent sequences: A358587 A358588 A358589 * A358591 A358592 A358593

Keyword

nonn

Author

Gus Wiseman, Nov 25 2022

Extensions

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

Status

approved