A298478 Number of unlabeled rooted trees with n nodes in which all positive outdegrees are different.

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

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

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

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

Cf. A000081, A001190, A001678, A004111, A032305, A124343, A290689, A295461, A298118, A298304, A298422, A298479.

Sequence in context: A218426 A321662 A320176 * A144419 A212322 A367005

Adjacent sequences: A298475 A298476 A298477 * A298479 A298480 A298481

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