A318226 Number of inequivalent leaf-colorings of rooted trees with n nodes.
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
Keywords
Examples
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)
Crossrefs
Programs
-
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}] -
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
Extensions
Terms a(9) and beyond from Andrew Howroyd, Dec 10 2020