Counting Toroidal Binary Arrays, II

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

Jiyeon Lee^{2} Department of Statistics Yeungnam University 214-1 Daedong, Kyeongsan Kyeongbuk 712-749 South Korea leejy@yu.ac.kr

Abstract

We derive formulas for (i) the number of distinct toroidal n × n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition, and (ii) the number of distinct toroidal n × n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition.

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

2Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (No. 2013R1A1A3A04007670).

1 Introduction

A previous paper [1] found the number of (distinct) toroidal m × n binary arrays, allowing rotation of rows and/or columns, to be

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

where φ is Euler’s phi function and lcm stands for least common multiple. This is \underline{A184271} in the On-Line Encyclopedia of Integer Sequences [2]. The main diagonal is \underline{A179043}. It was also shown that, allowing rotation and/or reflection of rows and/or columns, the number becomes

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

where

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

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

+ \begin{cases}(4n)^{−1} ∑′ φ(d)(2^{(m+1)n/(2d)} − 2^{mn/d}), & if m is odd; \\ (8n)^{−1} ∑′ φ(d)(2^{mn/(2d)} + 2^{(m+2)n/(2d)} − 2 · 2^{mn/d}), & if m is even, \end{cases}

with ∑′ := ∑_{d | n: d 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}

(The formula for b_{2}(m, n) given in [1] is simplified here.) This is \underline{A222188} in the OEIS [2]. The main diagonal is \underline{A209251}.

Our aim here is to derive the corresponding formulas when m = n and we allow matrix transposition as well. More precisely, we show that the number of (distinct) toroidal n × n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition, is

α(n) = \frac{1}{2} a(n, n) + \frac{1}{2n} ∑_{d | n} φ(d) 2^{n(n+d−2⌊d/2⌋)/(2d)},  (3)

where a(n, n) is from (1). When we allow rotation and/or reflection of rows and/or columns as well as matrix transposition, the number becomes

β(n) = \frac{1}{2} b(n, n) + \frac{1}{4n} ∑_{d | n} φ(d) 2^{n(n+d−2⌊d/2⌋)/(2d)} + \begin{cases}2^{(n^{2}−5)/4}, & if n is odd; \\ 5 · 2^{n^{2}/4−3}, & if n is even, \end{cases}  (4)

where b(n, n) is from (2). These are the sequences \underline{A255015} and \underline{A255016}, respectively, recently added to the OEIS [2].

For an alternative description, we could define a group action on the set of n × n binary arrays, which has 2^{n^{2}} elements. If the group is generated by σ (row rotation) and τ (column rotation), then the number of orbits is given by a(n, n); see [1]. If the group is generated by σ, τ, and ζ (matrix transposition), then the number of orbits is given by α(n); see Theorem 1 below. If the group is generated by σ, τ, ρ (row reflection), and θ (column reflection), then the number of orbits is given by b(n, n); see [1]. If the group is generated by σ, τ, ρ, θ, and ζ, then the number of orbits is given by β(n); see 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 [3, Theorem 37.1, p. 524]).

To help clarify the distinction between the various group actions, we consider the case of 3 × 3 binary arrays as in [1]. When the group is generated by σ and τ (allowing rotation of rows and/or columns), there are 64 orbits, which were listed in [1]. When the group is generated by σ, τ, and ζ (allowing rotation of rows and/or columns as well as matrix transposition), there are 44 orbits, which are listed in Table 1 below. When the group is generated by σ, τ, ρ, and θ (allowing rotation and/or reflection of rows and/or columns), there are 36 orbits, which were listed in [1]. When the group is generated by σ, τ, ρ, θ, and ζ (allowing rotation and/or reflection of rows and/or columns as well as matrix transposition), there are 26 orbits, which are listed in Table 2 below.

Table 3 provides numerical values for α(n) and β(n) for small n.

We take this opportunity to correct a small gap in the proof of Theorem 2 in [1]. The proof assumed implicitly that m, n ≥ 3. The theorem is correct as stated for m, n ≥ 1, so the proof is incomplete if m or n is 1 or 2. Following the proof of Theorem 2 below, we supply the missing steps.

2 Rotation of rows and columns, and matrix transposition

