login
A318227
Number of inequivalent leaf-colorings of rooted identity trees with n nodes.
7
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,4
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
LINKS
FORMULA
a(n) = Sum_{k=1..n} A055327(n,k) * A000110(k). - Andrew Howroyd, Dec 10 2020
EXAMPLE
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)))
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}]
PROG
(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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 21 2018
EXTENSIONS
Terms a(17) and beyond from Andrew Howroyd, Dec 10 2020
STATUS
approved