Domino Tilings of 2 × n Grids (or Perfect Matchings of Grid Graphs) on Surfaces

sarah-marie belcastro Mathematical Staircase, Inc. Holyoke, MA 01040 USA and Department of Mathematical Sciences Smith College Northampton, MA 01063 USA

              smbelcas@toroidalsnark.net

Abstract

It is well known that the number of edge-labeled perfect matchings of a 2×n planar grid graph is the (n + 1)st Fibonacci number. The number of edge-labeled perfect matchings of grid graphs on surfaces has been computed using Pfaffians, matching polynomials, and generating functions. Here we present an elegant and elementary approach to enumerating edge-labeled perfect matchings of 2×n grid graphs on surfaces representable by opposite-edge-identified quadrilaterals. For simplicity in description, we give proofs using the language of tilings of grids.

1 Introduction

Let R_{n} be the number of ways to tile a 2 × n grid with 2 × 1 tiles. It is well known that R_{n} is the Fibonacci sequence. In this paper, we consider some variations on this classic counting problem, where instead of tiling a standard rectangular grid we tile a 2 × n grid drawn on surfaces. These include 2 × n grids drawn on bracelets (where the height-two sides are identified), cylinders (where the length-n sides are identified), tori (where both pairs of opposing sides are identified), Möbius bands (where the height-two sides are identified with a twist, and where the length-n edges are identified with a twist), Klein bottles (where the boundaries of Möbius bands are identified), and projective planes (where both the height-two sides and the length-n sides are identified with twists).

This problem is of interest in its own right, but also has deep connections to graph theory. There is a 1-1 correspondence between grids on surfaces and graphs on surfaces, given by associating a graph vertex to each square of a grid and associating a graph edge to each grid line between two adjacent squares. In turn, there is a 1-1 correspondence between tilings of grids and perfect matchings of their associated graphs. (A perfect matching is a subset of edges that pairs all of the vertices; every vertex is incident to exactly one edge in the subset.) This view is of interest in computational chemistry, where the number of perfect matchings of a graph is known as the Kekulé number [7]. An excellent and interesting survey about the enumeration of perfect matchings was given by Propp [16].

We review the known results on the number of perfect matchings of m × n grid graphs on surfaces in Section 2, and summarize the various methods of proof used to obtain these results. Then in Section 3, we use the terminology of tilings to give elementary proofs of these results in the 2×n case. Almost nothing is new in this paper except the proofs—where “almost” refers to the fact that we reveal the number of perfect matchings of a 2×n grid graph on a projective plane, and contribute a few new sequences to the On-Line Encyclopedia of Integer Sequences [15] that are referenced here by their A-numbers (e.g., the Fibonacci series is sequence \underline{A000045})—though as far as the author is aware, this is the first comprehensive summary of results on the topic.

2 Background and history

We refer the reader to West’s text [19] for definitions in graph theory used subsequently. Tutte [18] characterized the existence of perfect matchings: a graph G has a perfect matching if and only if for every vertex subset C, the number of odd components of G \ C is less than |C|. There is little known about the number of perfect matchings of a general graph. In fact, the only results that count perfect matchings concern edge-labeled graphs rather than unlabeled graphs (as are considered in this paper).

One of the few general results is due to Wilf, who showed in 1968 [20] that the number of perfect matchings of a graph G with n vertices can be counted using the formula

\frac{1}{(n/2)!} ∑_{e=1}^{|E|} e^{n/2} ∑_{v=0}^{|V |}(−1)^{v}ψ(v, e)  (1)

where ψ(v, e) is the number of induced subgraphs of G with exactly v vertices and e edges. Using (1) reduces the problem to enumerating induced subgraphs, which seems no less difficult, whether one is counting by hand or by computer.

Lovász and Plummer devoted an entire chapter of Matching Theory [10] to counting perfect matchings of graphs. They gave two methods relevant to this paper, described here.

Method 1, for bipartite graphs: Consider graph G with the vertex set partitioned into parts U and V, so that G is bipartite. The biadjacency matrix B has rows indexed by vertices from U and columns indexed by vertices from V, where the entry b_{ij} is the number of edges between vertices u_{i} and v_{j}. The permanent of a matrix is defined much as is the determinant, except that all terms in the cofactor expansion are positive; this prevents cancellation of terms in a biadjacency matrix. The nonzero terms of the permanent of a biadjacency matrix B correspond to perfect matchings of the graph G. Even though Wilf [20] gave a generating function for permanents, this is not a very practical method for counting perfect matchings. Still, the method produces upper and lower bounds.

Theorem 1. [10, Thms. 8.1.3 and 8.1.4] If G is k-regular, bipartite, and has 2n vertices, then the number of perfect matchings of G is at least n!(k/n)^{n}. If G is also simple, then the number of perfect matchings of G is at most (k!)^{n/k}.

Method 2, for arbitrary graphs: Given a digraph G, the skew adjacency matrix of G is the usual adjacency matrix except that a_{ij} is 1 when v_{i} points to v_{j} and is −1 when v_{j} points to v_{i}. The Pfaffian of a skew-symmetric matrix is the square root of its determinant.

Now we can assign directions to an undirected graph and compute the associated Pfaffian. This will always give a lower bound on the number of perfect matchings of G. A Pfaffian orientation is an assignment of directions to graph edges such that the associated Pfaffian counts the number of perfect matchings of G.

Theorem 2. [10, Thm. 8.3.5] Every graph without a subdivision of K_{3,3} has a Pfaffian orientation.

There is a much more technical condition that describes which bipartite graphs have Pfaffian orientations.

2.1 Results and extensions using the Pfaffian

Kasteleyn [9] used the Pfaffian method to compute the number of perfect matchings of an m × n rectangular grid. The result is

2^{mn/2} ∏_{k=1}^{m} ∏_{ℓ=1}^{n} (cos^{2} (\frac{πk}{m + 1}) + cos^{2} (\frac{πℓ}{n + 1}))^{1/4} .  (2)

Setting m = 2 and simplifying (via Mathematica [21] and then by hand) produces

2^{n} ∏_{k=1}^{n} \sqrt{cos^{2} (\frac{kπ}{n + 1}) + \frac{1}{4}}.  (3)

Now recall that the number of perfect matchings for m = 2 is the Fibonacci sequence (\underline{A000045}); sadly, expression (3) is not obviously equivalent to the Binet formula (though it is interesting to see such a different formula for the Fibonacci numbers). This shows the need, or at least the desire, for a more elementary approach in specific cases.

