A358589 Number of square rooted trees with n nodes.

1, 0, 1, 0, 3, 2, 11, 17, 55, 107, 317, 720, 1938, 4803, 12707, 32311, 85168, 220879, 581112, 1522095, 4014186, 10568936, 27934075, 73826753, 195497427, 517927859, 1373858931, 3646158317, 9684878325, 25737819213, 68439951884, 182070121870, 484583900955, 1290213371950

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(7) = 11 trees:
  o  .  (oo)  .  ((ooo))  ((o)(oo))  (((oooo)))
                 (o(oo))  (o(o)(o))  ((o(ooo)))
                 (oo(o))             ((oo(oo)))
                                     ((ooo(o)))
                                     (o((ooo)))
                                     (o(o(oo)))
                                     (o(oo(o)))
                                     (oo((oo)))
                                     (oo(o(o)))
                                     (ooo((o)))
                                     ((o)(o)(o))

Mathematica

art[n_]:=If[n==1, {{}}, Join@@Table[Select[Tuples[art/@c], OrderedQ], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[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  + exp( sum(i=1, n-1, 1/i * subst( subst( A + O(x*x^((n-1)\i)), x, x^i), y, y^i) ) )); 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 A185650 aerated, ranked by A358578.

These trees are ranked by A358577.

For internals instead of leaves we have A358587, ranked by A358576.

The ordered version is A358590.

A000081 counts rooted trees, ordered A000108.

A034781 counts rooted trees by nodes and height, ordered A080936.

A055277 counts rooted trees by nodes and leaves, ordered A001263.

A358575 counts rooted trees by nodes and internal nodes, ordered A090181.

Cf. A000891, A065097, A109129, A358552, A358588, A358591.

Sequence in context: A087956 A116391 A305491 * A087629 A254214 A362995

Adjacent sequences: A358586 A358587 A358588 * A358590 A358591 A358592

Keyword

nonn

Author

Gus Wiseman, Nov 23 2022

Extensions

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

Status

approved