login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A298478 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are different. 3
1, 1, 1, 3, 3, 5, 13, 15, 23, 34, 95, 106, 176, 241, 374, 942, 1129, 1760, 2515, 3711, 5136, 12857, 14911, 23814, 33002, 49141, 65798, 97056, 209707, 255042, 389725, 545290, 790344, 1071010, 1525919, 2043953, 4272124, 5110583, 7772247, 10611491, 15447864, 20496809 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
a(n) is the number of labeled trees with sum of the labels equal to n-1 and the outdegree of every node less than or equal to the value of its label. - Andrew Howroyd, Feb 02 2021
LINKS
EXAMPLE
The a(7) = 13 trees: ((o(ooo))), ((oo(oo))), ((ooooo)), (o((ooo))), (o(oo(o))), (o(oooo)), ((o)(ooo)), (oo((oo))), (oo(o(o))), (o(o)(oo)), (ooo(oo)), (oooo(o)), (oooooo).
MATHEMATICA
krut[n_]:=krut[n]=If[n===1, {{}}, Select[Join@@Function[c, Union[Sort/@Tuples[krut/@c]]]/@IntegerPartitions[n-1], UnsameQ@@Length/@Cases[#, {__}, {0, Infinity}]&]];
Table[krut[n]//Length, {n, 15}]
PROG
(PARI)
relabel(b)={my(w=hammingweight(b)); b = bitand((1<<w)-1, b); b + (((1 << (w-hammingweight(b))) - 1) << w)}
a(n)={local(M=Map());
my(recurse(b, k) = if(!b, 1, b=relabel(b); my(hk=[b, k], z); if(!mapisdefined(M, hk, &z),
z = if(k==0,
sum(i=1, logint(b, 2), if(bittest(b, i), self()(b-2^i, i-1))),
sum(f=2^logint(b, 2), b, if(!bitnegimply(f, b), self()(f, 0)*self()(b-f, k-1)));
);
mapput(M, hk, z)); z));
if( n==1, 1, my(t=0); for(np=1, sqrtint(2*n-2), forpart(p=n-1-binomial(np, 2), t+=recurse(sum(i=1, #p, 2^(p[i]+i-1)), 0), , [np, np])); t);
} \\ Andrew Howroyd, Feb 02 2021
CROSSREFS
Sequence in context: A218426 A321662 A320176 * A144419 A212322 A367005
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 19 2018
EXTENSIONS
a(27)-a(34) from Robert G. Wilson v, Jan 19 2018
Terms a(35) and beyond from Andrew Howroyd, Feb 02 2021
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)