login
A318226
Number of inequivalent leaf-colorings of rooted trees with n nodes.
6
1, 1, 3, 8, 25, 80, 286, 1070, 4280, 17946, 78907, 361248, 1718001, 8456130, 42980034, 225066289, 1212028798, 6701265897, 37986122037, 220477639797, 1308833637621, 7938564964369, 49151551028767, 310388888456536, 1997635594602629, 13093695854320203, 87349973125826943
OFFSET
1,3
EXAMPLE
Inequivalent representatives of the a(5) = 25 leaf-colorings:
(1111) (11(1)) (1(11)) ((111)) ((1)(1)) (1((1))) ((1(1))) (((11))) ((((1))))
(1112) (11(2)) (1(12)) ((112)) ((1)(2)) (1((2))) ((1(2))) (((12)))
(1122) (12(1)) (1(22)) ((123))
(1123) (12(3)) (1(23))
(1234)
MATHEMATICA
undats[m_]:=Union[DeleteCases[Cases[m, _?AtomQ, {0, Infinity}, Heads->True], List]];
expnorm[m_]:=If[Length[undats[m]]==0, m, If[undats[m]!=Range[Max@@undats[m]], expnorm[m/.Rule@@@Table[{(undats[m])[[i]], i}, {i, Length[undats[m]]}]], First[Sort[expnorm[m, 1]]]]]; expnorm[m_, aft_]:=If[Length[undats[m]]<=aft, {m}, With[{mx=Table[Count[m, i, {0, Infinity}, Heads->True], {i, Select[undats[m], #>=aft&]}]}, Union@@(expnorm[#, aft+1]&/@Union[Table[MapAt[Sort, m/.{par+aft-1->aft, aft->par+aft-1}, Position[m, _[___]]], {par, First/@Position[mx, Max[mx]]}]])]];
urt[n_]:=urt[n]=If[n==1, {{}}, Join@@Table[Union[Sort/@Tuples[urt/@c]], {c, IntegerPartitions[n-1]}]];
slip[e_, l_, q_]:=ReplacePart[e, Rule@@@Transpose[{Position[e, l], q}]];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Join@@Table[Union[expnorm/@Table[slip[tree, {}, seq], {seq, Join@@Permutations/@allnorm[Count[tree, {}, {0, Infinity}, Heads->True]]}]], {tree, urt[n]}]], {n, 7}]
PROG
(PARI) \\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(Z=x*sv(1), p = Z + O(x^2)); for(n=2, n, p = Z-x + x*sEulerT(p)); p}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 13 2020
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 21 2018
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Dec 10 2020
STATUS
approved