Aigner [1, Ch. 10.1] described the Pfaffian approach and gave a proof that every planar graph has a Pfaffian orientation. He was disturbed by Kasteleyn’s formula (2) because it does not seem to produce integers (let alone Fibonacci numbers in the m = 2 case), and used Chebyshev polynomials and a theorem on resultants to obtain a new formula for the n×n case that at least produces integers. This formula is a power of two times the square of a determinant of a matrix with binomial coefficient entries. (It is unwieldy and has 2 cases, and so is not reproduced here.)

Yan and Zhang [22] considered planar graphs with reflective symmetry and no vertices lying on the axis of reflection, and found ways to reduce the computational complexity of finding the Pfaffian for such graphs. They also computed the number of perfect matchings of G × K_{2} in terms of a Pfaffian orientation for G, for certain special G. This forms an interesting contrast with Ciucu, who considered planar graphs with reflective symmetry and an even number of vertices lying on the axis of reflection [4]. He obtained the number of perfect matchings of such a graph as a product of the numbers of perfect matchings of two subgraphs obtained by certain edge deletions near the axis of reflection, times a factor of two. His proof technique uses the matching generating function. He obtained a similar result under the additional constraints that the graph is invariant under a rotation of π radians and certain paths contain even numbers of edges.

More recently, Ciucu used permanents and determinants to count the perfect matchings of a special class of planar graphs [3, Thm. 2.1]. Combining this result with his 1997 work [4] and some eigenvalue computations, he obtained a formula for the number of perfect matchings of a 2r × n cylindrical grid (here 2r is the girth of the cylinder), namely

2^{n−2⌊n/2⌋} ∏_{k=1}^{⌊n/2⌋} (1 + (cos \frac{kπ}{n+1} + \sqrt{1 + cos^{2} \frac{kπ}{n+1}} )^{2r} )(1 + (cos \frac{kπ}{n+1} − \sqrt{1 + cos^{2} \frac{kπ}{n+1}} )^{2r} ). (4)

He then used an extension of his 1997 work [4] with Kasteleyn’s work [9] to get a formula for the number of perfect matchings of a (2r + 1) × n (n even) cylindrical grid,

∏_{k=1}^{n/2} ∏_{j∈\{1,3,...,2r+1\}} (4 cos^{2} \frac{jπ}{4r + 2} + 4 cos^{2} \frac{kπ}{n + 1}) ,  (5)

and finally combined these two formulae into a monstrosity of a product of 4th roots of products of mth powers of sums of roots of cosines.

For the 2r = 2 case, Mathematica does not simplify either (4) or (5) (after a reasonable amount of computation), but for small values of n outputs the Pell sequence (\underline{A000129}), which agrees with our results in Theorem 4. When n = 2, Mathematica does not produce a simplification of the 2r + 1 formula (5), but gives a version of the 2r formula (4) equivalent to the Hosoya-Harary formula [7] for \underline{A068397} described in Section 2.2.

Tesler [17] cited Kasteleyn [9] as having computed the number of perfect matchings of an m × n toroidal grid by using a linear combination of four Pfaffians, and as having hinted at a way to compute the number of perfect matchings for more general graphs embedded on orientable surfaces. In his excellent and clearly written paper, Tesler went on to actually give a method for computing the number of perfect matchings of a graph embedded on any compact surface (orientable or nonorientable). The method involves computing a linear combination of a large number (exponential in the genus) of Pfaffians.

As a specific example, Tesler computed the number of perfect matchings for an edgeweighted m × n Möbius grid. We first consider the case where the twist is on the m side. (His twist is on the n side, so we switch the roles of m, n from his notation here.) In the case where all weights are 1 and m is even, Tesler obtained

Re ((1 − i) ∏_{r=1}^{(m)/2} (F_{n} (2 cos \frac{rπ}{m + 1}) + F_{n−2} (2 cos \frac{rπ}{m + 1}) + 2i(−1)^{r+m/2})) for n odd

(6)

and

∏_{r=1}^{m/2} (F_{n} (2 cos \frac{rπ}{m + 1}) + F_{n−2} (2 cos \frac{rπ}{m + 1}))  for n even,  (7)

where F_{n}(q) = ∑_{j=0}^{⌊n/2⌋} \binom{n − j}{j}q^{n−2j} is a q-analogue of the Fibonacci numbers. (Mathematica

does not produce a substantial simplification.)

For the m = 2 case, Mathematica simplifies (6) and (7) to

Re ((1 − i) (\frac{L_{n} − F_{n}}{2} + F_{n+1} + 2i)) (8) and \frac{L_{n} − F_{n}}{2} + F_{n+1} (9)

respectively, where L_{n} is the nth Lucas number (\underline{A000204}). The expressions (8) and (9) are not exactly recognizable, but at least some Fibonaccïshness is evident; this is expected, given the results in Sections 2.2 and 3. Excellent! The corresponding sequences are \underline{A162483} and \underline{A005248}, respectively.

Now, when the twist is on the n side, Tesler’s formulae are

2 ∏_{r=1}^{(n−1)/2} (F_{m} (2 cos \frac{rπ}{n + 1}) + F_{m−2} (2 cos \frac{rπ}{n + 1}))  for n odd  (10)

and

∏_{r=1}^{n/2} (F_{m} (2 cos \frac{rπ}{n + 1}) + F_{m−2} (2 cos \frac{rπ}{n + 1}))  for n even.  (11)

For the m = 2 case, Mathematica simplifies (10) and (11) to

2 ∏_{r=1}^{\frac{n−1}{2}} (4 cos^{2} (\frac{πr}{n + 1}) + 2) (12) and  ∏_{r=1}^{\frac{n}{2}} (4 cos^{2} (\frac{πr}{n + 1}) + 2) , (13)

respectively. Expressions (12) and (13) are even less recognizable than expressions (8) and (9), and (12) and (13) do not obviously produce integers, but do in fact produce the sequences \underline{A052530} and \underline{A079935}, respectively; these sequences are each defined by the straightforward recurrence a_{n} = 4a_{n−1} −a_{n−2}. We show that our computations for Möbius bands in Theorem 8 give this same recurrence in Corollary 9.

