A294791 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry and swappable colors.

0, 1, 4, 1, 7, 31, 3, 23, 179, 2107, 3, 55, 1095, 26271, 671103, 7, 189, 7327, 350063, 17896831, 954459519, 9, 595, 49939, 4794087, 490853415, 52357746895, 5744387279871, 19, 2101, 349715, 67115111, 13743921631, 2932032057731, 643371380132743, 144115188277194943, 29, 7315, 2485591, 954444607, 390937468407, 166799988703927, 73201365371896619

Offset

1,3

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.)

References

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

Links

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

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Marko Riedel, Maple code for sequences A294791, A294792, A294793, A294794.

Formula

T(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) with Q=2. 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.

Example

For the 2 X 2 grid and two colors we find T(2,2) = 4:
  +---+  +---+  +---+  +---+
  |X| |  |X| |  |X|X|  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | |X|  | | |  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+

Crossrefs

Cf. A152175, A294684, A294685, A294686, A294687, A294792, A294793, A294794, A295197. T(n,1) is A056295.

Sequence in context: A139045 A349147 A262361 * A084884 A329998 A143320

Adjacent sequences: A294788 A294789 A294790 * A294792 A294793 A294794

Keyword

nonn,tabl,nice

Author

Marko Riedel, Nov 08 2017

Status

approved