cp's OEIS Frontend

A358584 Number of rooted trees with n nodes, at most half of which are leaves.

%I A358584 #11 Dec 30 2022 21:38:42
%S A358584 0,1,1,3,5,15,28,87,176,550,1179,3688,8269,25804,59832,186190,443407,
%T A358584 1375388,3346702,10348509,25632265,79020511,198670299,610740694,
%U A358584 1555187172,4768244803,12276230777,37546795678,97601239282,297831479850,780790439063,2377538260547
%N A358584 Number of rooted trees with n nodes, at most half of which are leaves.
%H A358584 Andrew Howroyd, <a href="/A358584/b358584.txt">Table of n, a(n) for n = 1..200</a>
%F A358584 A358581(n) + A358584(n) = A000081(n).
%F A358584 A358582(n) + A358583(n) = A000081(n).
%F A358584 a(n) = Sum_{k=1..floor(n/2)} A055277(n, k). - _Andrew Howroyd_, Dec 30 2022
%e A358584 The a(2) = 1 through a(6) = 15 trees:
%e A358584   (o)  ((o))  ((oo))   (((oo)))   (((ooo)))
%e A358584               (o(o))   ((o)(o))   ((o)(oo))
%e A358584               (((o)))  ((o(o)))   ((o(oo)))
%e A358584                        (o((o)))   ((oo(o)))
%e A358584                        ((((o))))  (o((oo)))
%e A358584                                   (o(o)(o))
%e A358584                                   (o(o(o)))
%e A358584                                   (oo((o)))
%e A358584                                   ((((oo))))
%e A358584                                   (((o)(o)))
%e A358584                                   (((o(o))))
%e A358584                                   ((o)((o)))
%e A358584                                   ((o((o))))
%e A358584                                   (o(((o))))
%e A358584                                   (((((o)))))
%t A358584 art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
%t A358584 Table[Length[Select[art[n],Count[#,{},{0,Infinity}]<=Count[#,_[__],{0,Infinity}]&]],{n,0,10}]
%o A358584 (PARI)
%o A358584 R(n) = {my(A = O(x)); for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + O(x*x^(j\i)), x, x^i), y, y^i) ) ))); Vec(A)};
%o A358584 seq(n) = {my(A=R(n)); vector(n, n, vecsum(Vecrev(A[n]/y)[1..n\2]))} \\ _Andrew Howroyd_, Dec 30 2022
%Y A358584 For equality we have A185650 aerated, ranked by A358578.
%Y A358584 The complement is A358581.
%Y A358584 The strict case is A358582.
%Y A358584 The opposite version is A358583.
%Y A358584 A000081 counts rooted trees, ordered A000108.
%Y A358584 A055277 counts rooted trees by nodes and leaves, ordered A001263.
%Y A358584 A358575 counts rooted trees by nodes and internal nodes, ordered A090181.
%Y A358584 A358589 counts square trees, ranked by A358577, ordered A358590.
%Y A358584 Cf. A000891, A034781, A065097, A109129, A342507, A358579, A358580, A358585, A358586, A358591.
%K A358584 nonn
%O A358584 1,4
%A A358584 _Gus Wiseman_, Nov 23 2022
%E A358584 Terms a(19) and beyond from _Andrew Howroyd_, Dec 30 2022