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

1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1393, 3343, 8111, 19801, 48719, 120489, 299787, 749258, 1881216, 4741340, 11993672, 30436507, 77471471, 197726053, 505917729, 1297471092, 3334630086, 8587369072, 22155278381, 57259037225, 148222036272, 384272253397

Offset: 1

Author

Gus Wiseman, Aug 01 2018

Keywords

• nonn

Comments

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

Examples

			The a(5) = 9 trees:
  ((((o))))
  (((oo)))
  ((o(o)))
  ((ooo))
  (o((o)))
  (o(oo))
  ((o)(o))
  (oo(o))
  (oooo)
		

Links

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

Crossrefs

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

Programs

Mathematica

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,IntegerPartitions[n-1]}]];
Table[Length[nms[n]],{n,10}]

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

Extensions

Terms a(20) and beyond from Andrew Howroyd, Aug 28 2018