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

Author

Gus Wiseman, Nov 25 2022

Keywords

• nonn

Comments

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

Examples

			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))
		

Links

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

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.

Programs

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}]

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

Extensions

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