Counting Toroidal Binary Arrays

S. N. Ethier^{1} Department of Mathematics University of Utah 155 South 1400 East Salt Lake City, UT 84112 USA ethier@math.utah.edu

Abstract A formula for the number of toroidal m × n binary arrays, allowing rotation of the rows and/or the columns but not reflection, is known. Here we find a formula for the number of toroidal m × n binary arrays, allowing rotation and/or reflection of the rows and/or the columns.

1 Introduction

The number of necklaces with n beads of two colors when turning over is not allowed is

\frac{1}{n} ∑_{d | n} φ(d) 2^{n/d},  (1)

where φ is Euler’s phi function. When turning over is allowed, the number becomes

\frac{1}{2n} ∑_{d | n} φ(d) 2^{n/d} + \begin{cases}2^{(n−1)/2}, & if n is odd; \\ 3 · 2^{n/2−2}, & if n is even. \end{cases}  (2)

These are the core sequences \underline{A000031} and \underline{A000029}, respectively, in The On-Line Encyclopedia of Integer Sequences [3].

1Partially supported by a grant from the Simons Foundation (209632).

Our concern here is with two-dimensional versions of these formulas. We consider an m × n binary array. When opposite edges are identified, it becomes what we will call a toroidal binary array. Just as we can rotate a necklace without effect, we can rotate the rows and/or the columns of such an array without effect. The number of (distinct) toroidal m × n binary arrays is

\frac{1}{mn} ∑_{c | m} ∑_{d | n} φ(c)φ(d) 2^{mn/ lcm(c,d)},  (3)

where lcm stands for least common multiple. This is \underline{A184271} in the OEIS [3]. The diagonal is \underline{A179043}. Rows (or columns) 2–8 are \underline{A184264}–\underline{A184270}. Row (or column) 1 is of course \underline{A000031}.

Our aim here is to find the formula that is related to (3) in the same way that (2) is related to (1). More precisely, we wish to count the number of toroidal m × n binary arrays allowing rotation and/or reflection of the rows and/or the columns. This is \underline{A222188} in the OEIS [3]. The diagonal is \underline{A209251}. Rows (or columns) 2–5 are \underline{A222187} and \underline{A222189}–\underline{A222191}. Row (or column) 1 is of course \underline{A000029}.

For an alternative description, we could define a group action on the set of m × n binary arrays, which has 2^{mn} elements. If the group is C_{m} × C_{n}, where C_{m} denotes the cyclic group of order m, then the number of orbits is given by (3) (see Theorem 1 below). If the group is D_{m} × D_{n}, where D_{m} denotes the dihedral group of order 2m, then the number of orbits is given in Theorem 2 below.

Both theorems are proved using Pólya’s enumeration theorem (actually, the simplified unweighted version; see, e.g., van Lint and Wilson [4, Theorem 37.1, p. 524]). Gilbert and Riordan [1] gave other applications of Pólya’s theorem in which the group was, as it is here, a direct product.

To help clarify the distinction between the two group actions, we provide an example. There is no distinction in the 2 × 2 case, so we consider the 3 × 3 case. When the group is C_{3} × C_{3} (allowing rotation of the rows and/or the columns but not reflection), there are 64 orbits, as shown in Table 1. When the group is D_{3} × D_{3} (allowing rotation and/or reflection of the rows and/or the columns), there are 36 orbits, as shown in Table 2. Both tables were generated by Mathematica programs.

Our interest in the number of toroidal m × n binary arrays allowing rotation and/or reflection of the rows and/or the columns derives from the fact that this is the size of the state space of the projection of the Markov chain of Mihailović and Rajković [2] under the mapping that takes a state to the orbit containing it. This reduction of the state space, from 512 states to 36 states in the 3 × 3 case for example, makes it easier to evaluate the stationary distribution.

2 Rotations of rows and columns

Let X_{m,n} := {0, 1}^{{0,1,...,m−1}×{0,1,...,n−1}} be the set of m × n arrays of 0s and 1s, which has 2^{mn} elements. Let a(m, n) denote the number of orbits of the group action on X_{m,n} by the Table 1: A list of the 64 orbits of the group action in which the group C_{3} × C_{3} acts on the set of 3 × 3 binary arrays. (Rows and/or columns can be rotated but not reflected.) Each orbit is represented by its minimal element in 9-bit binary form . Subscripts indicate orbit size. Bars separate different numbers of 1s.

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})_{1} | (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix})_{9} | (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix})_{9} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix})_{9}