Let X_{n} := {0, 1}^{{0,1,...,n−1}^{2}} be the set of n × n matrices of 0s and 1s, which has 2^{n^{2}} elements. Let α(n) denote the number of orbits of the group action on X_{n} by the group of order 2n^{2} generated by σ (row rotation), τ (column rotation), and ζ (matrix transposition). (Exception: If n = 1, the group is of order 1.)

Informally, α(n) is the number of (distinct) toroidal n×n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition.

Theorem 1. With a(n, n) defined using (1), α(n) is given by (3).

Proof. Let us assume that n ≥ 2. By Pólya’s enumeration theorem,

α(n) = \frac{1}{2n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1}(2^{A_{ij}} + 2^{E_{ij}}),  (5)

Table 1: A list of the 44 orbits of the group action in which the group generated by σ, τ, and ζ acts on the set of 3 × 3 binary arrays. (Rows and/or columns can be rotated and matrices can be transposed.) 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})_{18} (\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})_{6} (\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})_{18} (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{18} (\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})_{18} (\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})_{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 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix})_{18} (\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 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 \\ 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 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix})_{18} | (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 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 \\ 1 & 1 & 0 \end{matrix})_{9} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})_{18} (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{18} (\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})_{6} (\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})_{18} (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})_{18} (\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})_{18} (\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})_{18} (\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}

where A_{ij} (resp., E_{ij}) is the number of cycles in the permutation σ^{i}τ^{j} (resp., σ^{i}τ^{j}ζ); here σ rotates the rows (row 0 becomes row 1, row 1 becomes row 2, …, row n − 1 becomes row 0), τ rotates the columns, and ζ transposes the matrix. We know from [1] that

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

so it remains to find E_{ij}. The permutation ζ has n fixed points and \binom{n}{2} transpositions, so E_{00} = n(n + 1)/2.

Notice that σ and τ commute, whereas σζ = ζτ and τζ = ζσ. Let (i, j) ∈ {0, 1, …, n − Table 2: A list of the 26 orbits of the group action in which the group generated by σ, τ, ρ, θ, and ζ acts on the set of 3 × 3 binary arrays. (Rows and/or columns can be rotated and/or reflected and matrices can be transposed.) 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})_{18} (\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})_{6} (\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})_{36} (\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})_{36} (\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})_{36} (\begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})_{9} (\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})_{36} (\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})_{36} (\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})_{6} (\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})_{36} (\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})_{18} (\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}

Table 3: The values of α(n) and β(n) for n = 1, 2, …, 12.

\begin{matrix}n & α(n) & β(n) \\ 1 & 2 & 2 \\ 2 & 6 & 6 \\ 3 & 44 & 26 \\ 4 & 2209 & 805 \\ 5 & 674384 & 172112 \\ 6 & 954623404 & 239123150 \\ 7 & 5744406453840 & 1436120190288 \\ 8 & 144115192471496836 & 36028817512382026 \\ 9 & 14925010120653819583840 & 3731252531904348833632 \\ 10 & 6338253001142965335834871200 & 1584563250300891724601560272 \\ 11 & 10985355337065423791175013899922368 & 2746338834266358751489231123956672 \\ 12 & 77433143050453552587418968170813573149024 & 19358285762613388352671214587818634041520 \end{matrix}

1}^{2} − {(0, 0)} be arbitrary. Then

(σ^{i}τ^{j}ζ)^{2} = (σ^{i}τ^{j}ζ)(ζτ^{i}σ^{j}) = σ^{i+j}τ^{i+j},

hence

(σ^{i}τ^{j}ζ)^{2d} = σ^{(i+j)d}τ^{(i+j)d} = ((στ)^{i+j})^{d},
(σ^{i}τ^{j}ζ)^{2d+1} = σ^{(i+j)d+i}τ^{(i+j)d+j}ζ.

Clearly, (σ^{i}τ^{j}ζ)^{2d+1} cannot be the identity permutation, so σ^{i}τ^{j}ζ is of even order. Using the fact that, in the cyclic group {a, a^{2}, …, a^{n−1}, a^{n} = e} of order n, a^{k} is of order n/ gcd(k, n), we find that the permutation σ^{i}τ^{j}ζ is of order 2d, where d := n/ gcd(i + j, n). Therefore, every cycle of this permutation must have length that divides 2d.

