login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2. 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

LINKS

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

EXAMPLE

The a(5) = 9 trees:

  ((((o))))

  (((oo)))

  ((o(o)))

  ((ooo))

  (o((o)))

  (o(oo))

  ((o)(o))

  (oo(o))

  (oooo)

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}]

PROG

(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

CROSSREFS

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

Sequence in context: A005908 A206119 A085748 * A252354 A052806 A329672

Adjacent sequences:  A317094 A317095 A317096 * A317098 A317099 A317100

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 01 2018

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 21:55 EDT 2021. Contains 345080 sequences. (Running on oeis4.)