A086675 Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.

1, 2, 10, 176, 16456, 6710912, 11453291200, 80421421917440, 2305843009750581376, 268650182136584290872320, 126765060022823052739661424640, 241677817415439249618874010960064512, 1858395433210885261795036719974526548094976

Offset

0,2

Comments

Also the number of digraphical necklaces with n vertices. A digraphical necklace is defined to be a directed graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of directed graphs under rotation of the vertices. These are a kind of partially labeled digraphs. - Gus Wiseman, Mar 04 2019

Links

Alois P. Heinz, Table of n, a(n) for n = 0..57

Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See p. 3.

Formula

a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n^2/d) for n > 0, a(0) = 1.

Example

From Gus Wiseman, Mar 04 2019: (Start)
Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:
  {}
  {(1,1)}
  {(1,2)}
  {(1,1),(1,2)}
  {(1,1),(2,1)}
  {(1,1),(2,2)}
  {(1,2),(2,1)}
  {(1,1),(1,2),(2,1)}
  {(1,1),(1,2),(2,2)}
  {(1,1),(1,2),(2,1),(2,2)}
(End)

Mathematica

Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]
(* second program *)
rotdigra[g_, m_]:=Sort[g/.k_Integer:>If[k==m, 1, k+1]];
Table[Length[Select[Subsets[Tuples[Range[n], 2]], #=={}||#==First[Sort[Table[Nest[rotdigra[#, n]&, #, j], {j, n}]]]&]], {n, 0, 4}] (* Gus Wiseman, Mar 04 2019 *)

Crossrefs

Cf. A000031 (binary necklaces), A000939 (cycle necklaces), A008965, A060690, A061417 (permutation necklaces), A184271, A192332 (graphical necklaces), A275527 (path necklaces), A323858 (toroidal necklaces), A323870.

Cf. A324463, A324464, A324513, A324514.

Sequence in context: A063573 A368573 A356887 * A319607 A057119 A226563

Adjacent sequences: A086672 A086673 A086674 * A086676 A086677 A086678

Keyword

nonn,easy

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003

Extensions

More terms from Wouter Meeussen, Jul 29 2003

a(0)=1 prepended by Gus Wiseman, Mar 04 2019

Status

approved