Lu and Wu [11] extended Kasteleyn’s and Tesler’s uses of the Pfaffian to compute the number of perfect matchings of edge-weighted m×n grid graphs on Möbius bands and Klein bottles. Their extension involves the use of imaginary weightings to simplify the computation of the Pfaffian. Because their work appears in the physics literature, their results are not well known among mathematicians and are reproduced here for the case of edges with weight 1 and m even.

For the Möbius band, with the twist on the m side, the number of perfect matchings is computed to be

Re ((1 − i) ∏_{s=1}^{m/2} ∏_{r=1}^{n} (2i(−1)^{m/2+s+1} sin \frac{(4r − 1)π}{2n} + 2 cos \frac{sπ}{m + 1}))  for n odd (14)

and

∏_{s=1}^{m/2} ∏_{r=1}^{n/2} (4 sin^{2} \frac{(4r − 1)π}{2n} + 4 cos^{2} \frac{sπ}{m + 1})  for n even.  (15)

The formulae (14) and (15) can be shown to be equivalent to Teslers’ formulae (6) and (7) [11].

For the Klein bottle, with the twist on the m side, the number of perfect matchings is computed to be

Re ((1 − i) ∏_{s=1}^{m/2} ∏_{r=1}^{n} (2i(−1)^{m/2+s+1} sin \frac{(4r − 1)π}{2n} + 2 sin \frac{(2s − 1)π}{m} ))  for n odd (16)

and

∏_{s=1}^{m/2} ∏_{r=1}^{n/2} (4 sin^{2} \frac{(4r − 1)π}{2n} + 4 sin^{2} \frac{(2s − 1)π}{m} )  for n even.  (17)

None of (14), (15), (16), or (17) simplify in the m = 2 case; even Mathematica offers nothing better than a simple hand calculation produces. Interestingly, the formulae for the Möbius band and Klein bottle for m = 2, n odd actually generate the appropriate sequences (\underline{A020878} and \underline{A162485}) for all positive integer n. Thus, Lu and Wu’s formula for the number of perfect matchings of an m × n grid graph on a Möbius band for m even and n odd is only equivalent to Tesler’s formula when n is odd! For m = 2, n even, Lu and Wu’s formulae produce the sequences \underline{A005248} (bisection of the Lucas numbers) for the Möbius band and \underline{A003499} (bisection of the companion Pell numbers) for the Klein bottle.

Now for the twist on the other side of the rectangle. For the Möbius band, with the twist on the n side, Lu and Wu computed the number of perfect matchings to be

∏_{s=1}^{m/2} ∏_{r=1}^{⌈n/2⌉} (4 sin^{2} \frac{(4s − 1)π}{2m} + 4 cos^{2} \frac{rπ}{n + 1}) .  (18)

For the Klein bottle, with the twist on the n side, the number of perfect matchings is computed to be

∏_{s=1}^{m/2} ∏_{r=1}^{⌈n/2⌉} (4 sin^{2} \frac{(4s − 1)π}{2m} + 4 sin^{2} \frac{(2r − 1)π}{n} ) .  (19)

As before, formulae (18) and (19) do not simplify significantly in the m = 2 case, but they generate the appropriate sequences (\underline{A048788} for the Möbius band and \underline{A351635} for the Klein bottle).

Lu and Wu’s work was used by a group at Reed College [6] to show that weighting certain edges of 2m × 2n planar grid graphs, and counting perfect matchings including these edges with multiplicity, counts perfect matchings of 2m × 2n grid graphs on the Möbius band (see \underline{A103997}).

Finally, Cimasoni [2] used vector bundles over Lie groups (spin and pin^{−} structures) with Kasteleyn orientations to derive a closed formula for computing the number of perfect matchings of a graph embedded on any compact surface (orientable or nonorientable). The idea is to examine a basis for the first homology group of the underlying surface and track the way the basis representatives intersect with the embedded graph relative to a chosen Kasteleyn orientation and use this to produce a specific set of Pfaffians. The computation is of equal complexity to that of Tesler’s.

2.2 Results about 2 × n grid graphs on surfaces

Hosoya and Harary considered the numbers of perfect matchings of grid graphs on 2 × n bracelets and Möbius bands, which they called cyclic ladder graphs and Möbius ladder graphs, respectively [7]. Their approach used a so-called operator technique to produce matching polynomials, and the closed forms obtained, respectively, are

((1 + \sqrt{5})/2)^{n} + ((1 − \sqrt{5})/2)^{n} + 1 + (−1)^{n}  (20)

and

((1 + \sqrt{5})/2)^{n} + ((1 − \sqrt{5})/2)^{n} + 1 − (−1)^{n}  (21)

(sequences \underline{A068397} and \underline{A020878} respectively). However, the authors found (20) and (21) suboptimal and so they created two new families of graphs, one containing the cyclic ladder graphs for odd n and Möbius ladder graphs for even n, and the other containing the remaining cyclic ladder and Möbius ladder graphs. This produced simpler recursions, using Lucas numbers, for the numbers of perfect matchings of the new families of graphs (and corresponding sequences \underline{A000032} and \underline{A000211}).

McSorley considered only Möbius ladder graphs and counted many different structures thereof [14]. He used a direct counting technique that produced a variety of generating functions, and produced the same formulae as did Hosoya and Harary [7] for the number of perfect matchings.

3 Variations and their elementary proofs

We now switch our terminology to that of tilings of grids rather than perfect matchings of grid graphs. As a preview of the technique we will use repeatedly in this section, let us consider the proof that R_{n}, the number of ways to tile a 2 × n grid with 2 × 1 tiles, is the Fibonacci sequence (\underline{A000045}). Figure 1 shows R_{1} = 1 and R_{2} = 2. Let a fault in a grid be a grid line crossed by no tiles. Notice that a 2 × n grid has its last vertical fault either after the (n − 1)st tile or after the (n − 2)nd tile. In the former case, the number of tilings of the grid is R_{n−1} and in the latter case, the number of tilings is R_{n−2}. Thus, R_{n} = R_{n−1} + R_{n−2}; and, because the initial values R_{1} and R_{2} are also initial values for the Fibonacci sequence, we have that R_{n} = F_{n+1}.

Figure 1: R_{1} = 1 and R_{2} = 2 demonstrated.

What follows in this section is variations on this situation, i.e., theorems on the number of ways to tile 2 × n grids on surfaces with 2 × 1 tiles.

3.1 Orientable surfaces

