A323872 -id:A323872 - cp's OEIS frontend

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

R. H. Hardin, Jan 10 2011

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

			      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)

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

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.

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

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

A179043 Number of n X n checkered tori.

Original entry on oeis.org

1, 2, 7, 64, 4156, 1342208, 1908897152, 11488774559744, 288230376353050816, 29850020237398264483840, 12676506002282327791964489728, 21970710674130840874443091905462272, 154866286100907105149651981766316633972736

Offset: 0

Rouben Rostamian (rostamian(AT)umbc.edu), Jun 25 2010

nonn

Consider an n X n checkerboard whose tiles are assigned colors 0 and 1, at random. There are 2^(n^2) such checkerboards. We identify the opposite edges of each checkerboard, thus making it into a (topological) torus. There are a(n) such (distinct) tori. It is possible to show that a(n) >= 2^(n^2)/n^2 for all n.
Main diagonal of A184271.
Main diagonal of Table 3: The number a(m, n) of toroidal m X n binary arrays, allowing rotation of the rows and/or the columns but not reflection, for m, n = 1, 2, ..., 8, at page 5 of Ethier. - Jonathan Vos Post, Jan 14 2013
This is a 2-dimensional generalization of binary necklaces (A000031). - Gus Wiseman, Feb 04 2019

			From _Gus Wiseman_, Feb 04 2019: (Start)
Inequivalent representatives of the a(2) = 7 checkered tori:
  [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
  [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..57
S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352v1 [math.CO], Jan 10, 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, J. Int. Seq. (2024) Vol. 27, Art. No. 24.6.1. See p. 2.
Wikipedia, Pólya enumeration theorem

Cf. A184271 (n X k toroidal binary arrays).
Cf. A000031, A001037, A008965.
Cf. A323858, A323859, A323861, A323863, A323865, A323870, A323872.

a[n_] := Sum[If[Mod[n, c] == 0, Sum[If[Mod[n, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n^2/LCM[c, d]), 0], {d, 1, n}], 0], {c, 1, n}]/n ^2

a(n) = (1/n^2)*Sum_{ c divides n } Sum_{ d divides n } phi(c)*phi(d)*2^(n^2/lcm(c,d)), where phi is A000010 and lcm stands for least common multiple. - Stewart N. Ethier, Aug 24 2012

Terms a(6) and a(7) from A184271
a(8)-a(12) from Stewart N. Ethier, Aug 24 2012
a(0)=1 prepended by Alois P. Heinz, Aug 20 2017

A323861 Table read by antidiagonals where A(n,k) is the number of n X k aperiodic binary toroidal necklaces.

Original entry on oeis.org

2, 1, 1, 2, 2, 2, 3, 9, 9, 3, 6, 27, 54, 27, 6, 9, 99, 335, 335, 99, 9, 18, 326, 2182, 4050, 2182, 326, 18, 30, 1161, 14523, 52377, 52377, 14523, 1161, 30, 56, 4050, 99858, 698535, 1342170, 698535, 99858, 4050, 56, 99, 14532, 698870, 9586395, 35790267, 35790267, 9586395, 698870, 14532, 99

Offset: 1

Gus Wiseman, Feb 04 2019

The 1-dimensional (Lyndon word) case is A001037.

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

			Table begins:
        1    2    3    4
    ------------------------
  1: |  2    1    2    3
  2: |  1    2    9   27
  3: |  2    9   54  335
  4: |  3   27  335 4050
Inequivalent representatives of the A(3,2) = 9 aperiodic toroidal necklaces:
  [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1]
  [0 0 1] [0 1 1] [0 1 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [1 0 1] [1 1 1]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.
Andrew Howroyd, GAP Program Code

First and last columns are A001037. Main diagonal is A323872.
Cf. A000031, A000740, A027375, A059966, A179043, A184271.
Cf. A323859, A323860, A323865, A323866, A323871.

# See link for code.
for n in [1..8] do for k in [1..8] do Print(A323861(n,k), ", "); od; Print("\n"); od; # Andrew Howroyd, Aug 21 2019

apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
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],And[apermatQ[#],neckmatQ[#]]&]],{n,6},{k,n-1}]

Terms a(37) and beyond from Andrew Howroyd, Aug 21 2019

A323863 Number of n X n aperiodic binary arrays.

Original entry on oeis.org

1, 2, 8, 486, 64800, 33554250, 68718675672, 562949953420302, 18446744060824780800, 2417851639229257812542976, 1267650600228226023797043513000, 2658455991569831745807614120560664598, 22300745198530623141521551172073990303938400

Offset: 0

Gus Wiseman, Feb 04 2019

nonn

An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

			The a(2) = 8 arrays are:
  [0 0] [0 0] [0 1] [0 1] [1 0] [1 0] [1 1] [1 1]
  [0 1] [1 0] [0 0] [1 1] [0 0] [1 1] [0 1] [1 0]
Note that the following are not aperiodic even though their row and column sequences are (independently) aperiodic:
  [1 0] [0 1]
  [0 1] [1 0]

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000031, A000740, A027375, A179043, A265627, A323351.

Cf. A323860, A323862, A323864, A323865, A323867, A323869.

apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
Table[Length[Select[(Partition[#,n]&)/@Tuples[{0,1},n^2],apermatQ]],{n,4}]

a(n) = 2^(n^2) - (n+1)*2^n + 2*n if n is prime. - Robert Israel, Feb 04 2019

a(n) = n^2 * A323872(n). - Andrew Howroyd, Aug 21 2019

a(5) from Robert Israel, Feb 04 2019
a(6)-a(7) from Giovanni Resta, Feb 05 2019
Terms a(8) and beyond from Andrew Howroyd, Aug 21 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A179043 Number of n X n checkered tori.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A323861 Table read by antidiagonals where A(n,k) is the number of n X k aperiodic binary toroidal necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

Extensions

A323863 Number of n X n aperiodic binary arrays.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions