login
Number of toroidal n X n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition.
3

%I #25 Nov 30 2023 16:39:03

%S 1,2,6,44,2209,674384,954623404,5744406453840,144115192471496836,

%T 14925010120653819583840,6338253001142965335834871200,

%U 10985355337065423791175013899922368,77433143050453552587418968170813573149024

%N Number of toroidal n X n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition.

%H Michael De Vlieger, <a href="/A255015/b255015.txt">Table of n, a(n) for n = 0..57</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 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. See p. 3.

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

%F a(n) = (2*n^2)^{-1} Sum_{ c divides n } Sum_{ d divides n } phi(c)*phi(d)* 2^(n^2/lcm(c,d)) + (2*n)^{-1} Sum_{ d divides n } phi(d)*2^(n*(n + d - 2 *floor(d/2))/(2*d)), where phi is A000010.

%t a[n_] := (2 n^2)^(-1) 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}] + (2 n)^(-1) Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n (n + d - 2 IntegerPart[d/2])/(2 d)), 0], {d, 1, n}];

%Y Cf. A184271 (number of m X n binary arrays allowing rotation of rows/columns), A179043 (main diagonal of A184271), A222188 (number of m X n binary arrays allowing rotation/reflection of rows/columns), A209251 (main diagonal of A222188), A255016 (number of n X n binary arrays allowing rotation/reflection of rows/columns as well as matrix transposition).

%K nonn

%O 0,2

%A _Stewart N. Ethier_, Feb 12 2015

%E a(0)=1 from _Alois P. Heinz_, Feb 19 2015