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

%I #48 Jul 05 2024 11:18:46

%S 2,3,3,4,7,4,6,14,14,6,8,40,64,40,8,14,108,352,352,108,14,20,362,2192,

%T 4156,2192,362,20,36,1182,14624,52488,52488,14624,1182,36,60,4150,

%U 99880,699600,1342208,699600,99880,4150,60,108,14602,699252,9587580,35792568

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

%C 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

%H Alois P. Heinz, <a href="/A184271/b184271.txt">Antidiagonals n = 1..100, flattened</a> (first 95 terms from R. H. Hardin)

%H S. N. Ethier, <a href="http://arxiv.org/abs/1301.2352">Counting toroidal binary arrays</a>, arXiv preprint arXiv:1301.2352, 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">J. Int. Seq. 16 (2013) #13.4.7</a> .

%H S. N. Ethier and Jiyeon Lee, <a href="http://arxiv.org/abs/1502.03792">Counting toroidal binary arrays, II</a>, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Lee/lee6.html">J. Int. Seq. 18 (2015) # 15.8.3</a>.

%H Veronika Irvine, <a href="http://hdl.handle.net/1828/7495">Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns</a>, PhD Dissertation, University of Victoria, 2016.

%H Peter Kagey and William Keehn, <a href="https://arxiv.org/abs/2311.13072">Counting tilings of the n X m grid, cylinder, and torus</a>, arXiv:2311.13072 [math.CO], 2023.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pólya_enumeration_theorem">Pólya enumeration theorem</a>

%F 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

%e 1 2 3 4 5 6 7

%e ----------------------------------------------------------------------------

%e 1: 2 3 4 6 8 14 20

%e 2: 3 7 14 40 108 362 1182

%e 3: 4 14 64 352 2192 14624 99880

%e 4: 6 40 352 4156 52488 699600 9587580

%e 5: 8 108 2192 52488 1342208 35792568 981706832

%e 6: 14 362 14624 699600 35792568 1908897152 104715443852

%e 7: 20 1182 99880 9587580 981706832 104715443852 11488774559744

%e 8: 36 4150 699252 134223976 27487816992 5864063066500

%e 9: 60 14602 4971184 1908881900 781874936816

%e 10: 108 52588 35792568 27487869472

%e From _Gus Wiseman_, Feb 04 2019: (Start)

%e Inequivalent representatives of the T(2,3) = 14 toroidal necklaces:

%e [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1]

%e [0 0 0] [0 0 1] [0 1 1] [1 1 1] [0 0 1] [0 1 0] [0 1 1]

%e .

%e [0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]

%e [1 0 1] [1 1 0] [1 1 1] [0 1 1] [1 0 1] [1 1 1] [1 1 1]

%e (End)

%t 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)

%t (* second program *)

%t neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];

%t Table[Length[Select[Partition[#,n-k]&/@Tuples[{0,1},(n-k)*k],neckmatQ]],{n,8},{k,n-1}] (* _Gus Wiseman_, Feb 04 2019 *)

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

%Y Main diagonal is A179043.

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

%K nonn,tabl

%O 1,1

%A _R. H. Hardin_, Jan 10 2011