login
A358583
Number of rooted trees with n nodes, at least half of which are leaves.
8
1, 1, 1, 3, 4, 13, 20, 67, 110, 383, 663, 2346, 4217, 15118, 27979, 101092, 191440, 695474, 1341974, 4893067, 9589567, 35055011, 69612556, 254923825, 511987473, 1877232869, 3807503552, 13972144807, 28585315026, 104955228432, 216381073935, 794739865822
OFFSET
1,4
LINKS
FORMULA
A358581(n) + A358584(n) = A000081(n).
A358582(n) + A358583(n) = A000081(n).
a(n) = Sum_{k=floor((n-1)/2)+1..n} A055277(n, k). - Andrew Howroyd, Dec 31 2022
EXAMPLE
The a(1) = 1 through a(6) = 13 trees:
o (o) (oo) (ooo) (oooo) (ooooo)
((oo)) ((ooo)) ((oooo))
(o(o)) (o(oo)) (o(ooo))
(oo(o)) (oo(oo))
(ooo(o))
(((ooo)))
((o)(oo))
((o(oo)))
((oo(o)))
(o((oo)))
(o(o)(o))
(o(o(o)))
(oo((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}]>=Count[#, _[__], {0, Infinity}]&]], {n, 1, 10}]
PROG
(PARI) \\ See A358584 for R(n).
seq(n) = {my(A=R(n)); vector(n, n, my(u=Vecrev(A[n]/y)); vecsum(u[(n-1)\2+1..#u]))} \\ Andrew Howroyd, Dec 31 2022
CROSSREFS
For equality we have A185650 aerated, ranked by A358578.
The strict case is A358581.
The opposite version is A358584, strict A358582.
The ordered version is A358586, strict A358585.
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 rooted trees, ranked by A358577, ordered A358590.
Sequence in context: A302392 A293941 A182691 * A026700 A187775 A377310
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 23 2022
EXTENSIONS
Terms a(19) and beyond from Andrew Howroyd, Dec 31 2022
STATUS
approved