login
Number of unlabeled series-reduced rooted trees with n nodes where the non-leaf branches directly under any given node are all equal.
8

%I #12 Jan 22 2023 18:17:36

%S 1,0,1,1,2,3,6,9,16,26,44,70,119,189,314,506,830,1336,2186,3522,5737,

%T 9266,15047,24313,39444,63759,103322,167098,270616,437714,708676,

%U 1146390,1855582,3002017,4858429,7860454,12720310,20580764,33303260,53884144,87190964

%N Number of unlabeled series-reduced rooted trees with n nodes where the non-leaf branches directly under any given node are all equal.

%C This is a weaker condition than achirality (cf. A167865).

%C A rooted tree is series-reduced if every non-leaf node has at least two branches.

%H Andrew Howroyd, <a href="/A320268/b320268.txt">Table of n, a(n) for n = 1..500</a>

%F a(1) = 1; a(2) = 0; a(n > 2) = 1 + Sum_{k = 2..n-2} floor((n-1)/k) * a(k).

%e The a(3) = 1 through a(8) = 9 rooted trees:

%e (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)

%e (o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))

%e (oo(oo)) (oo(ooo)) (oo(oooo))

%e (ooo(oo)) (ooo(ooo))

%e ((oo)(oo)) (oooo(oo))

%e (o(o(oo))) (o(o(ooo)))

%e (o(oo)(oo))

%e (o(oo(oo)))

%e (oo(o(oo)))

%t saum[n_]:=Sum[If[DeleteCases[ptn,1]=={},1,saum[DeleteCases[ptn,1][[1]]]],{ptn,Select[IntegerPartitions[n-1],And[Length[#]!=1,SameQ@@DeleteCases[#,1]]&]}];

%t Array[saum,20]

%o (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

%Y Cf. A001678, A002541, A003238, A010766, A070776, A014668, A126656, A167865, A317099, A317100, A317712, A320222, A320226, A320269.

%K nonn

%O 1,5

%A _Gus Wiseman_, Oct 08 2018