We claim that all cycles have length d or 2d. Accepting that for now, let us determine how many cycles have length d. A cycle that includes entry (k, l) has length d if (k, l) is a fixed point of (σ^{i}τ^{j}ζ)^{d}. For this to hold we must have d odd (otherwise there would be no fixed points because we have excluded the case i = j = 0 and (i + j)d/2 = lcm(i + j, n)/2 is not a multiple of n). Since

(σ^{i}τ^{j}ζ)^{d} = σ^{(i+j)(d−1)/2+i}τ^{(i+j)(d−1)/2+j}ζ,

we must also have

(k, l) = ([l + (i + j)(d − 1)/2 + j], [k + (i + j)(d − 1)/2 + i]),  (7)

where d := n/ gcd(i + j, n) and, for simplicity, [r] := (r mod n) ∈ {0, 1, …, n − 1}. For each k ∈ {0, 1, …, n − 1}, there is a unique l (namely, l := [k + (i + j)(d − 1)/2 + i]) such that (7) holds; indeed,

[l + (i + j)(d − 1)/2 + j] = [[k + (i + j)(d − 1)/2 + i] + (i + j)(d − 1)/2 + j]
= [k + (i + j)(d − 1)/2 + i + (i + j)(d − 1)/2 + j]
= [k + (i + j)d]
= [k + (i + j)(n/ gcd(i + j, n))]
= [k + lcm(i + j, n)]
= k.

This shows that there are n fixed points of (σ^{i}τ^{j}ζ)^{d}. Each cycle of length d of σ^{i}τ^{j}ζ will account for d such fixed points, hence there are n/d such cycles. All remaining cycles will have length 2d, and so there are n(n − 1)/(2d) of these. The total number of cycles is therefore n(n + 1)/(2d).

The other possibility is that d is even and all cycles have the same length, 2d, so there are n^{2}/(2d) of them. Notice that d is a divisor of n, so the contribution to

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{E_{ij}}

from odd d is

∑_{d | n: d is odd} nφ(d)2^{n(n+1)/(2d)}  (8)

and from even d is

∑_{d | n: d is even} nφ(d)2^{n^{2}/(2d)}.  (9)

The reason for the coefficient nφ(d) is that, if d | n, then the number of elements of the cyclic group {e, στ, (στ)^{2}, …, (στ)^{n−1}} that are of order d is φ(d). And for a given (i, j) ∈ {0, 1, …, n − 1}^{2}, there are n pairs (k, l) ∈ {0, 1, …, n − 1}^{2} such that [k + l] = [i + j]. Putting (8) and (9) together, we obtain

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{E_{ij}} = ∑_{d | n} nφ(d)2^{n(n+d−2⌊d/2⌋)/(2d)},  (10)

which, together with (5) and (6), yields (3).

It remains to prove our claim that, for (i, j) ∈ {0, 1, …, n−1}^{2}−{(0, 0)}, the permutation σ^{i}τ^{j}ζ cannot have any cycles whose length is a proper divisor of d := n/ gcd(i + j, n). Let c | d with 1 ≤ c < d. We must show that (σ^{i}τ^{j}ζ)^{c} has no fixed points. We can argue as above with c in place of d. For (k, l) to be a fixed point of (σ^{i}τ^{j}ζ)^{c} we must have (i + j)c a multiple of n. But d := n/ gcd(i + j, n) is the smallest integer c such that (i + j)c is a multiple of n because (i + j)n/ gcd(i + j, n) = lcm(i + j, n).

Finally, we excluded the case n = 1 at the beginning of the proof, but we notice that the formula (3) gives α(1) = 2, which is correct.

3 Rotation and reflection of rows and columns, and matrix transposition

Let X_{n} := {0, 1}^{{0,1,...,n−1}^{2}} be the set of n × n matrices of 0s and 1s, which has 2^{n^{2}} elements. Let β(n) denote the number of orbits of the group action on X_{n} by the group of order 8n^{2} generated by σ (row rotation), τ (column rotation), ρ (row reflection), θ (column reflection), and ζ (matrix transposition). (Exceptions: If n = 2, the group is of order 8; if n = 1, the group is of order 1.)

Informally, β(n) is the number of (distinct) toroidal n×n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition.

Theorem 2. With b(n, n) defined using (2), β(n) is given by (4).

Proof. Let us assume that n ≥ 3. (We will treat the cases n = 1 and n = 2 later.) By Pólya’s enumeration theorem,

