|
|
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);
|
|
CROSSREFS
|
Cf. A000081, A001190, A001678, A004111, A032305, A124343, A290689, A295461, A298118, A298304, A298422, A298479.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|