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

Author

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

Keywords

• nonn
• easy

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

Examples

			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)
		

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.

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.

Programs

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

Formula

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

Extensions

More terms from Wouter Meeussen, Jul 29 2003

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