We begin by bending a 2 × n grid around into a bracelet and securing it with tape. The tape signifies a choice to consider translates of a tiling as different; this makes the counting of tilings significantly simpler as we need not account for overcounting of rotations of or symmetries within tilings. Additionally, this is consistent with the results in Section 2 that count perfect matchings on labeled graphs. Notice that the corresponding bracelet graph is 3-regular (each vertex has degree 3), simple (no multiple edges or loops) for n > 2, and bipartite exactly when n is even. Figure 2 shows two different representations of a 2 × 13 taped bracelet grid.

Figure 2: A 2 × 13 taped bracelet grid along with a more convenient representation thereof.

Theorem 3. Let B_{n} be the number of ways to tile a 2×n taped bracelet grid with 2×1 tiles. Then

B_{n} = R_{n} + R_{n−2} + 2((n − 1) mod 2) = B_{n−1} + B_{n−2} − 2(n mod 2).

Proof. Consider the tape line on a taped bracelet grid. Given a tiling of the grid, the tape line is either a fault of the tiling or it is not. If it is a fault of the tiling, then there are R_{n} possible tilings. If it is not a fault of the tiling, then two possibilities remain. One is that two horizontal tiles cover the tape line. In this case, the rest of the grid may be tiled in R_{n−2} ways. The other possibility is that exactly one horizontal tile covers (half of the) tape line. As can be seen from the example in Figure 3, such a tile configuration forces the remainder

Figure 3: A 2 × 4 taped bracelet grid, partially tiled and with half of the tape line covered with a horizontal tile.

of the tiling; and, this tiling can only be completed when n is even, so that (n − 1) ≡ 1 (mod 2). As either the upper or lower half of the tape line may be covered, when such a tiling exists, two such tilings exist. Thus, B_{n} = R_{n} + R_{n−2} + 2((n − 1) mod 2).

We may instead consider neighborhoods of the tape line on a tiled taped bracelet grid. The eight possible neighborhoods are shown in Figure 4. Consider the two grid squares to the right of the tape to be the beginning of the 2×n grid, and the two grid squares to the left of the tape to be the end of the grid. Then notice that the first two neighborhoods in Figure 4 have faults along the tape and two grid-squares previous; these correspond to tilings of a 2 × (n − 2) bracelet. The second pair of neighborhoods in Figure 4 has faults along the tape Figure 4: The eight possible neighborhoods of the tape on a tiled 2 × n taped bracelet (or Möbius) grid.

and one grid-square previous; these correspond to tilings of a 2 × (n − 1) bracelet. Similarly, the fifth and sixth neighborhoods in Figure 4 have faults one grid-square previous to the tape and three (resp. two) grid-squares previous to the tape; they correspond to tilings of a 2 × (n − 2) (resp. 2 × (n − 1)) bracelet. The last two neighborhoods in Figure 4 each force a particular tiling. Within the first six neighborhoods, three correspond to tilings of a 2×(n−1) bracelet and three to tilings of a 2×(n−2) bracelet. Thus B_{n} = B_{n−1} +B_{n−2} +ϵ, where ϵ is a correction factor to account for the final two neighborhoods (tilings). Those neighborhoods only exist when n is even. They appear in either the set of tilings of a 2 × (n − 1) bracelet (when n is odd) or the set of tilings of a 2 × (n − 2) bracelet (when n is even); so, for n odd we need to remove those two tilings from the expression, and ϵ = −2(n mod 2). This completes the proof.

The recursions from Theorem 3 produce the sequence 1, 5, 4, 9, 11, 20, 29, … (\underline{A068397}) as follows from the closed form given by Hosoya and Harary [7].

Now consider bending a 2 × n grid so that the top and bottom meet, forming a cylinder, and secure this with tape. Notice that the corresponding cylinder graph is bipartite but neither regular nor simple; some vertices are of degree 4 and others of degree 3, and the “vertical” edges each have multiplicity 2, reflecting the two different ways to travel between vertically adjacent vertices (grid cells).

Theorem 4. Let C_{n} be the number of ways to tile a 2×n taped cylinder grid with 2×1 tiles.

Then C_{n} = 2C_{n−1} +C_{n−2}, with corresponding closed form C_{n} = \frac{(1 + \sqrt{2})^{n+1} − (1 − \sqrt{2})^{n+1}}{2\sqrt{2}} .

Proof. The proof is similar to that for the 2 × n rectangular grid, except that there are two possibilities for the placement of each vertical tile (see Figure 5). That is, a 2 × n taped cylinder grid has its last vertical fault either after the (n − 1)st grid squares or after the (n − 2)nd grid squares. In the former case, the number of tilings is 2C_{n−1} because there are two ways to place a vertical tile to cover the remaining two squares, and in the latter case the number of tilings is C_{n−2}. Thus, C_{n} = 2C_{n−1} + C_{n−2}; and, both the recurrence and the initial values C_{1} and C_{2} match the Pell sequence (\underline{A000129}). The closed form for the Pell sequence is well known.

We will now bend a taped bracelet grid so that the top and bottom meet, forming a torus, and secure this with tape. (Equivalently, we could bend a taped cylinder grid around

Figure 5: The two ways to place a vertical tile on a taped cylinder grid.

into a taped toroidal grid.) Notice that the corresponding toroidal grid graph is 4-regular, bipartite exactly when n is even, and not simple (as it has multiple edges).

Theorem 5. Let T_{n} be the number of ways to tile a 2 × n taped toroidal grid with 2 × 1 tiles. Then

T_{n} = C_{n} + C_{n−2} + 2((n − 1) mod 2) = 2T_{n−1} + T_{n−2} − 4(n mod 2).

Proof. This proof of the first recursion is similar to that for the taped bracelet grid, substituting C_{n} for R_{n}.

We may instead consider neighborhoods of the vertical tape line on a tiled taped toroidal grid; this proof is similar to that for the taped bracelet grid. The eight possible neighborhoods

Figure 6: The eight possible neighborhoods of the tape on a tiled 2 × n taped torus (or Klein) grid.

are shown in Figure 6, and these show that T_{n} = 2T_{n−1} + T_{n−2} + δ. Those neighborhoods only exist when n is even, so they both appear in the set of tilings of a 2 × (n − 1) torus when n is odd; so, we need to remove those two tilings from the expression, and then each is counted twice (because of the coefficient of 2 in the expression) so δ = −4(n mod 2).

