login
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.
9
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.
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.
Sequence in context: A128116 A082153 A283944 * A013946 A261327 A330613
KEYWORD
nonn,tabl,nice
AUTHOR
Marko Riedel, Nov 06 2017
STATUS
approved