A376808 Number of non-isomorphic colorings of a toroidal n X n grid using any number of swappable colors.

1, 9, 2387, 655089857, 185543613289205809, 106103186941524316132396201360, 218900758256599151027392153440612298654753249, 2689595989958732045849530682270318547733917269644639109073775285

Offset: 1

Author

Marko Riedel, Oct 04 2024

Keywords

• nonn

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). The maximum number of colors is n * n.

Examples

			For the 2x2 we find
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  |X|X|   |X|X|   |X|X|   |X| |   |X| |
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  |X|X|   |X| |   | | |   |X| |   | |X|
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  +-+-+   +-+-+   +-+-+   +-+-+
  |X|Y|   |X| |   |X| |   |X|Y|
  +-+-+   +-+-+   +-+-+   +-+-+
  | | |   |Y| |   | |Y|   |Z| |
  +-+-+   +-+-+   +-+-+   +-+-+
so a(2) = 9.
		

References

• F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..24
• Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
• Marko Riedel, Maple code for sequence by PGE.

Crossrefs

Main diagonal of A295197.

Cf. A294791, A294792, A294793, A294794.

Formula

a(n) = Sum_{Q=1..n^2} (1/(n^2*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|n} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(n/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.