The recursion from Theorem 5 produces the sequence 2, 8, 14, 36, 82, … (\underline{A162484}).

3.2 Nonorientable surfaces

Now we consider again bending a 2 × n grid around into a bracelet, but give one side a half-twist before securing the sides together with tape. This forms a taped Möbius band grid. Note that the corresponding Möbius grid graph is 3-regular, simple for n > 1, and bipartite exactly when n is odd.

Theorem 6. Let M_{n} be the number of ways to tile a 2 × n taped Möbius grid with 2 × 1 tiles, with the tape on the 2 side, not the n side. Then

M_{n} = R_{n} + R_{n−2} + 2(n mod 2) = M_{n−1} + M_{n−2} − 2((n − 1) mod 2).

Proof. The proof of the first recursion is similar to that for the taped bracelet grid, with the exception that when exactly one horizontal tile covers (half of the) tape line, the forced configuration can only be completed when n is odd (see Figure 7), so that n ≡ 1 (mod 2).

Figure 7: A 2×13 taped Möbius grid, untiled (left) and tiled with an odd-only tiling (right).

For the second recursion, we consider neighborhoods of the tape line on a tiled taped Möbius grid as in Figure 4. The analysis proceeds exactly as in the proof of Theorem 3, so that M_{n} = M_{n−1} + M_{n−2} + ε, where ε is a correction factor to account for the final two neighborhoods (tilings). Those neighborhoods only exist when n is odd, and thus appear in either the set of tilings of 2 × (n − 1) Möbius band or the set of tilings of a 2 × (n − 2) Möbius band; so, for n even we need to remove those two tilings from the expression, and ε = −2((n − 1) mod 2). This completes the proof.

The recursion from Theorem 6 produces the Möbius grid tiling sequence 3, 3, 6, 7, 13, 18, 31, … (\underline{A020878}).

Next, we will bend a taped Möbius grid so that the top meets the bottom, and form a taped Klein bottle grid. Notice that the corresponding Klein grid graph is 4-regular, bipartite exactly when n is odd, and not simple.

Theorem 7. Let K_{n} be the number of ways to tile a 2 × n taped Klein grid with 2 × 1 tiles. (The twist is on the 2 side, not the n side.) Then

K_{n} = C_{n} + C_{n−2} + 2(n mod 2) = 2K_{n−1} + K_{n−2} − 4((n − 1) mod 2).

Proof. The proof is similar to that for the taped toroidal grid, but here that the parity of the forced tilings switches as in the proof of Theorem 6.

The recursion from Theorem 7 produces the sequence 4, 6, 16, 34, 84, 198, … (\underline{A162485}). We could also bend a 2 × n grid into a cylinder, but give the top a half-twist before

securing it to the bottom with tape. This forms a new taped Möbius band grid. Note that the corresponding Möbius grid graph is simple when n is even, bipartite exactly when n is odd, and not regular.

Theorem 8. Let \overline{M}_{n} be the number of ways to tile a 2 × n taped Möbius grid with 2 × 1 tiles, with the tape on the n side of the grid. Then \overline{M}_{n} = \overline{M}_{n−1} + \overline{M}_{n−2} + (n mod 2)\overline{M}_{n−1}, with closed form

\overline{M}_{n} = \frac{2^{− \frac{n}{2} −2}}{\sqrt{3}} (2^{n/2} (\sqrt{2} + 1) (\sqrt{3} + 1) (\sqrt{3} + 2)^{n/2} − (\sqrt{2} − 1) (\sqrt{3} − 1)^{n+1}
+ e^{iπn} ((\sqrt{2} + 1) (\sqrt{3} − 1)^{n+1} − 2^{n/2} (\sqrt{2} − 1) (\sqrt{3} + 1) (\sqrt{3} + 2)^{n/2})) .

In contrast to the orientable cases and the short-end-twist nonorientable cases, here we will examine a neighborhood of the center of the grid instead of a neighborhood of the tape or a neighborhood of the boundary.

Proof. We proceed in two cases, for even n and for odd n.

Figure 8: Some of the possible neighborhoods of the central line in a 2 × n, n even long-side-tape Möbius band or Klein bottle or projective planar grid.

Figure 9: The remaining possible neighborhoods of the central line in a 2 × n, n even longside-tape Möbius band (or Klein bottle or projective planar) grid.

For the case of even n, there is a central vertical line with 2 × \frac{n}{2} squares on either side. There are ten possible neighborhoods of this line, six of which include vertical tiles as shown in Figure 8, and four that use only horizontal tiles as shown in Figure 9. However, closer examination shows that the final two neighborhoods shown in Figure 9 cannot be realized on a Möbius band: Each forces the remainder of the tiling, but must leave blank squares (or have half-tiles hanging off the sides). This reduces the cases to eight central-line neighborhoods to consider.

Now notice that each of the six vertical-tile-including neighborhoods can be replaced by a particular 2×1 region, as shown in Figure 11, to produce from a 2×n long-side-tape Möbius band grid a 2 × (n − 1) long-side-tape Möbius band grid. (Conveniently, these are the six possible central colunns of a 2 × n, n odd long-side-tape Möbius band grid, as exhibited in Figure 10.) Similarly, for each of the two only-horizontal-tile neighborhoods, the region can be removed from a 2 × n long-side-tape Möbius band grid to produce a 2 × (n − 2) long-side-tape Möbius band grid as shown in Figure 12. These operations are reversible, so we have a pair of bijections that shows for even n, \overline{M}_{n} = \overline{M}_{n−1} + \overline{M}_{n−2}.

Figure 10: Possible central columns in a 2 × n, n odd long-side-tape Möbius band (or Klein bottle or projective planar) grid.

Figure 11: One-to-one correspondence between neighborhoods of the central line in a 2 × n, n even long-side-tape Möbius band (or Klein bottle or projective planar) grid and central columns of a 2 × n, n odd long-side-tape Möbius band (or Klein bottle or projective planar) grid.

