A317097 - OEIS

%I #12 Aug 28 2018 19:55:19

%S 1,1,2,4,9,20,46,106,248,583,1393,3343,8111,19801,48719,120489,299787,

%T 749258,1881216,4741340,11993672,30436507,77471471,197726053,

%U 505917729,1297471092,3334630086,8587369072,22155278381,57259037225,148222036272,384272253397

%N Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

%C There can be more than two branches as long as there are not three distinct branches.

%H Andrew Howroyd, <a href="/A317097/b317097.txt">Table of n, a(n) for n = 1..200</a>

%e The a(5) = 9 trees:

%e   ((((o))))

%e   (((oo)))

%e   ((o(o)))

%e   ((ooo))

%e   (o((o)))

%e   (o(oo))

%e   ((o)(o))

%e   (oo(o))

%e   (oooo)

%t semisameQ[u_]:=Length[Union[u]]<=2;

%t nms[n_]:=nms[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,IntegerPartitions[n-1]}]];

%t Table[Length[nms[n]],{n,10}]

%o (PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=1, n-1, v[n+1]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ _Andrew Howroyd_, Aug 28 2018

%Y Cf. A000081, A000598, A001190, A003238, A055277, A111299, A292050, A298204, A301344, A317098.

%K nonn

%O 1,3

%A _Gus Wiseman_, Aug 01 2018

%E Terms a(20) and beyond from _Andrew Howroyd_, Aug 28 2018