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

0, 1, 1, 3, 5, 15, 28, 87, 176, 550, 1179, 3688, 8269, 25804, 59832, 186190, 443407, 1375388, 3346702, 10348509, 25632265, 79020511, 198670299, 610740694, 1555187172, 4768244803, 12276230777, 37546795678, 97601239282, 297831479850, 780790439063, 2377538260547

Offset: 1

Author

Gus Wiseman, Nov 23 2022

Keywords

• nonn

Examples

			The a(2) = 1 through a(6) = 15 trees:
  (o)  ((o))  ((oo))   (((oo)))   (((ooo)))
              (o(o))   ((o)(o))   ((o)(oo))
              (((o)))  ((o(o)))   ((o(oo)))
                       (o((o)))   ((oo(o)))
                       ((((o))))  (o((oo)))
                                  (o(o)(o))
                                  (o(o(o)))
                                  (oo((o)))
                                  ((((oo))))
                                  (((o)(o)))
                                  (((o(o))))
                                  ((o)((o)))
                                  ((o((o))))
                                  (o(((o))))
                                  (((((o)))))
		

Links

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

Crossrefs

For equality we have A185650 aerated, ranked by A358578.

The complement is A358581.

The strict case is A358582.

The opposite version is A358583.

A000081 counts rooted trees, ordered A000108.

A055277 counts rooted trees by nodes and leaves, ordered A001263.

A358575 counts rooted trees by nodes and internal nodes, ordered A090181.

A358589 counts square trees, ranked by A358577, ordered A358590.

Cf. A000891, A034781, A065097, A109129, A342507, A358579, A358580, A358585, A358586, 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],Count[#,{},{0,Infinity}]<=Count[#,[_],{0,Infinity}]&]],{n,0,10}]

PARI

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)};
seq(n) = {my(A=R(n)); vector(n, n, vecsum(Vecrev(A[n]/y)[1..n\2]))} \\ Andrew Howroyd, Dec 30 2022

Formula

A358581(n) + A358584(n) = A000081(n).

A358582(n) + A358583(n) = A000081(n).

a(n) = Sum_{k=1..floor(n/2)} A055277(n, k). - Andrew Howroyd, Dec 30 2022

Extensions

Terms a(19) and beyond from Andrew Howroyd, Dec 30 2022