For the case of odd n, we examine the central column of two grid squares. There are six ways this region can be tiled, and they can be grouped into three pairs, exhibited at left, in center, and at right in Figure 10. Note that the left two tilings each use a single tile. There is a one-to-one correspondence between 2 × n tilings with these central columns and 2 × (n − 1) tilings with a central fault line, as shown at top in Figure 13. Consider now the two center tilings in Figure 10. Each is included in two different 2 × 3 neighborhoods of the center, shown at the bottom of Figure 13 and at top in Figure 14; thus, there is a one-to-one correspondence between 2 × n tilings with these central tilings and 2 × (n − 2) tilings with the same two central tilings, and a one-to-one correspondence between 2 × n tilings with these central tilings and 2 × (n − 1) tilings without a central fault line. Recall that every 2 × n, n even long-side-tape Möbius band grid tiling either has a central fault line, or has two tiles crossing the central line. We may conclude that there are two 2 × n long-side-tape Möbius band grid tilings corresponding to each 2 × (n − 1) long-side-tape Möbius band grid tiling, and this accounts for the 2\overline{M}_{n−1} term in our recurrence.

Now examine the two right-hand tilings in Figure 10. Each is included in two different 2×3 neighborhoods of the center, shown in the lower parts of Figure 14. These neighborhoods are in one-to-one correspondence with central tilings of 2×(n−1) long-side-tape Möbius band grids, as also shown in the lower parts of Figure 14. (Note that the matching of corresponding central columns in the middle two correspondences is arbitrary.) Collectively, the six one-to-one correspondences exhibited in Figure 14 show that there is a one-to-one correspondence between 2 × n long-side-tape Möbius band grid tilings and 2 × (n − 2) long-side-tape Möbius Figure 12: One-to-one correspondence between only-horizontal-tile neighborhoods of the central line in a 2 × n, n even long-side-tape Möbius band (or Klein bottle or projective planar) grid.

Figure 13: One-to-one correspondence between neighborhoods of the central column in a 2 × n, n odd long-side-tape Möbius band (or Klein bottle or projective planar) grid and central lines of a 2 × n, n even long-side-tape Möbius band (or Klein bottle or projective planar) grid.

band grid tilings (because their sets of central tilings are the same). This accounts for the \overline{M}_{n−2} term in our recurrence. Thus, we have shown that for n odd, \overline{M}_{n} = 2\overline{M}_{n−1} + \overline{M}_{n−2}.

Together, we have shown that \overline{M}_{n} = \overline{M}_{n−1} + \overline{M}_{n−2} + (n mod 2)\overline{M}_{n−1}, and using Mathematica we obtain the closed form given in the theorem statement.

The recursion from Theorem 8 produces the sequence 2, 3, 8, 11, 30, 41 … (\underline{A048788} offset).

Corollary 9. \overline{M}_{n} = 4\overline{M}_{n−2} − \overline{M}_{n−4}.

Proof. Splitting \overline{M}_{n} = \overline{M}_{n−1}+\overline{M}_{n−2}+(n mod 2)\overline{M}_{n−1} by parity produces the two sequences \overline{M}_{n} = 2\overline{M}_{n−1} + \overline{M}_{n−2} for n odd and \overline{M}_{n} = \overline{M}_{n−1} + \overline{M}_{n−2} for n even. We recurse to get the result, as shown in the following computations:

When n is odd, n − 1 and n − 3 are even, so we have

\overline{M}_{n} = 2\overline{M}_{n−1} + \overline{M}_{n−2}
= 2(\overline{M}_{n−2} + \overline{M}_{n−3}) + \overline{M}_{n−2}
= 3\overline{M}_{n−2} + (2\overline{M}_{n−3} + \overline{M}_{n−4}) − \overline{M}_{n−4}
= 4\overline{M}_{n−2} − \overline{M}_{n−4}.

The computations for even n are similar.

Figure 14: One-to-one correspondence between neighborhoods of the central column in a 2 × n, n odd long-side-tape Möbius band (or Klein bottle or projective planar) grid and central columns of a 2 × n, n odd long-side-tape Möbius band (or Klein bottle or projective planar) grid.

Splitting sequence \underline{A048788} by parity as in the proof produces the sequences 2, 8, 30, … (\underline{A052530}) and 3, 11, 41, … (\underline{A079935}).

We now identify the boundary of the new taped Möbius grid so that it forms a new taped Klein bottle grid. Note that the corresponding Klein grid graph is 4-regular, simple for n even, and not bipartite.

Theorem 10. Let \overline{K}_{n} be the number of ways to tile a 2 × n taped Klein grid with 2 × 1 tiles. (The twist is on the n side.) Then

\overline{K}_{n} = \overline{M}_{n} + \overline{M}_{n−2} + 2(n − 1 mod 2) = \overline{K}_{n−1} + \overline{K}_{n−2} + (n mod 2)\overline{K}_{n−1} − 4(n mod 2).

Proof. We first show that \overline{K}_{n} = \overline{M}_{n} + \overline{M}_{n−2} + 2(n − 1 mod 2). There are \overline{M}_{n} tilings of the new taped Klein bottle grid that do not cross the height-2 tape. There are three possibilities for the neighborhood of the height-2 tape when at least one tile crosses the height-2 tape, as shown in Figure 15. Then for the first neighborhood there are \overline{M}_{n−2} ways to tile the

Figure 15: Neighborhoods of the height-2 tape of the new taped Klein bottle grid for tilings that cross the tape.

remainder of the grid, and exactly one way to complete each of the remaining two tilings— but only in the case that n is even. This completes the proof of the statement.

From this statement, we can show that

\overline{K}_{n} = \overline{K}_{n−1} + \overline{K}_{n−2} + (n mod 2)\overline{K}_{n−1} − 4(n mod 2).

We proceed by induction in two cases, noting first that the base cases can be verified empirically and that our statement is equivalent to the two statements \overline{K}_{even} = \overline{K}_{even−1} + \overline{K}_{even−2} and \overline{K}_{odd} = 2\overline{K}_{odd−1} + \overline{K}_{odd−2} − 4.

Even case:

\overline{K}_{even} = \overline{M}_{even} + \overline{M}_{even−2} + 2
= (\overline{M}_{even−1} + \overline{M}_{even−2}) + \overline{M}_{even−2} + 2
= \overline{M}_{even−1} + (\overline{M}_{even−3} + \overline{M}_{even−4}) + \overline{M}_{even−2} + 2
= (\overline{M}_{even−1} + \overline{M}_{even−3}) + (\overline{M}_{even−2} + \overline{M}_{even−4} + 2)
= \overline{K}_{even−1} + \overline{K}_{even−2}.

The computation in the odd case is similar.

