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

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

Author

Gus Wiseman, Feb 04 2019

Keywords

• nonn
• tabl

Comments

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.

Examples

			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]
		

Links

• 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

Crossrefs

First and last columns are A001037. Main diagonal is A323872.

Cf. A000031, A000740, A027375, A059966, A179043, A184271.

Cf. A323859, A323860, A323865, A323866, A323871.

Programs

GAP

# 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

Mathematica

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}]

Extensions

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