A358728 Number of n-node rooted trees whose node-height is less than their number of leaves.

0, 0, 0, 1, 1, 5, 10, 30, 76, 219, 582, 1662, 4614, 13080, 36903, 105098, 298689, 852734, 2434660, 6964349, 19931147, 57100177, 163647811, 469290004, 1346225668, 3863239150, 11089085961, 31838349956, 91430943515, 262615909503, 754439588007, 2167711283560

Offset: 1

Author

Gus Wiseman, Nov 29 2022

Keywords

• nonn

Comments

Node-height is the number of nodes in the longest path from root to leaf.

Examples

			The a(1) = 0 through a(7) = 10 trees:
  .  .  .  (ooo)  (oooo)  (ooooo)   (oooooo)
                          ((oooo))  ((ooooo))
                          (o(ooo))  (o(oooo))
                          (oo(oo))  (oo(ooo))
                          (ooo(o))  (ooo(oo))
                                    (oooo(o))
                                    ((o)(ooo))
                                    ((oo)(oo))
                                    (o(o)(oo))
                                    (oo(o)(o))
		

Links

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

Crossrefs

These trees are ranked by A358727.

For internals instead of node-height we have A358581, ordered A358585.

The case of equality is A358589 (square trees), ranked by A358577.

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.

Cf. A109082, A109129, A185650, A358552, A358582-A358586, A358587, A358591.

Programs

Mathematica

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Depth[#]-1
				

PARI

\\ Needs R(n,f) defined in A358589.
seq(n) = {Vec(R(n, (h,p)->sum(j=h+1, n-1, polcoef(p,j,y))), -n)} \\ Andrew Howroyd, Jan 01 2023

Extensions

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