However, we also have a bijective proof as follows: The proof is the same as for Theorem 8, except that the two neighborhoods of the center line (for n even) in Figure 9 that were unrealizable for Möbius bands correspond to valid Klein bottles. Each of these neighborhoods determines the remainder of a tiling, and its removal produces a 2 × (n − 2) long-side-tape Klein grid from a 2 × n long-side-tape Klein grid, as shown in Figure 16. Thus for even n, we still have \overline{K}_{n} = \overline{K}_{n−1} + \overline{K}_{n−2}. For odd n, the expression 2\overline{K}_{n−1} + \overline{K}_{n−2} overcounts by 4 (twice for each of the two even forced tilings). Together, we have

\overline{K}_{n} = \overline{K}_{n−1} + \overline{K}_{n−2} + (n mod 2)\overline{K}_{n−1} − 4(n mod 2).

Figure 16: One-to-one correspondence between neighborhoods of the central line in a 2 × n, n even long-side-tape Klein grid and central lines of a 2 × n, n even long-side-tape Klein grid.

The recursion from Theorem 10 produces the sequence 2, 6, 10, 16, 38, 54, 142 … (\underline{A351635}). Finally, we identify the boundary of the new taped Möbius grid with a twist so that it

forms a taped projective planar grid. Note that the corresponding projective planar grid graph is 4-regular, not simple, and bipartite exactly when n is odd.

Theorem 11. Let P_{n} be the number of ways to tile a 2 × n taped projective-planar grid with 2 × 1 tiles. Then

P_{n} = P_{n−1} + P_{n−2} + (n mod 2)P_{n−1} = 2\overline{M}_{n}.

Proof. The proof that the recurrence holds is identical to that of Theorem 8. By direct inspection we can see that the values P_{1} = 2\overline{M}_{1} and P_{2} = 2\overline{M}_{2}, so the result follows.

The recursion from Theorem 11 produces the sequence 4, 6, 16, 22, 60, 82, … (\underline{A048788} offset and doubled). The fact that P_{n} = 2\overline{M}_{n} raises the question of whether there is a simple way to show that there are exactly two 2 × n taped projective-planar grid tilings associated to each 2 × n long-side-taped Möbius grid tilings. While we have not found a simple or straightforward proof, we do provide a bijection here.

Proof. First note that there is a one-to-one correspondence between 2×1-tile tilings of a 2×n long-side-taped Möbius band grid and 2×1-tile tilings of a 2×n taped projective-planar grid where no tiles cross the length-2 tape. Thus it remains to provide a bijection between 2 × 1tile tilings of a 2 × n taped projective-planar grid where at least one tile crosses the length-2 tape and 2 × 1-tile tilings of a 2 × n long-side-taped Möbius band grid. We accomplish this in the following way: Our model for the projective plane has been the standard arrowed 4-gon, and we convert this via surgery to the standard arrowed 2-gon representation (see Figure 17).

Figure 17: From left to right, our usual presentation of the 2 × n taped projective-planar grid; the same presentation with identification arrows explicitly added; the grid re-labeled in preparation for cutting along the grey solid arrow; the grid after cutting along the grey solid arrow and gluing the double-arrowed sides; the grid after gluing the single-arrowed sides and the open-arrowed sides.

We can consider the possible neighborhoods of the length-2 tape before and after this transformation, as shown in Figure 18. To avoid curved tiles, we use the usual grid representation but with grey lines on the sides to denote the 2-gon representation.

This gives us five types of projective-planar grid tilings that have tilings crossing the length-2 tape. Figure 19 shows that four of these five neighborhoods correspond to types of long-side-taped Möbius band grid tilings in a straightforward way: the number of ways to tile the remaining grid squares is the same in each case.

There are three other types of long-side-taped Möbius band grid tilings, shown in Figure 20 along with three subcases of the fifth type of projective-planar grid tiling from Figure 18. The first subcase bijection is again straightforward.

The second subcase is quickly dispatched with surgery shown in Figure 21.

Figure 18: The five possible projective-planar neighborhoods of the length-2 tape, transformed from the standard 4-gon presentation of the projective plane to the standard 2-gon representation (where the left (resp. right) edges are are top/bottom-identified).

Figure 19: Four of the five types of projective-planar grid tilings that have tilings crossing the length-2 tape, together with corresponding types of long-side-taped Möbius band grid tilings. Note that the association of the two right-hand pairs is arbitrary, and could be interchanged.

The final subcase from Figure 20 requires some finessing: we wish to associate a particular type of 2 × n projective-planar grid tiling (Figure 20, bottom left) with a particular type of 2 × n long-side-taped Möbius band grid tiling (Figure 20, bottom right). First note that by cutting the leftmost and rightmost tiles from the 2 × n projective-planar grid tiling type (Figure 20, bottom left), we are left with a 2 × (n − 2) long-side-taped Möbius band grid tiling type (one with a horizontal tile at upper left). Next, note that by cutting the leftmost and rightmost horizontal tile pairs from the 2 × n long-side-taped Möbius band grid tiling type (Figure 20, bottom right), we are left with a 2 × (n − 4) long-side-taped Möbius band grid. This reduces the subcase to a new problem: we seek to show that there are the same number of a particular type of 2 × (n − 2) long-side-taped Möbius band grid tiling and all 2 × (n − 4) long-side-taped Möbius band grid tilings. Equivalently, we want to show that there are the same number of upper-left-horizontal-tile 2 × n long-side-taped Möbius band grid tilings as there are 2×(n−2) long-side-taped Möbius band grid tilings. Figure 22 shows the desired correspondence for two small cases.

Figure 20: The remaining types of projective-planar grid tilings and remaining types of longside-taped Möbius band grid tilings. The top correspondence holds because the numbers of ways to tile the remaining grid squares are the same.

Figure 21: By removing the outer tiles of the given type of projective-planar grid, cutting along the center line and regluing along the tape to obtain a partly tiled 2×(n−2) long-side-taped Möbius band grid, we see that the number of ways to tile the remaining grid squares is the same as that of the indicated partly tiled 2 × n long-side-taped Möbius band grid.

We proceed by induction, assuming that for k ≥ 1, there are the same number of upperleft-horizontal-tile 2 × (n − 2k) long-side-taped Möbius band grid tilings as there are 2 × (n − 2(k + 1)) long-side-taped Möbius band grid tilings. Now consider a generic upperleft-horizontal-tile 2 × n long-side-taped Möbius band grid tiling. There are three possible configurations for the lower left and upper right tiles, as shown in Figure 23.

