login
A358587
Number of n-node rooted trees of height equal to the number of internal (non-leaf) nodes.
18
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
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.
Sequence in context: A326008 A196713 A375406 * A237853 A132357 A262875
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 23 2022
EXTENSIONS
Terms a(19) and beyond from Andrew Howroyd, Jan 01 2023
STATUS
approved