A184271 Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal binary arrays (n >= 1, k >= 1).

2, 3, 3, 4, 7, 4, 6, 14, 14, 6, 8, 40, 64, 40, 8, 14, 108, 352, 352, 108, 14, 20, 362, 2192, 4156, 2192, 362, 20, 36, 1182, 14624, 52488, 52488, 14624, 1182, 36, 60, 4150, 99880, 699600, 1342208, 699600, 99880, 4150, 60, 108, 14602, 699252, 9587580, 35792568

Offset: 1

Author

R. H. Hardin, Jan 10 2011

Keywords

• nonn
• tabl

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

Examples

			      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)
		

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

Crossrefs

Columns 1-8 are A000031, A184264, A184265, A184266, A184267, A184268, A184269, A184270.

Main diagonal is A179043.

Cf. A001037 (binary Lyndon words), A008965, A323858, A323859 (binary toroidal necklaces of size n), A323861 (aperiodic version), A323865, A323870 (normal toroidal necklaces), A323872.

Programs

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

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