If the lower left tile crosses the tape, then there are the same number of ways to fill in the remaining squares as there are for a 2 × (n − 2) long-side-taped Möbius band grid with the upper left tile crossing the tape. We can see this by transforming the 2 × n tiling: cut off the outermost 2 × 1 grid rectangles and replace the two fractional tiles with one tile that crosses the tape.

Figure 22: The left parts of the pairings show all long-side-taped Möbius band grid tilings of width 1 and 2; the right parts show all long-side-taped Möbius band grid tilings with a horizontal tile at upper left in widths 3 and 4.

Figure 23: The three possible configurations for the lower left and upper right tiles in an upper-left-horizontal-tile 2 × n long-side-taped Möbius band grid tiling, each paired with a 2 × (n − 2) long-side-taped Möbius band grid configuration that has the same number of tiling completions.

If the lower left tile does not cross the tape, and the upper right tile is vertical, then there are the same number of ways to fill in the remaining squares as there are for a 2 × (n − 2) long-side-taped Möbius band grid with vertical leftmost tile. Again we can see this using a transformation of the 2 × n tiling: cut off the outermost 2 × 1 grid rectangles and replace the two fractional tiles with one vertical tile.

If the lower left tile does not cross the tape, and the upper right tile is horizontal, then the lower right tile is also horizontal. There are the same number of ways to fill in the remaining tiles as there are tilings of a 2 × (n − 4) long-side-taped Möbius band grid. By our inductive hypothesis, this is the same as the number of tilings of an upper-left-horizontal-tile 2 × (n − 2) long-side-taped Möbius band grid. This completes our correspondence, our final subcase, and therefore our proof.

3.3 Conclusion

This cluster of problems and some of the accompanying elementary solutions arose while writing a problem for an admissions exam for an intensive summer program for high-school mathematics students. Subsequently, a selection of this material has been enjoyed by students via interactive lecture at American Regions Mathematics League competitions, and the problems have been explored in group activities at another intensive summer program for high-school mathematics students. It is therefore no exaggeration to state that many of the proofs given herein are understandable and even derivable by high-school students.

There are several extensions one can state, some of which have also been suggested by students. For example, one extension is to a third dimension, where 2 × n × p grids must be tiled with 2 × 1 × 1 or with 2 × k × 1 blocks. This has a fun solution in the case of 2 × 2 × p grids tiled with 2×1×1 blocks (try to find it!). Another generalization is to tiling 3×n grids; this is promising, and the planar grid case is addressed by Hung et al. [8] (see also sequence \underline{A001835}). One might also consider triangular or hexagonal grids. The number of domino tilings of the planar 2 × n triangular grid has a straightforward closed form; hexagonal grids on the Möbius strip and Klein bottle are addressed by Feng, Zhang, and Zhang [5], with unsurprisingly complex formulae. Similarly, considering alternate identifications for the torus or for the Klein bottle, as described by Lu, Zhang, and Lin [12, 13], could be interesting. Elementary treatments of these extensions await further investigation.

References

[1] M. Aigner, A Course in Enumeration, Springer GTM 238, 2007.

[2] D. Cimasoni, Dimers on graphs in non-orientable surfaces, Lett. Math. Phys. 87 (2009), 149–179.

[3] M. Ciucu, Two counterparts of the TFK formula for cylinder graphs, J. Combin. Theory Ser. A 196 (2023), 105722.

[4] M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), 67–97.

[5] X. Feng, L. Zhang, and M. Zhang, Kekulé structures of honeycomb lattice on Klein bottle and Möbius strip, J. Math. Anal. App. 496 (2021), 124790.

[6] L. Florescu, D. Morar, D. Perkinson, N. Salter, and T. Xu, Sandpiles and dominos, Electron. J. Combin. 22(1) (2015), #P1.66.

[7] H. Hosoya and F. Harary, On the matching properties of three fence graphs, J. Math. Chem. 12 (1993), 211–218.

[8] L. V. Hung, T. Yiming, H. Keyi, and J. Qingyang, A simple approach to the tiling problem using recursive sequence, preprint, 2021, https://arxiv.org/abs/2108.08909.

[9] P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209–1225.

[10] L. Lovász and M. D. Plummer, Matching Theory, North-Holland, 1986.

[11] W. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Phys. Lett. A 293 (2002), 235–246.

[12] F. Lu, L. Zhang, and F. Lin, Enumeration of perfect matchings of a type of quadratic lattice on the torus, Electron. J. Combin. 17 (2010), #R36.

[13] F. Lu, L. Zhang, and F. Lin, Dimer statistics on the Klein bottle, Physica A 90 (2011), 2315–2324.

[14] J. P. McSorley, Counting structures in the Möbius ladder, Discrete Math. 184 (1998), 137–164.

[15] OEIS Foundation Inc. (2023), The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org.

[16] J. Propp, Enumeration of matchings: problems and progress, in L. Billera et al., eds., New Perspectives in Geometric Combinatorics, Mathematical Sciences Research Institute series, Vol. 38, Cambridge University Press, 1999, pp. 255–292.

[17] G. Tesler, Matchings in graphs on non-orientable surfaces, J. Combin. Theory Ser. B 78 (2000), 198–231.

[18] W. T. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947), 107–111.

[19] D. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.

[20] H. Wilf, A mechanical counting method and combinatorial applications, J. Combin. Theory 4 (1968), 246–258.

[21] Wolfram Research, Inc., Mathematica, Version 13.2, Champaign, IL (2022).

[22] W. Yan and F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. in Appl. Math. 32 (2004), 655–668.

2020 Mathematics Subject Classification: Primary 05C30; Secondary 05A19, 05A15, 05B45. Keywords: domino tiling, perfect matching, grid graph, Pfaffian, surface.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, \underline{A000204}, \underline{A000211}, \underline{A001835}, \underline{A003499}, \underline{A005248}, \underline{A020878}, \underline{A048788}, \underline{A052530}, \underline{A068397}, \underline{A079935}, \underline{A103997}, \underline{A162483}, \underline{A162484}, \underline{A162485}, and \underline{A351635}.)

Received July 17 2009; revised versions received February 16 2022; February 7 2023; April 11 2023. Published in Journal of Integer Sequences, June 7 2023.

Return to Journal of Integer Sequences home page.