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

0, 0, 0, 0, 1, 4, 14, 41, 111, 282, 688, 1627, 3761, 8540, 19122, 42333, 92851, 202078, 436916, 939359, 2009781, 4281696, 9087670, 19223905, 40544951, 85284194, 178956984, 374691171, 782936761, 1632982372, 3400182458, 7068800357, 14674471611, 30422685030

Offset

1,6

Links

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

Formula

Conjectures from Chai Wah Wu, Apr 15 2024: (Start)

a(n) = 5*a(n-1) - 7*a(n-2) - a(n-3) + 8*a(n-4) - 4*a(n-5) for n > 7.

G.f.: x^5*(x^2 - x + 1)/((x - 1)^2*(x + 1)*(2*x - 1)^2). (End)

Example

The a(5) = 1 through a(7) = 14 trees:
  ((o)(o))  ((o)(oo))   ((o)(ooo))
            (o(o)(o))   ((oo)(oo))
            (((o)(o)))  (o(o)(oo))
            ((o)((o)))  (oo(o)(o))
                        (((o))(oo))
                        (((o)(oo)))
                        ((o)((oo)))
                        ((o)(o(o)))
                        ((o(o)(o)))
                        (o((o)(o)))
                        (o(o)((o)))
                        ((((o)(o))))
                        (((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) \\ Needs R(n, f) defined in A358589.
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 A185650 aerated, ranked by A358578.

These trees are ranked by A358576.

The ordered version is A358588.

Square trees are counted by A358589, ranked by A358577, ordered 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, A342507, A358552, A358581-A358584, A358591.

Sequence in context: A196480 A326008 A196713 * A237853 A132357 A262875

Adjacent sequences: A358584 A358585 A358586 * A358588 A358589 A358590

Keyword

nonn,changed

Author

Gus Wiseman, Nov 23 2022

Extensions

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

Status

approved