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.
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
Examples
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; ...
References
- F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..300 (24 rows; first 36 terms from Marko Riedel)
- Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
- Marko Riedel, Maple code for sequence A295197, computing all colorings at once with no prior classification.
- Marko Riedel, Maple code for sequence A295197, classifying by the exact number of colors that appear.
Crossrefs
Programs
-
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
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
Comments