(\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})_{3} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})_{3} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{matrix})_{9}

(\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix})_{9} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{9}

(\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix})_{9} |

(\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{9}

(\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{3} (\begin{matrix}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})_{3} |

(\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{9} | (\begin{matrix}0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} | (\begin{matrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{1}

Table 2: A list of the 36 orbits of the group action in which the group D_{3} × D_{3} acts on the set of 3 × 3 binary arrays. (Rows and/or columns can be rotated and/or reflected.) Each orbit is represented by its minimal element in 9-bit binary form. Subscripts indicate orbit size. Bars separate different numbers of 1s.

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})_{1} | (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix})_{9} | (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})_{18} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})_{36} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})_{6} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})_{36} |

(\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{36} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix})_{9} |

(\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{36} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})_{3} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})_{18} (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{6} |

(\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix})_{18} | (\begin{matrix}0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{9} | (\begin{matrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{1}

group C_{m} × C_{n}. In other words, a(m, n) is the number of (distinct) toroidal m × n binary arrays, allowing rotation of the rows and/or the columns but not reflection.

Theorem 1.

a(m, n) = \frac{1}{mn} ∑_{c | m} ∑_{d | n} φ(c)φ(d) 2^{mn/ lcm(c,d)}.  (4)

Proof. By Pólya’s enumeration theorem,

a(m, n) = \frac{1}{mn} ∑_{i=0}^{m−1} ∑_{j=0}^{n−1} 2^{A_{ij}},  (5)

where A_{ij} is the number of cycles in the permutation σ^{i}τ^{j}; here σ rotates the rows (row 0 becomes row 1, row 1 becomes row 2, …, row m − 1 becomes row 0) and τ rotates the columns. For example, A_{00} = mn because the identity permutation has mn fixed points, each of which is a cycle of length 1.

It is well known that, if d divides n, then the number of elements of C_{n} that are of order d is φ(d). So if c divides m and d divides n, then the number of pairs (i, j) ∈ {0, 1, …, m − 1} × {0, 1, …, n − 1} such that σ^{i} is of order c and τ^{j} is of order d is φ(c)φ(d). For such (i, j), σ^{i}τ^{j} is of order lcm(c, d) because σ^{i} and τ^{j} commute, hence each cycle of σ^{i}τ^{j} has length lcm(c, d) and A_{ij} = mn/ lcm(c, d). We are using the fact that each permutation in C_{m} × C_{n} has the property that all of its cycles are of equal length. Therefore, (4) follows from (5).

Clearly, a(1, n) reduces to (1); also, a(m, n) = a(n, m) for all m, n ≥ 1. Table 3 provides numerical values of a(m, n) for small m and n.

Table 3: The number a(m, n) of toroidal m × n binary arrays, allowing rotation of the rows and/or the columns but not reflection, for m, n = 1, 2, …, 8.

2  3  4  6  8  14  20  36
3  7  14  40  108  362  1182  4150
4  14  64  352  2192  14624  99880  699252
6  40  352  4156  52488  699600  9587580  134223976
8  108  2192  52488  1342208  35792568  981706832  27487816992
14  362  14624  699600  35792568  1908897152  104715443852  5864063066500
20 1182  99880  9587580  981706832  104715443852  11488774559744  1286742755471400
36 4150 699252 134223976 27487816992 5864063066500 1286742755471400 288230376353050816

3 Rotations and reflections of rows and columns

Let b(m, n) denote the number of orbits of the group action on X_{m,n} by the group D_{m} × D_{n}. In other words, b(m, n) is the number of (distinct) toroidal m × n binary arrays, allowing rotation and/or reflection of the rows and/or the columns.

Theorem 2.

b(m, n) = b_{1}(m, n) + b_{2}(m, n) + b_{3}(m, n) + b_{4}(m, n),

where

b_{1}(m, n) = \frac{1}{4mn} ∑_{c | m} ∑_{d | n} φ(c)φ(d) 2^{mn/ lcm(c,d)},

b_{2}(m, n)

= \begin{cases}(4n)^{−1}2^{(m+1)n/2}, & if m is odd; \\ (8n)^{−1}[2^{mn/2} + 2^{(m+2)n/2}], & if m is even, \end{cases} + \frac{1}{4n} ∑_{d≥2: d | n} φ(d) 2^{mn/d}

+ \begin{cases}(4n)^{−1} ∑′[2^{(m+1) gcd(j,n)/2} − 2^{m gcd(j,n)}], & if m is odd; \\ (8n)^{−1} ∑′[2^{m gcd(j,n)/2} + 2^{(m+2) gcd(j,n)/2} − 2^{m gcd(j,n)+1}], & if m is even, \end{cases}

with ∑′ := ∑_{1≤j≤n−1: n/ gcd(j,n) is odd},

b_{3}(m, n) = b_{2}(n, m),

and

b_{4}(m, n) = \begin{cases}2^{(mn−3)/2}, & if m and n are odd; \\ 3 · 2^{mn/2−3}, & if m and n have opposite parity; \\ 7 · 2^{mn/2−4}, & if m and n are even. \end{cases}

Proof. Again by Pólya’s enumeration theorem,

b(m, n) = \frac{1}{4mn} ∑_{i=0}^{m−1} ∑_{j=0}^{n−1}[2^{A_{ij}} + 2^{B_{ij}} + 2^{C_{ij}} + 2^{D_{ij}}],

where A_{ij} (resp., B_{ij}, C_{ij}, D_{ij}) is the number of cycles in the permutation σ^{i}τ^{j} (resp., σ^{i}τ^{j}ρ, σ^{i}τ^{j}θ, σ^{i}τ^{j}ρθ); here σ rotates the rows (row 0 becomes row 1, row 1 becomes row 2, …, row m − 1 becomes row 0), τ rotates the columns, ρ reflects the rows (rows 0 and m − 1 are interchanged, rows 1 and m − 2 are interchanged, …, rows ⌊m/2⌋ − 1 and m − ⌊m/2⌋ are interchanged), and θ reflects the columns.

By the proof of Theorem 1, we know the form of A_{ij}, and this gives the formula for b_{1}(m, n).

Next we find (B_{i0}), the entries in the 0th column of matrix B. For i = 0, 1, …, m−1, the permutation σ^{i}ρ can be described by its effect on the rows of {0, 1, …, m−1}×{0, 1, …, n− 1}. It reverses the first m − i rows and reverses the last i rows. Since the reversal of k consecutive integers has k/2 transpositions if k is even and (k − 1)/2 transpositions and one fixed point if k is odd, the permutation of {0, 1, …, m − 1} induced by σ^{i}ρ has (m − 1)/2 transpositions and one fixed point if m is odd, and m/2 transpositions if i is even and m is even, and (m − 2)/2 transpositions and two fixed points if i is odd and m is even. These numbers must be multiplied by n for the permutation σ^{i}ρ of {0, 1, …, m−1}×{0, 1, …, n− 1}. The results are that B_{i0} = (m + 1)n/2 if m is odd, B_{i0} = mn/2 if i is even and m is even, and B_{i0} = (m + 2)n/2 if i is odd and m is even. Therefore, (4mn)^{−1} ∑_{i=0}^{m−1} 2^{B_{i0}} = (4n)^{−1}2^{(m+1)n/2} if m is odd, whereas (4mn)^{−1} ∑_{i=0}^{m−1} 2^{B_{i0}} = (8n)^{−1}[2^{mn/2} + 2^{(m+2)n/2}] if m is even, and this gives the first term in the formula for b_{2}(m, n).

We turn to B_{ij} for i = 0, 1, …, m − 1 and j = 1, 2, …, n − 1. First, by a property of cyclic groups, τ^{j} has order d := n/ gcd(j, n). If d is even, then, since σ^{i}ρ has order 2 (see the preceding paragraph), σ^{i}τ^{j}ρ has order d and all of its cycles have length d. In this case, B_{ij} = mn/d = m gcd(j, n). Suppose then that d is odd. There are three cases: (i) m odd, (ii) i even and m even, and (iii) i odd and m even. Recall that σ^{i}ρ reverses the first m − i rows and reverses the last i rows. In case (i), one row is fixed by σ^{i}ρ, so cycles of σ^{i}τ^{j}ρ in this row have length d and all others have length 2d. We find that B_{ij} = n/d + (m − 1)n/(2d) = (m + 1)n/(2d) = (m + 1) gcd(j, n)/2. In case (ii), no rows are fixed by σ^{i}ρ, so all cycles of σ^{i}τ^{j}ρ have length 2d. It follows that B_{ij} = mn/(2d) = m gcd(j, n)/2. In case (iii), two rows are fixed by σ^{i}ρ, so cycles of σ^{i}τ^{j}ρ in these rows have length d and all others have length 2d. We conclude that B_{ij} = 2n/d + (m − 2)n/(2d) = (m + 2) gcd(j, n)/2. If the formula for B_{ij} that holds when d is even were valid generally, we would have the second term in the formula for b_{2}(m, n). The third term in the formula for b_{2}(m, n) is a correction to the second term to treat the cases (i)–(iii) in which d is odd.

Next, the formula for b_{3}(m, n) follows by symmetry. More explicitly,

b_{3}(m, n) = \frac{1}{4mn} ∑_{i=0}^{m−1} ∑_{j=0}^{n−1} 2^{C_{ij}} = \frac{1}{4nm} ∑_{j=0}^{n−1} ∑_{i=0}^{m−1} 2^{B_{ji}} = b_{2}(n, m)

because the number of cycles C_{ij} of σ^{i}τ^{j}θ acting on m × n arrays is equal to the number of cycles B_{ji} of σ^{j}τ^{i}ρ acting on n × m arrays.

Finally, we consider b_{4}(m, n). For i = 0, 1, …, m − 1 and j = 0, 1, …, n − 1, σ^{i}τ^{j}ρθ has the effect of reversing the first m − i rows, reversing the last i rows, reversing the first n − j columns, and reversing the last j columns. If m and n are odd, then there is one fixed point and (mn−1)/2 transpositions, so D_{ij} = (mn+1)/2 for all i and j, hence b_{4}(m, n) = 2^{(mn−3)/2}. If m is odd and n is even, then D_{ij} = mn/2 for all i and even j and D_{ij} = mn/2 + 1 for all i and odd j. This leads to b_{4}(m, n) = (1/8)[2^{mn/2} + 2^{mn/2+1}] = 3 · 2^{mn/2−3}. If m is even and n is odd, then D_{ij} = mn/2 for even i and all j and D_{ij} = mn/2 + 1 for odd i and all j. This leads to the same formula for b_{4}(m, n). Finally, if m and n are even, then D_{ij} = mn/2 unless i and j are both odd, in which case D_{ij} = mn/2 + 2. This implies that b_{4}(m, n) = (1/4)[(3/4)2^{mn/2} + (1/4)2^{mn/2+2}] = 7 · 2^{mn/2−4}.

This completes the proof.

It is easy to check that b(1, n) reduces to (2) and that b(m, n) = b(n, m) for all m, n ≥ 1. Table 4 provides numerical values of b(m, n) for small m and n.

Table 4: The number b(m, n) of toroidal m × n binary arrays, allowing rotation and/or reflection of the rows and/or the columns, for m, n = 1, 2, …, 8.

2  3  4  6  8  13  18  30
3  7  13  34  78  237  687  2299
4  13  36  158  708  4236  26412  180070
6  34  158  1459  14676  184854  2445918  33888844
8  78  708  14676  340880  8999762  245619576  6873769668
13  237  4236  184854  8999762  478070832  26185264801  1466114420489
18  687  26412  2445918  245619576  26185264801  2872221202512  321686550498774
30 2299 180070 33888844 6873769668 1466114420489 321686550498774 72057630729710704

References

[1] E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math. 5 (1961), 657–665.

[2] Z. Mihailović and M. Rajković, Cooperative Parrondo’s games on a two-dimensional lattice, Phys. A 365 (2006), 244–251.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/, 2013.

[4] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001.

2010 Mathematics Subject Classification: Primary 05A05. Keywords: necklace, Euler’s phi function, group action, cyclic group, dihedral group, Pólya’s enumeration theorem.

Concerned with sequences \underline{A000029}, \underline{A000031}, \underline{A179043}, \underline{A184264}, \underline{A184265}, \underline{A184266}, \underline{A184267}, \underline{A184268}, \underline{A184269}, \underline{A184270}, \underline{A184271}, \underline{A209251}, \underline{A222187}, \underline{A222188}, \underline{A222189}, \underline{A222190}, \underline{A222191}.

Received January 13 2013; revised version received April 26 2013. Published in Journal of Integer Sequences, May 1 2013.

Return to Journal of Integer Sequences home page.