login
A295197
Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using any number of swappable colors, 1 <= k <= n.
6
1, 2, 9, 3, 43, 2387, 7, 587, 351773, 655089857, 12, 11703, 92197523, 2586209749712, 185543613289205809, 43, 352902, 37893376167, 18581620064907130, 28224967150633208580385, 106103186941524316132396201360, 127, 13639372, 22612848403571, 220019264470242220839, 8045720086273150473238405274, 851013076163633746725692124186472539, 218900758256599151027392153440612298654753249
OFFSET
1,2
COMMENTS
Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.) Maximum number of colors is n * k.
REFERENCES
F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.
FORMULA
T(n,k) = Sum_{Q=1..n*k} (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma). The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.
T(n,k) = (Sum_{d|n} Sum_{f|k} phi(d) * phi(f) * A162663(n*k/lcm(d,f), lcm(d,f)))/(n*k). - Andrew Howroyd, Oct 06 2024
EXAMPLE
The two-by-two with swappable colors has one monochrome coloring, four colorings with two colors, three colorings with three colors (determined by the color that appears twice) and one coloring with four colors.
Triangle begins:
1;
2, 9;
3, 43, 2387;
7, 587, 351773, 655089857;
12, 11703, 92197523, 2586209749712, 185543613289205809;
...
PROG
(PARI) \\ B(m, n) is A162663(n, m).
B(m, n)={n!*polcoef(exp(sumdiv(m, d, (exp(d*x + O(x*x^n))-1)/d)), n)}
T(n, k)={my(v=vector(lcm(n, k))); fordiv(n, d, fordiv(k, e, v[lcm(d, e)] += eulerphi(d) * eulerphi(e) )); sumdiv(#v, g, v[g]*B(g, n*k/g))/(n*k)} \\ Andrew Howroyd, Oct 06 2024
CROSSREFS
Main diagonal is A376808.
Sequence in context: A088614 A162615 A275716 * A155163 A309929 A339799
KEYWORD
nonn,tabl
AUTHOR
Marko Riedel, Nov 16 2017
STATUS
approved