login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

Table of n, a(n) for n=1..27.

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

CROSSREFS

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

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

Sequence in context: A101490 A148793 A180718 * A197159 A161634 A293385

Adjacent sequences:  A318223 A318224 A318225 * A318227 A318228 A318229

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 21 2018

EXTENSIONS

Terms a(9) and beyond from Andrew Howroyd, Dec 10 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 02:41 EDT 2021. Contains 347609 sequences. (Running on oeis4.)