login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A320268
Number of unlabeled series-reduced rooted trees with n nodes where the non-leaf branches directly under any given node are all equal.
8
1, 0, 1, 1, 2, 3, 6, 9, 16, 26, 44, 70, 119, 189, 314, 506, 830, 1336, 2186, 3522, 5737, 9266, 15047, 24313, 39444, 63759, 103322, 167098, 270616, 437714, 708676, 1146390, 1855582, 3002017, 4858429, 7860454, 12720310, 20580764, 33303260, 53884144, 87190964
OFFSET
1,5
COMMENTS
This is a weaker condition than achirality (cf. A167865).
A rooted tree is series-reduced if every non-leaf node has at least two branches.
LINKS
FORMULA
a(1) = 1; a(2) = 0; a(n > 2) = 1 + Sum_{k = 2..n-2} floor((n-1)/k) * a(k).
EXAMPLE
The a(3) = 1 through a(8) = 9 rooted trees:
(oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
(o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))
(oo(oo)) (oo(ooo)) (oo(oooo))
(ooo(oo)) (ooo(ooo))
((oo)(oo)) (oooo(oo))
(o(o(oo))) (o(o(ooo)))
(o(oo)(oo))
(o(oo(oo)))
(oo(o(oo)))
MATHEMATICA
saum[n_]:=Sum[If[DeleteCases[ptn, 1]=={}, 1, saum[DeleteCases[ptn, 1][[1]]]], {ptn, Select[IntegerPartitions[n-1], And[Length[#]!=1, SameQ@@DeleteCases[#, 1]]&]}];
Array[saum, 20]
PROG
(PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=3, n, v[n] = 1 + sum(k=2, n-2, (n-1)\k*v[k])); v} \\ Andrew Howroyd, Oct 26 2018
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 08 2018
STATUS
approved