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
Examples
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| | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
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.
Crossrefs
Programs
-
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 *) -
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
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
Comments