cp's OEIS Frontend

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

%I A358587 #14 Apr 15 2024 04:56:44
%S A358587 0,0,0,0,1,4,14,41,111,282,688,1627,3761,8540,19122,42333,92851,
%T A358587 202078,436916,939359,2009781,4281696,9087670,19223905,40544951,
%U A358587 85284194,178956984,374691171,782936761,1632982372,3400182458,7068800357,14674471611,30422685030
%N A358587 Number of n-node rooted trees of height equal to the number of internal (non-leaf) nodes.
%H A358587 Andrew Howroyd, <a href="/A358587/b358587.txt">Table of n, a(n) for n = 1..200</a>
%F A358587 Conjectures from _Chai Wah Wu_, Apr 15 2024: (Start)
%F A358587 a(n) = 5*a(n-1) - 7*a(n-2) - a(n-3) + 8*a(n-4) - 4*a(n-5) for n > 7.
%F A358587 G.f.: x^5*(x^2 - x + 1)/((x - 1)^2*(x + 1)*(2*x - 1)^2). (End)
%e A358587 The a(5) = 1 through a(7) = 14 trees:
%e A358587   ((o)(o))  ((o)(oo))   ((o)(ooo))
%e A358587             (o(o)(o))   ((oo)(oo))
%e A358587             (((o)(o)))  (o(o)(oo))
%e A358587             ((o)((o)))  (oo(o)(o))
%e A358587                         (((o))(oo))
%e A358587                         (((o)(oo)))
%e A358587                         ((o)((oo)))
%e A358587                         ((o)(o(o)))
%e A358587                         ((o(o)(o)))
%e A358587                         (o((o)(o)))
%e A358587                         (o(o)((o)))
%e A358587                         ((((o)(o))))
%e A358587                         (((o)((o))))
%e A358587                         ((o)(((o))))
%t A358587 art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
%t A358587 Table[Length[Select[art[n],Count[#,_[__],{0,Infinity}]==Depth[#]-1&]],{n,1,10}]
%o A358587 (PARI) \\ Needs R(n,f) defined in A358589.
%o A358587 seq(n) = {Vec(R(n, (h,p)->polcoef(subst(p, x, x/y), -h, y)), -n)} \\ _Andrew Howroyd_, Jan 01 2023
%Y A358587 For leaves instead of height we have A185650 aerated, ranked by A358578.
%Y A358587 These trees are ranked by A358576.
%Y A358587 The ordered version is A358588.
%Y A358587 Square trees are counted by A358589, ranked by A358577, ordered A358590.
%Y A358587 A000081 counts rooted trees, ordered A000108.
%Y A358587 A034781 counts rooted trees by nodes and height, ordered A080936.
%Y A358587 A055277 counts rooted trees by nodes and leaves, ordered A001263.
%Y A358587 A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
%Y A358587 Cf. A000891, A065097, A342507, A358552, A358581-A358584, A358591.
%K A358587 nonn
%O A358587 1,6
%A A358587 _Gus Wiseman_, Nov 23 2022
%E A358587 Terms a(19) and beyond from _Andrew Howroyd_, Jan 01 2023