login
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
OFFSET
1,3
COMMENTS
There can be more than two branches as long as there are not three distinct branches.
LINKS
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 01 2018
EXTENSIONS
Terms a(20) and beyond from Andrew Howroyd, Aug 28 2018
STATUS
approved