β(n) = \frac{1}{8n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1}(2^{A_{ij}} + 2^{B_{ij}} + 2^{C_{ij}} + 2^{D_{ij}} + 2^{E_{ij}} + 2^{F_{ij}} + 2^{G_{ij}} + 2^{H_{ij}}),

where A_{ij} (resp., B_{ij}, C_{ij}, D_{ij}, E_{ij}, F_{ij}, G_{ij}, H_{ij}) is the number of cycles in the permutation σ^{i}τ^{j} (resp., σ^{i}τ^{j}ρ, σ^{i}τ^{j}θ, σ^{i}τ^{j}ρθ, σ^{i}τ^{j}ζ, σ^{i}τ^{j}ρζ, σ^{i}τ^{j}θζ, σ^{i}τ^{j}ρθζ); here σ rotates the rows (row 0 becomes row 1, row 1 becomes row 2, …, row n − 1 becomes row 0), τ rotates the columns, ρ reflects the rows (rows 0 and n − 1 are interchanged, rows 1 and n − 2 are interchanged, …, rows ⌊n/2⌋ − 1 and n − ⌊n/2⌋ are interchanged), θ reflects the columns, and ζ transposes the matrix. The order of the group generated by σ, τ, ρ, θ, and ζ is 8n^{2}, using the assumption that n ≥ 3.

We have already evaluated

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

α(n) = \frac{1}{2n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1}(2^{A_{ij}} + 2^{E_{ij}}),

and

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

so

β(n) = \frac{1}{2} b(n, n) + \frac{1}{4}(α(n) − \frac{1}{2}a(n, n)) + \frac{1}{8n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1}(2^{F_{ij}} + 2^{G_{ij}} + 2^{H_{ij}}).  (11)

Let us begin with

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{H_{ij}}.

Here we are concerned with the permutations σ^{i}τ^{j}ρθζ for (i, j) ∈ {0, 1, …, n − 1}^{2}. We will need some multiplication rules for the permutations σ, τ, ρ, θ, and ζ, specifically

στ = τσ, σθ = θσ, τρ = ρτ, ρθ = θρ, σρ = ρσ^{−1}, τθ = θτ^{−1},

and

σζ = ζτ, τζ = ζσ, ρζ = ζθ, θζ = ζρ.

It follows that (with τ^{−i} := (τ^{−1})^{i})

σ^{i}τ^{j}ρθζ = σ^{i}τ^{j}ζθρ = ζτ^{i}σ^{j}θρ = ζθτ^{−i}σ^{j}ρ = ζθρτ^{−i}σ^{−j},

and hence

(σ^{i}τ^{j}ρθζ)^{2} = (σ^{i}τ^{j}ρθζ)(ζθρτ^{−i}σ^{−j}) = σ^{i−j}τ^{−i+j} = (στ^{−1})^{i−j} = (σ^{−1}τ)^{−i+j}. (12)

In particular, if i ∈ {0, 1, …, n − 1}, then the permutation σ^{i}τ^{i}ρθζ is of order 2. Furthermore, under this permutation, the entry in position (k, l) moves to position (n − 1 − [l + i], n − 1 − [k + i]), where, as before, [r] := (r mod n) ∈ {0, 1, …, n − 1}. Thus, (k, l) is a fixed point if and only if

(k, l) = (n − 1 − [l + i], n − 1 − [k + i]).  (13)

For each k ∈ {0, 1, …, n−1} there is a unique l ∈ {0, 1, …, n−1} (namely l := n−1−[k+i]) such that (13) holds; indeed,

n − 1 − [l + i] = n − 1 − [n − 1 − [k + i] + i] = n − 1 − [n − 1 − (k + i) + i]
= n − 1 − [n − 1 − k] = n − 1 − (n − 1 − k) = k.

Thus, σ^{i}τ^{i}ρθζ with i ∈ {0, 1, …, n − 1} is of order 2 and has exactly n fixed points, hence \binom{n}{2} transpositions. This implies that H_{ii} = n(n + 1)/2 for such i.

Now we let (i, j) ∈ {0, 1, …, n − 1}^{2} be arbitrary but with i ≠ j. Let us generalize (12) to

