|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|