OFFSET
1,1
COMMENTS
This is a 2-dimensional generalization of binary necklaces (A000031). A toroidal array or necklace can be defined either as an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns, or as a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns. - Gus Wiseman, Feb 04 2019
LINKS
Alois P. Heinz, Antidiagonals n = 1..100, flattened (first 95 terms from R. H. Hardin)
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352, 2013 and J. Int. Seq. 16 (2013) #13.4.7 .
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023.
Wikipedia, Pólya enumeration theorem
FORMULA
T(n,k) = (1/(nk))*Sum_{ c divides n } Sum_{ d divides k } phi(c)*phi(d)*2^(nk/lcm(c,d)), where phi is A000010 and lcm stands for least common multiple. - Stewart N. Ethier, Aug 24 2012
EXAMPLE
1 2 3 4 5 6 7
----------------------------------------------------------------------------
1: 2 3 4 6 8 14 20
2: 3 7 14 40 108 362 1182
3: 4 14 64 352 2192 14624 99880
4: 6 40 352 4156 52488 699600 9587580
5: 8 108 2192 52488 1342208 35792568 981706832
6: 14 362 14624 699600 35792568 1908897152 104715443852
7: 20 1182 99880 9587580 981706832 104715443852 11488774559744
8: 36 4150 699252 134223976 27487816992 5864063066500
9: 60 14602 4971184 1908881900 781874936816
10: 108 52588 35792568 27487869472
From Gus Wiseman, Feb 04 2019: (Start)
Inequivalent representatives of the T(2,3) = 14 toroidal necklaces:
[0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1]
[0 0 0] [0 0 1] [0 1 1] [1 1 1] [0 0 1] [0 1 0] [0 1 1]
.
[0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]
[1 0 1] [1 1 0] [1 1 1] [0 1 1] [1 0 1] [1 1 1] [1 1 1]
(End)
MATHEMATICA
a[n_, k_] := Sum[If[Mod[n, c] == 0, Sum[If[Mod[k, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n k/LCM[c, d]), 0], {d, 1, k}], 0], {c, 1, n}]/(n k)
(* second program *)
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m, {i, j}], {i, Length[m]}, {j, Length[First[m]]}]];
Table[Length[Select[Partition[#, n-k]&/@Tuples[{0, 1}, (n-k)*k], neckmatQ]], {n, 8}, {k, n-1}] (* Gus Wiseman, Feb 04 2019 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Jan 10 2011
STATUS
approved