(σ^{i}τ^{j}ρθζ)^{2d} = σ^{(i−j)d}τ^{(−i+j)d} = ((στ^{−1})^{i−j})^{d} = ((σ^{−1}τ)^{−i+j})^{d},
(σ^{i}τ^{j}ρθζ)^{2d+1} = σ^{(i−j)d+i}τ^{(−i+j)d+j}ρθζ.

The proof proceeds much like the proof of Theorem 1. Specifically, σ^{i}τ^{j}ρθζ is of order 2d, where d := n/ gcd(|i − j|, n). All cycles have length d or 2d. In fact, if d is odd, there are n/d cycles of length d and n(n − 1)/(2d) cycles of length 2d. If d is even, there are n^{2}/(2d) cycles, all of length 2d. And for a given (i, j) ∈ {0, 1, …, n − 1}^{2}, there are n pairs (k, l) ∈ {0, 1, …, n − 1}^{2} such that [k − l] = [|i − j|]. We arrive at the conclusion that

\frac{1}{8n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{H_{ij}} = \frac{1}{8n^{2}} ∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{E_{ij}} = \frac{1}{4}(α(n) − \frac{1}{2}a(n, n)).  (14)

Next we evaluate

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{F_{ij}} = ∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{G_{ij}},  (15)

where the equality holds by symmetry. We consider the permutations σ^{i}τ^{j}ρζ for (i, j) ∈ {0, 1, …, n − 1}^{2}. From the multiplication rules, it follows that

σ^{i}τ^{j}ρζ = ζθτ^{−i}σ^{j}

and hence

(σ^{i}τ^{j}ρζ)^{2} = (σ^{i}τ^{j}ρζ)(ζθτ^{−i}σ^{j}) = σ^{i}τ^{j}ρθτ^{−i}σ^{j} = σ^{i−j}τ^{i+j}ρθ = θρσ^{−i+j}τ^{−i−j}, (16)

which implies

(σ^{i}τ^{j}ρζ)^{4} = (σ^{i−j}τ^{i+j}ρθ)(θρσ^{−i+j}τ^{−i−j}) = e.

So the permutation σ^{i}τ^{j}ρζ is of order 4. The entry in position (k, l) moves to position ([l + j], n − 1 − [k + i]) under this permutation. Thus, (k, l) ∈ {0, 1, …, n − 1}^{2} is a fixed point of σ^{i}τ^{j}ρζ if and only if

(k, l) = ([l + j], n − 1 − [k + i]).

There is a solution (k, l) if and only if there exists l ∈ {0, 1, …, n − 1} such that, with k := [l + j], we have n − 1 − [k + i] = l or, equivalently,

[l + i + j] = n − 1 − l.  (17)

When i + j ≤ n − 1, (17) is equivalent to

l + i + j = n − 1 − l or l + i + j − n = n − 1 − l

or to

l = (n − 1 − i − j)/2 or l = (2n − 1 − i − j)/2.

If n is odd and i + j is odd, then there is one fixed point, (k, l) = ([(2n − 1 − i + j)/2], [(2n − 1 − i − j)/2]). If n is odd and i + j is even, then there is one fixed point, (k, l) = ([(n − 1 − i + j)/2], [(n − 1 − i − j)/2]). If n is even and i + j is odd, then there are two fixed points, namely

(k, l) = ([(n − 1 − i + j)/2], [(n − 1 − i − j)/2]),
(k, l) = ([(2n − 1 − i + j)/2], [(2n − 1 − i − j)/2]).

Finally, if n is even and i + j is even, then there is no fixed point.

When i + j ≥ n, (17) is equivalent to

l + i + j − n = n − 1 − l or l + i + j − 2n = n − 1 − l

or to

l = (2n − 1 − i − j)/2 or l = (3n − 1 − i − j)/2.

If n is odd and i + j is odd, then there is one fixed point, (k, l) = ([(2n − 1 − i + j)/2], [(2n − 1 − i − j)/2]). If n is odd and i + j is even, then there is one fixed point, (k, l) = ([(3n − 1 − i + j)/2], [(3n − 1 − i − j)/2]) = ([(n − 1 − i + j)/2], [(n − 1 − i − j)/2]). If n is even and i + j is odd, then there are two fixed points, namely

(k, l) = ([(2n − 1 − i + j)/2], [(2n − 1 − i − j)/2]),
(k, l) = ([(n − 1 − i + j)/2], [(n − 1 − i − j)/2]).

Finally, if n is even and i + j is even, then there is no fixed point. Notice that the results are the same for i + j ≥ n as for i + j ≤ n − 1.

Using (16), under the permutation (σ^{i}τ^{j}ρζ)^{2}, the entry in position (k, l) moves to position (n − 1 − [k + i − j], n − 1 − [l + i + j]). Thus, (k, l) ∈ {0, 1, …, n − 1}^{2} is a fixed point of (σ^{i}τ^{j}ρζ)^{2} if and only if

(k, l) = (n − 1 − [k + i − j], n − 1 − [l + i + j]).

A necessary and sufficient condition on (k, l) is (17) together with [k + i − j] = n − 1 − k. Solutions have l as before. On the other hand, k must satisfy

k + i − j − n = n − 1 − k, k + i − j = n − 1 − k, or k + i − j + n = n − 1 − k,

or equivalently,

k = [(n − 1 − i + j)/2] or k = [(2n − 1 − i + j)/2].

If n is odd, the only fixed points of (σ^{i}τ^{j}ρζ)^{2} are those already shown to be fixed points of σ^{i}τ^{j}ρζ. If n is even and i + j is odd, there are two fixed points of (σ^{i}τ^{j}ρζ)^{2} that are not fixed points of σ^{i}τ^{j}ρζ, namely

(k, l) = ([(n − 1 − i + j)/2], [(2n − 1 − i − j)/2]),
(k, l) = ([(2n − 1 − i + j)/2], [(n − 1 − i − j)/2]).

Finally, there are no fixed points when n is even and i + j is even.

Consequently, if n is odd, then the permutation σ^{i}τ^{j}ρζ, which is of order 4, has only one fixed point. Therefore, it has one cycle of length 1 and (n^{2} − 1)/4 cycles of length 4. Thus,

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{F_{ij}} = n^{2}2^{(n^{2}+3)/4}.

For even n, if i + j is odd, then the permutation σ^{i}τ^{j}ρζ has two cycles of length 1 and one cycle of length 2, and the remaining cycles are of length 4. If i + j is even, then all cycles of the permutation σ^{i}τ^{j}ρζ are of length 4, hence there are n^{2}/4 of them. Thus,

∑_{i=0}^{n−1} ∑_{j=0}^{n−1} 2^{F_{ij}} = \frac{1}{2}n^{2}2^{(n^{2}−4)/4+3} + \frac{1}{2}n^{2}2^{n^{2}/4} = 5n^{2}2^{n^{2}/4−1}.

These results, together with (3), (10), (11), (14), and (15), yield (4).

Finally, recall that we have assumed that n ≥ 3. We notice that the formula (4) gives β(1) = 2 and β(2) = 6, which are correct, as we can see by direct enumeration.

In the derivation of (2) in [1], the proof requires m, n ≥ 3 because the group D_{m} × D_{n} used in the application of Pólya’s enumeration theorem (D_{m} being the dihedral group of order 2m), is incorrect if m or n is 1 or 2. If m = 2, row rotation and row reflection are the same, so the latter is redundant. Thus, D_{2} should be replaced by C_{2}, the cyclic group of order 2. The reason (2) is still valid is that b_{1}(2, n) = b_{2}(2, n) and b_{3}(2, n) = b_{4}(2, n), as is easily verified. If m = 1, again row reflection is redundant, so D_{1} should be replaced by C_{1}. Here (2) remains valid because b_{1}(1, n) = b_{2}(1, n) and b_{3}(1, n) = b_{4}(1, n). A similar remark applies to n = 2 and n = 1, except that here b_{1}(m, 2) = b_{3}(m, 2), b_{2}(m, 2) = b_{4}(m, 2), b_{1}(m, 1) = b_{3}(m, 1), and b_{2}(m, 1) = b_{4}(m, 1).

References

[1] S. N. Ethier, Counting toroidal binary arrays, J. Integer Sequences 16 (2013), Article 13.4.7.

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

[3] 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: toroidal array, Euler’s phi function, group action, orbit, Pólya’s enumeration theorem.

(Concerned with sequences \underline{A179043}, \underline{A184271}, \underline{A209251}, \underline{A222188}, \underline{A255015}, and \underline{A255016}.)

Received February 19 2015; revised version received June 3 2015. Published in Journal of Integer Sequences, July 16 2015.

Return to Journal of Integer Sequences home page.