A318226 - OEIS

%I #15 Dec 13 2020 16:13:55

%S 1,1,3,8,25,80,286,1070,4280,17946,78907,361248,1718001,8456130,

%T 42980034,225066289,1212028798,6701265897,37986122037,220477639797,

%U 1308833637621,7938564964369,49151551028767,310388888456536,1997635594602629,13093695854320203,87349973125826943

%N Number of inequivalent leaf-colorings of rooted trees with n nodes.

%e Inequivalent representatives of the a(5) = 25 leaf-colorings:

%e (1111) (11(1)) (1(11)) ((111)) ((1)(1)) (1((1))) ((1(1))) (((11))) ((((1))))

%e (1112) (11(2)) (1(12)) ((112)) ((1)(2)) (1((2))) ((1(2))) (((12)))

%e (1122) (12(1)) (1(22)) ((123))

%e (1123) (12(3)) (1(23))

%e (1234)

%t undats[m_]:=Union[DeleteCases[Cases[m,_?AtomQ,{0,Infinity},Heads->True],List]];

%t 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]]}]])]];

%t urt[n_]:=urt[n]=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[urt/@c]],{c,IntegerPartitions[n-1]}]];

%t slip[e_,l_,q_]:=ReplacePart[e,Rule@@@Transpose[{Position[e,l],q}]];

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

%t 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}]

%o (PARI) \\ See links in A339645 for combinatorial species functions.

%o cycleIndexSeries(n)={my(Z=x*sv(1), p = Z + O(x^2)); for(n=2, n, p = Z-x + x*sEulerT(p)); p}

%o InequivalentColoringsSeq(cycleIndexSeries(15)) \\ _Andrew Howroyd_, Dec 13 2020

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

%Y Cf. A318227, A318228, A318229, A318230, A318231, A318234, A339645.

%K nonn

%O 1,3

%A _Gus Wiseman_, Aug 21 2018

%E Terms a(9) and beyond from _Andrew Howroyd_, Dec 10 2020