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

0, 1, 5, 2, 12, 62, 4, 38, 350, 4154, 6, 106, 2190, 52486, 1342206, 12, 360, 14622, 699598, 35792566, 1908897150, 18, 1180, 99878, 9587578, 981706830, 104715443850, 11488774559742, 34, 4148, 699250, 134223974, 27487816990, 5864063066498, 1286742755471398, 288230376353050814

Offset

1,3

Comments

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

References

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

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

Marko Riedel, Maple code for sequences A294684, A294685, A294686, A294687.

Formula

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=2 and S(n,k) Stirling numbers of the second kind.

T(n,k) = A184271(n,k) - 2. - Andrew Howroyd, Oct 05 2024

Example

Triangle begins:
   0;
   1,    5;
   2,   12,    62;
   4,   38,   350,    4154;
   6,  106,  2190,   52486,   1342206;
  12,  360, 14622,  699598,  35792566,   1908897150;
  18, 1180, 99878, 9587578, 981706830, 104715443850, 11488774559742;
  ...
For the 2 X 2 and two colors we find
  +---+  +---+  +---+  +---+  +---+
  |X| |  | |X|  |X| |  |X|X|  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  |X|X|  | |X|  | | |  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+

Mathematica

With[{Q = 2}, Table[(Q!/n/k) Sum[Sum[EulerPhi[d] EulerPhi[f] StirlingS2[GCD[d, f] (n/d) (k/f), Q], {f, Divisors@ k}], {d, Divisors@ n}], {n, 8}, {k, n}]] // Flatten (* Michael De Vlieger, Nov 08 2017 *)

Prog

(PARI) T(n, m) = {2*sumdiv(n, d, sumdiv(m, e, eulerphi(d) * eulerphi(e) * stirling(n*m/lcm(d, e), 2, 2) ))/(n*m)} \\ Andrew Howroyd, Oct 05 2024

Crossrefs

Main diagonal is A376822.

Cf. A184271, A294685, A294686, A294687, A294791, A294792, A294793, A294794. T(n,1) is A052823.

Sequence in context: A128116 A082153 A283944 * A013946 A261327 A330613

Adjacent sequences: A294681 A294682 A294683 * A294685 A294686 A294687

Keyword

nonn,tabl,nice

Author

Marko Riedel, Nov 06 2017

Status

approved