A318227 Number of inequivalent leaf-colorings of rooted identity trees with n nodes.

1, 1, 1, 3, 5, 14, 38, 114, 330, 1054, 3483, 11841, 41543, 149520, 552356, 2084896, 8046146, 31649992, 127031001, 518434863, 2153133594, 9081863859, 38909868272, 169096646271, 745348155211, 3329032020048, 15063018195100, 68998386313333, 319872246921326, 1500013368166112

Offset: 1

Author

Gus Wiseman, Aug 21 2018

Keywords

• nonn

Comments

In a rooted identity tree, all branches directly under any given branch are different.

The leaves are colored after selection of the tree. Since all trees are asymmetric, the symmetry group of the leaves will be the identity group and a tree with k leaves will have Bell(k) inequivalent leaf-colorings. - Andrew Howroyd, Dec 10 2020

Examples

			Inequivalent representatives of the a(6) = 14 leaf-colorings:
  (1(1(1)))  ((1)((1)))  (1(((1))))  ((1((1))))  (((1(1))))  (((((1)))))
  (1(1(2)))  ((1)((2)))  (1(((2))))  ((1((2))))  (((1(2))))
  (1(2(1)))
  (1(2(2)))
  (1(2(3)))
		

Links

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

Crossrefs

Cf. A000081, A001190, A001678, A003238, A004111, A290689, A318185, A304486.

Cf. A318226, A318228, A318229, A318230, A318231, A318234.

Cf. A000110 (Bell numbers), A055327, A301342.

Programs

Mathematica

idt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[idt/@c]],UnsameQ@@#&],{c,IntegerPartitions[n-1]}]];
Table[Sum[BellB[Count[tree,{},{0,Infinity}]],{tree,idt[n]}],{n,16}]

PARI

\\ bell(n) is A000110(n).
WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
bell(n)={sum(k=1, n, stirling(n,k,2))}
seq(n)={my(v=[y], b=vector(n,k,bell(k))); for(n=2, n, v=concat(v[1], WeighMT(v))); vector(n, k, sum(i=1, k, polcoef(v[k],i)*b[i]))} \\ Andrew Howroyd, Dec 10 2020

Formula

a(n) = Sum_{k=1..n} A055327(n,k) * A000110(k). - Andrew Howroyd, Dec 10 2020

Extensions

Terms a(17) and beyond from Andrew Howroyd, Dec 10 2020