Counting Miura-ori Foldings

Jessica Ginepro^{1} Department of Mathematics University of Connecticut 196 Auditorium Road, Unit 3009 Storrs, CT 06269-3009 USA

               jessica.ginepro@uconn.edu

Thomas C. Hull^{1} Department of Mathematics Western New England University 1215 Wilbraham Road Springfield, MA 01119 USA

                     thull@wne.edu

Abstract

We consider the problem of enumerating the different ways in which the classic Miura map fold crease pattern can be folded flat. Specifically, we aim to count the number M(n, m) of ways to assign mountains and valleys to the creases so that each vertex in a m by n Miura map fold will be able to fold flat. Recurrence relations and closed formulas are found for small n and arbitrary m. We also prove that the array of numbers generated by M(n, m) is equivalent to the number of ways to properly 3-vertex-color a m × n grid graph with one vertex pre-colored.

1Research supported by the National Science Foundation grant EFRI-1240441 “Mechanical Meta-Materials from Self-Folding Polymer Sheets”.

Figure 1: A 4 × 4 Miura-ori with the standard MV assignment. Bold creases are mountains and non-bold creases are valleys.

1 Introduction

In the mathematics of origami (paper folding), enumerating the number of ways in which a crease pattern can fold up is often difficult. Even the seemingly simple postage-stamp folding problem, where the crease pattern is a grid of orthogonal lines, is unsolved [7, 9, 11]. Furthermore, origami enumeration problems emerge naturally from the study of crumpling polymer membranes, where asymptotic results are obtained for restricted families of crease patterns [1]. Also, in the growing field of self-folding structures knowing the possible folded configurations of a given crease pattern is essential for ensuring that a structure folds into the desired shape.

To be more specific, there are different ways one can count origami foldings of a given crease pattern. To use the postage-stamp folding problem as an example, we may try to count the number of different ways we can assign the creases between vertices in the grid to be mountains (convex) or valleys (concave) while being able to fold into a flat square without the paper self-intersecting. This problem is unsolved [7]. Alternatively, we can also count the number of ways the layers of paper can be re-arranged in the final, folded state. This version of the question had been explored more; e.g., Koehler [9] wrote an early paper while Jensen and Guttmann [5] improved algorithms for the one-dimensional stamp folding with layers problem from the point of view of meanders. Lunnon (among others) found algorithms for two-dimensional stamp folding with layers counted [11, 12]. In this paper we focus on the former version of the counting foldings problem and ignore variable layer orders of the origami model.

A general theory for enumerating mountain-valley foldings remains elusive except in the single-vertex case [3]. Therefore finding families of crease patterns for which these problems are tractable is of value. One family that has attracted considerable interest among origami applications in engineering and nature is the Miura map fold, also known as the Miura-ori [13, 14, 16, 19]. Its crease pattern is made of an m × n array of congruent parallelograms in a herringbone pattern. Figure 1 shows this crease pattern; each vertex consists of two congruent acute angles α and two congruent obtuse angles π − α, where 0 < α < π/2.

We can determine how a crease pattern folds up from its mountain-valley (MV) assignment. If we think of our crease pattern C as a connected, embedded graph in the plane, with vertex set V (C) and edge set E(C), where each edge is a line segment of our crease pattern, then a MV assignment is a function μ : E(C) → {−1, 1}, where −1 indicates a valley and +1 a mountain crease. In order for the crease pattern to fold, the function μ must obey certain rules, as will be described in Section 2.

The MV assignment shown in Figure 1 is the standard way in which the Miura-ori is folded flat since it allows the paper to fold and unfold smoothly and rigidly [14]. Many other MV assignments are possible, however, that guarantee each vertex will fold flat. Unfortunately, as we will discuss in Section 5, not every Miura-ori MV assignment that locally folds flat will globally fold flat.

In this paper we discuss enumerating the number of MV assignments for an m×n Miuraori crease pattern that locally fold flat. Specifically, we obtain closed formulas for small values of m and prove a bijection between the general case and the problem of counting the number of ways to 3-vertex color a m × n grid graph with one vertex pre-colored.

2 Local flat folding conditions

In order for a vertex in an origami crease pattern to fold flat (i.e., can be pressed in a book without crumpling or adding new creases), certain geometric and combinatorial rules must be followed [2].

Kawasaki’s theorem states that a vertex v in C will fold flat if and only if the alternating sum of the angles around v, in order, equals zero. In the Miura-ori, we have that this alternating sum about each vertex is

α − α + (π − α) − (π − α) = 0,

and therefore each vertex will fold flat.

Maekawa’s theorem states that if vertex v in C folds flat, then the difference between the number of mountain and the number of valley creases adjacent to v must be two. Note that this holds at every vertex of the example in Figure 1.

Maekawa’s theorem implies that the degree four vertices in the Miura-ori must have three mountain creases and one valley, or vice versa, emanating from them. But not all combinations of three mountains and one valley will work. Using the labeling shown in Figure 2, we cannot have μ(e_{4}) = V and μ(e_{i}) = M for i = 1, 2, 3. Readers are encouraged to try this for themselves and discover how the two acute angles α cannot contain the obtuse angles if e_{1}, e_{2}, and e_{3} creases are all mountains. We refer to this phenomenon as the bird’s foot forcing, since these Miura-ori vertices look like a bird’s foot. The same thing happens if we reverse all the creases (so that μ(e_{4}) = M and the others are V), and so there are only six different MV assignments that can be assigned to a Miura-ori vertex. These are shown in Figure 2.

Figure 2: A Miura-ori vertex and the six MV assignments it can have, following the bird’s foot forcing.

We say that a MV assignment μ : E(C) → {±1} is locally flat foldable if μ matches one of the MV assignments shown in Figure 2 for every vertex of C. In other words, each vertex will fold flat on its own. We then let M(m, n) denote the number of different locally flat foldable MV assignments μ that can be made for a m × n Miura-ori (with m rows and n columns of parallelograms). Figure 2 shows that M(2, 2) = 6. In the next section we develop some closed formulas for cases of M(m, n).

3 Recursions and formulas

First let us calculate M(2, n). This is easily done, since we know that there are six ways to fold a single vertex, so let this vertex be one of our end vertices. Then the vertex adjacent to it has one line already assigned as a mountain or valley, so this vertex is restricted to only having three possible assignments. We then continue on to each adjacent vertex until we get to the (n − 1)-th vertex. The recursion is M(2, n) = 3M(2, n − 1), M(2, 2) = 6. Therefore

M(2, n) = 2 · 3^{n−1}.

Notice that this same argument works to show that M(m, 2) = 2 · 3^{m−1}. In fact, M(m, n) = M(n, m) always holds, but we will delay a proof of this until Section 5.

Looking at a larger case than m×2 presents new problems. For this, a Lemma will prove useful. We say that a Miura-ori vertex points left if the “heel” of the bird’s foot points left, as they do in Figure 2. Points right is defined similarly.

Lemma 1. Let C be the crease pattern for a 2 × n Miura-ori with all the vertices pointing left, and let μ be a MV assignment for C. Let c be the left-most crease in C and let γ be a simple closed curve around all the vertices in C (i.e., crossing all the non-internal creases). Let M_{γ} (resp., V_{γ}) be the number of mountain (resp., valley) creases that γ crosses. Then we have: If μ is locally flat-foldable then μ(c) = (M_{γ} − V_{γ})/2.

As will be seen in the proof, what Lemma 1 is really saying is that M_{γ} − V_{γ} will always equal ±2, just as in Maekawa’s theorem, and that the MV parity of the crease c will control Figure 3: As per Lemma 1, a 2 × 5 Miura-ori with M_{γ} = 6, V_{γ} = 4, and μ(c) = 1 (left) and a 2 × n Miura-ori as used in the proof (right).

Figure 4: The last row of vertices in an m × 3 Miura-ori crease pattern.

the plus/minus parity of M_{γ} − V_{γ}. See Figure 3 for an example. (Note that these properties are not typically present in multiple-vertex flat origami crease patterns. See [4, Activity 23] for examples.)

Proof. We proceed by induction on n. When n = 2 we have only one vertex. If the vertex folds flat, then Maekawa’s theorem gives us that M_{γ} − V_{γ} = ±2 and consulting the six possible MV assignments in Figure 2 confirms the result.

Now let C be a 2 × n Miura-ori with MV assignment μ as in the statement of the lemma and label the external creases c_{1}, …, c_{2n} going clockwise around the crease pattern, with c_{1} the left-most crease. Then the right-most crease is c_{n+1}. Let d be the remaining unlabeled crease of the right-most vertex v, so that v has creases d, c_{n}, c_{n+1} and c_{n+2} going clockwise, as seen in Figure 3.

Suppose that μ is locally flat-foldable in C. Then μ is also locally flat-foldable on the crease pattern C − v, which is a 2 × (n − 1) Miura-ori. Using the induction hypotheses, we may assume without loss of generality that M_{γ′} − V_{γ′} = 2 for γ′ surrounding this 2 × (n − 1) Miura-ori, so that c_{1} is a M. (The M_{γ′} − V_{γ′} = −2 case is attained by simply switching all the Ms to Vs and vice-versa.) We now look at the crease d.

If d is a M then c_{n}, c_{n+1} and c_{n+2} must have 2 Ms and 1 V in order for v to be flat foldable. So if we extend γ′ to γ which includes v then we still have M_{γ} − V_{γ} = 2 since γ no longer crosses d but now crosses c_{n}, c_{n+1}, and c_{n+2} (we subtract an M add 2 Ms and a V). The case where d is a V is similar, and in both cases, we conclude that μ(c_{1}) = (M_{γ} − V_{γ})/2. This completes the proof of the lemma.

We will now develop recursive equations for M(m, 3) by looking at cases. For an m × 3 crease pattern C, denote the creases adjacent to the bottom-most row of two vertices as in Figure 4. Then let

A_{m} = the number of m × 3 MV assignments with μ(e_{4}) = μ(e_{5}), and
B_{m} = the number of m × 3 MV assignments with μ(e_{4}) ≠ μ(e_{5}).

We start with the initial conditions A_{1} = 2 and B_{1} = 2, which makes sense if we think of the 1 × 3 case as having two parallel creases and zero vertices. Then consider A_{m} where we have e_{4} and e_{5} are both Ms and e_{6} is also a M. Then drawing a curve γ as in Figure 4, Lemma 1 tells us that M_{γ} −V_{γ} = 2 and thus exactly one of e_{1}, e_{2}, e_{3} is a M. All three of these cases give us flat-foldable vertices for the bottom row. Two of them have μ(e_{1}) ≠ μ(e_{2}) and thus have B_{m−1} ways to assign Ms and Vs to the remaining creases, while one case has e_{1} and e_{2} being both V, and so has A_{m−1} ways to finish the rest of the crease pattern.

However, if e_{6} is a V, then we have M_{γ} − V_{γ} = −2 and then all three of e_{1}, e_{2}, e_{3} are valleys. This gives us A_{m−1} ways to assign Ms and Vs to the remaining creases. Furthermore, the same division of cases would happen if we had chosen e_{4} and e_{5} to both be Vs. Thus,

A_{m} = 2A_{m−1} + 2B_{m−1}.

For B_{m}, let e_{4} be a V and e_{5} be a M. Then if e_{6} is a M we have M_{γ} − V_{γ} = 2, implying that exactly one of e_{1}, e_{2}, e_{3} is a V. All of these cases are locally flat-foldable for these two vertices, giving is two B_{m−1} cases and one A_{m−1} case. If e_{6} is a valley, then, interestingly, e_{1} is forced to be a V by the bird’s foot forcing. Since M_{γ} − V_{γ} = −2, we have that exactly one of e_{2} and e_{3} is a M, giving us one B_{m−1} and one A_{m−1} case. Thus

B_{m} = 2A_{m−1} + 3B_{m−1}.

Then M(m, 3) = A_{m} + B_{m}. Using the standard techniques of solving a system of first-order linear recurrences (e.g., [18, Sec. 7.5]), we obtain the generating function (1−x)/(1−5x+2x^{2}) for M(m, 3). The zeros of the denominator are α_{±} = (5 ± \sqrt{17})/4, giving us the closed form

M(m, 3) = c_{+}(1/α_{+})^{m} + c_{−}(1/α_{−})^{m}

where c_{±} = (17 ± 3\sqrt{17})/34.

The m × 4 and m × 5 cases are handled similarly, but with many more cases and details to check, which we skip here for brevity. For m × 4 we let the bottom-most creases be e_{1} e_{2}, and e_{3} (playing the same role as e_{4} and e_{5} in the previous case) and let

A_{m} = the number of MV assignments with μ(e_{1}) = μ(e_{2}) = μ(e_{3}),
B_{m} = the number of MV assignments with μ(e_{1}) = μ(e_{2}) ≠ μ(e_{3}),
C_{m} = the number of MV assignments with μ(e_{1}) = μ(e_{3}) ≠ μ(e_{2}), and
D_{m} = the number of MV assignments with μe_{1} ≠ μ(e_{2}) = μ(e_{3}).

Examining these cases carefully results in the following first-order recurrences:

A_{m} = 2A_{m−1} + B_{m−1} + C_{m−1} + D_{m−1} B_{m} = A_{m−1} + 2B_{m−1} + 2C_{m−1} + 2D_{m−1} C_{m} = A_{m−1} + 3B_{m−1} + 3C_{m−1} + D_{m−1} D_{m} = A_{m−1} + 2B_{m−1} + 2C_{m−1} + 2D_{m−1}, and A_{1} = B_{1} = C_{1} = D_{1} = 2. Once again, we obtain a generating function for M(m, 4) = A_{m} + B_{m} + C_{m} + D_{m}:

\frac{4 − 12x + 6x^{2}}{3 − 27x + 45x^{2} − 18x^{3}} .

The denominator of this has zeros α_{1} ≈ 1.65406, α_{2} ≈ 0.702511, and α_{3} ≈ 0.143432, but their expression using radicals is quite messy. The approximate formula is

M(m, 4) = c_{1}(1/α_{1})^{m} + c_{2}(1/α_{2})^{m} + c_{3}(1/α_{3})^{m}

where c_{1} ≈ 0.0132428, c_{2} ≈ 0.21837, and c_{3} ≈ 1.10172.

The recurrence equations obtained for the m × 5 case using these same methods are: A_{m} = 2A_{m−1} + B_{m−1} + C_{m−1} + D_{m−1} + E_{m−1} B_{m} = A_{m−1} + 2B_{m−1} + C_{m−1} + D_{m−1} + E_{m−1} + F_{m−1} + G_{m−1} + H_{m−1} C_{m} = A_{m−1} + B_{m−1} + 2C_{m−1} + D_{m−1} + E_{m−1} + F_{m−1} + 2G_{m−1} + 2H_{m−1} D_{m} = A_{m−1} + B_{m−1} + C_{m−1} + 2D_{m−1} + E_{m−1} + F_{m−1} + 2G_{m−1} + 2H_{m−1} E_{m} = A_{m−1} + B_{m−1} + C_{m−1} + D_{m−1} + 2E_{m−1} + F_{m−1} + G_{m−1} + H_{m−1} F_{m} = B_{m−1} + C_{m−1} + D_{m−1} + E_{m−1} + 2F_{m−1} + 2G_{m−1} + 2H_{m−1} G_{m} = B_{m−1} + 2C_{m−1} + 2D_{m−1} + E_{m−1} + 2F_{m−1} + 2G_{m−1} + 2H_{m−1} H_{m} = B_{m−1} + 2C_{m−1} + 2D_{m−1} + E_{m−1} + 2F_{m−1} + 2G_{m−1} + 3H_{m−1}. Here the initial m = 1 terms are all 2 and M(m, 5) = A_{m} + B_{m} + ⋯ + H_{m}. Once again

we obtain a generating function:

\frac{2 − 16x + 36x^{2} − 30x^{3} + 8x^{4}}{1 − 16x + 65x^{2} − 92x^{3} + 48x^{4} − 8x^{5}} .

An approximate closed formula can be created from this, although note that the denominator is an irreducible quintic. A closed formula for this system evaded the authors.

4 Coloring bijection

The formulas and recurrences generated thus far can be used to produce the following table of data for M(m, n):

\begin{matrix}n\m & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 6 & 18 & 54 & 162 & 486 & 1458 & 4374 \\ 3 & 18 & 82 & 374 & 1706 & 7782 & 35498 & 161926 \\ 4 & 54 & 374 & 2604 & 18150 & 126534 & 882180 & 6150510 \\ 5 & 162 & 1706 & 18150 & 193662 & 2068146 & 22091514 & 235994086 \end{matrix}

Figure 5: A 3 × 5 grid graph with proper 3-vertex coloring and arrows showing the order of constructing the coloring sequence s_{k}.

This table of numbers fits exactly the sequence \underline{A078099} in the On-Line Encyclopedia of Integer Sequences [20], which encodes T (m, n) = the number of ways of 3-coloring the vertices of a grid graph (with m rows and n columns of vertices) with one vertex pre-colored. This cannot be a mere coincidence.

Our aim in this section is to construct a bijection between Miura-ori locally flat-foldable MV assignments and such grid graph colorings, i.e., that M(m, n) = T (m, n).

Define an m × n grid graph to be a planar grid graph with m rows and n columns of vertices. We will establish a bijection between the number of proper 3-vertex colorings of m × n grid graphs with one vertex pre-colored and the number of locally flat-foldable m × n Miura-ori crease patterns by defining a finite sequence s_{k} for both of them.

Given a properly 3-vertex colored m × n grid graph, let the colors be the elements of ℤ_{3} and let the first element of our sequence, s_{0} be the color of the upper-left vertex, which we assume to be zero (our pre-colored vertex). Then proceed to the right along the first row of vertices, assigning the colors to the sequence terms s_{1} thru s_{n}. Then let s_{n+1} be the color of the right-most vertex in the second row of vertices (directly under the vertex with s_{n}’s color) and proceed to the left. Continue in this way, snaking back-and-forth across the rows of the grid graph to generate the grid graph coloring sequence s_{k}. For example, the grid graph coloring shown in Figure 5 is

s_{k} : 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 1

Let v(s_{i}) denote the vertex whose color was assigned to s_{i}. Note that v(s_{i}) is adjacent to v(s_{i+1}) for i = 1 to mn − 1, so therefore s_{i} ≠ s_{i+1}. Also, vertices directly above and below each other must have different colors. This can be captured in the following relation:

v(s_{i}) is adjacent to v(s_{j}) if j − i = 2n − 1 − (2i mod 2n)

where j > i.

We now describe a way to generate a sequence s_{k} from an m × n locally flat-foldable Miura-ori crease pattern with MV assignment μ : C → {−1, 1}. We will call such a sequence Figure 6: A 3 × 5 Miura-ori crease pattern with MV assignment generates a sequence. Bold creases are mountains and non-bold creases are valleys. This crease pattern generates the Miura-ori sequence s_{k} : 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 1.

a Miura-ori sequence. First orient our crease pattern so that the top row of vertices all point left. Then imagine an m × n grid graph overlaid on our crease pattern so that every parallelogram of our crease pattern has a vertex of the grid graph inside of it, as in a planar dual graph. We then use the same ordering of the vertices as if we were making a coloring sequence for the grid graph. The vertex v(s_{0}) will be in the upper-left face of the crease pattern, and we set s_{0} = 0. Let us denote c_{i} to be the crease between vertices v(s_{i−1}) and v(s_{i}). We then assign the remaining terms of the sequence recursively as follows:

s_{i} ≡ s_{i−1} + μ(c_{i}) (mod 3).

See Figure 6 for an example of creating a Miura-ori sequence.

In the following Lemma we prove that our recursion rule for generating the Miura-ori sequence holds for horizontal creases as well.

Lemma 2. Given a Miura-ori sequence s_{k} generated by an m × n Miura-ori crease pattern, consider non-negative integers i, j with j − i = 2n − 1 − (2i mod 2n) and let d_{i} be the crease between v(s_{i}) and v(s_{j}). Then s_{j} ≡ s_{i} + μ(d_{i}) (mod 3).

Proof. If j − i = 2n − 1 − (2i mod 2n) then j > i and v(s_{i}) is directly above v(s_{j}) in the grid graph that is superimposed on our crease pattern. Telescoping the recursion for s_{j}, we obtain

s_{j} ≡ s_{i} + ∑_{k=i+1}^{j} μ(c_{k}) (mod 3).

Therefore we want to show that μ(d_{i}) = ∑_{k=i+1}^{j} μ(c_{k}). For this, we apply Lemma 1. Let γ be a simple closed curve through the creases, in order, c_{i+1}, …, c_{j}, d_{i}. Then, by Lemma 1 we have

2μ(d_{i}) = M_{γ} − V_{γ} = μ(d_{i}) + ∑_{k=i+1}^{j} μ(c_{k}),

Figure 7: Two Miura-ori vertices that point left with the creases labeled and superimposed grid graph section.

where the second equality is obtained by simply adding all the values of μ along γ. Thus μ(d_{i}) = ∑_{k=i+1}^{j} μ(c_{k}) and we are done.

Lemma 2 shows that every m × n Miura-ori sequence also gives an m × n grid graph coloring sequence with s_{0} = 0, and this correspondence is injective; a given Miura-ori crease pattern with MV assignment will generate a grid graph sequence with a well-defined, proper coloring.

Conversely, given a proper 3-vertex coloring of an m × n grid graph whose upper-left vertex is colored 0 and its coloring sequence s_{k} (where s_{0} = 0), we can overlay the grid onto an m × n Miura-ori crease pattern (with the top row vertices pointing left) and generate a MV assignment from the recurrence s_{i} ≡ s_{i−1} + μ(c_{i}) (mod 3). That is,

μ(c_{i}) = \begin{cases}1, & if s_{i} − s_{i−1} ≡ 1 (mod 3); \\ −1, & if s_{i} − s_{i−1} ≡ 2 (mod 3). \end{cases}

Note, however, that this does not define μ for all the creases in the Miura-ori, but only creases c_{i} between vertices v(s_{i−1}) and v(s_{i}). Nonetheless, the MV assignment μ defined thus far will generate the same sequence s_{k} that the grid graph coloring generated. Therefore we can use the result of Lemma 2 to assign μ for the remaining creases as follows: If crease d_{i} is the crease directly below vertex v(s_{i}) and directly above v(s_{j}) (so that v(s_{i}) and v(s_{j}) are adjacent), then let

μ(d_{i}) = \begin{cases}1, & if s_{j} − s_{i} ≡ 1 (mod 3); \\ −1, & if s_{j} − s_{i} ≡ 2 (mod 3). \end{cases}

Lemma 3. The m × n Miura-ori MV assignment μ created by the above procedure is locally flat-foldable.

Proof. All that needs to be shown is that at each bird’s foot vertex we have that the “heel” crease has the same MV parity as the majority of the creases around the vertex.

Take an arbitrary vertex in the crease pattern, and suppose it points left. Label the creases and consider the section of the superimposed grid graph around the vertex, as in Figure 7. From the construction of μ, we have

s_{i} ≡ s_{i−1} + μ(c_{i}) (mod 3)
s_{j} ≡ s_{i} + μ(d_{i}) (mod 3)
s_{j+1} ≡ s_{j} + μ(c_{j+1}) (mod 3)
s_{j+1} ≡ s_{i−1} + μ(d_{i−1}) (mod 3)

Substituting the first three equations into one another, we obtain s_{j+1} ≡ s_{i−1}+μ(c_{i})+μ(d_{i})+ μ(c_{j+1}) (mod 3), and since each of the μ values are only ±1, we have

μ(d_{i−1}) = μ(c_{i}) + μ(d_{i}) + μ(c_{j+1}).

Therefore, crease d_{i−1}, which is the bird’s foot heel, must have the same MV parity as the majority of the creases at this vertex. The case where the vertex points right is similar.

Therefore we have that the m × n Miura-ori MV assignment generated by a coloring sequence s_{k} is locally flat foldable, and this generated MV assignment is well-defined. That is, this correspondence between proper 3-vertex colorings of an m × n grid graph where the upper-left vertex is colored 0 and m × n Miura-ori locally flat-foldable MV assignments is injective.

We conclude that the correspondence between grid graph colorings with one vertex precolored and Miura-ori locally flat-foldable crease pattern MV assignments is a bijection. Therefore, if we let T (m, n) = the number of proper 3-vertex colorings of an m × n grid graph (m rows and n columns of squares) with the upper-left vertex pre-colored, then we have proven the following:

Theorem 4. T (m, n) = M(m, n) for all m, n ≥ 1.

Unfortunately, there are no known formulas for 3-coloring grid graphs, e.g. the problem of finding the chromatic polynomial of an n × m grid graph is unsolved [6, Problem 14.7]. However, in the OEIS listing for \underline{A078099} a recursive transfer matrix for T (m, n) is given. Specifically, define matrices M(1) = [1],

M(m + 1) = [ \begin{matrix}M(m) & M(m)^{T} \\ 0 & M(m) \end{matrix} ] ,

and W (m) = M(m) + M(m)^{T} (where A^{T} denotes the transpose of A). Then T (m, n) equals the sum of the entries of W (m)^{n−1}. One way to see this is to first note that

W (m + 1) = [ \begin{matrix}W (m) & M(m)^{T} \\ M(m) & W (m) \end{matrix} ] .  (1)

Then think of the rows and columns of W (m) as representing the different equivalence classes C_{i} of ways to vertex-color an m × 1 grid graph with colors in ℤ_{3}, where two such colorings x⃗, y⃗ ∈ ℤ_{3}^{m} are equivalent if either x⃗ + (1)^{m} or x⃗ + (2)^{m} is equivalent to y⃗ (mod 3) (where (i)^{m} denotes the m-dimensional vector with i in every coordinate). Then each equivalence class C_{i} contains three vectors from ℤ_{3}^{m} and W (m) is the adjacency matrix for the graph whose vertices are the classes C_{i} where we connect C_{i} and C_{j} by an edge for every pair of vectors x⃗ ∈ C_{i} and y⃗ ∈ C_{j} that are different in every coordinate. Then finding T (m, n) is a matter of counting the walks of length n − 1 on this graph, i.e., summing the entries of W (m)^{n−1}. Examining the entries of the classes C_{i} reveals a recursive structure in m that explains equation (1).

5 Further observations and questions

One immediate consequence of Theorem 4 is the following:

Corollary 5. M(m, n) = M(n, m) for all m, n ≥ 1.

This simply follows from the symmetry of the grid graph colorings, giving us T (n, m) = T (m, n). Corollary 5 is surprising because the Miura-ori crease pattern itself does not follow this symmetry; an m × n Miura-ori does not look the same as an n × m Miura-ori.

We are fortunate that statistical mechanics results exist for enumerating our m × n grid graph coloring problem for very large m and n. The problem is the same as counting the number of Eulerian orientations on an m × n grid graph on a torus, which is exactly the antiferroelectric model for two-dimensional ice lattices, called the square ice model [10, 15]. In 1967, Lieb used a transfer matrix method to show that a grid graph with N vertices (where N is very large, say 10^{23}) will have

(4/3)^{3N/2}

ways to be properly vertex colored using three colors with one vertex pre-colored. Therefore this gives the number of locally flat-foldable MV assignments for a Miura-ori crease pattern with N parallelograms, where N is very large.

The transfer matrix in equation (1) can be used to find more generating functions for M(m, n) than were shown in Section 3. That is, following Stanley [17, Sec. 14.7], the generating function G_{m}(x) for M(m, n) for a fixed m will be

G_{m}(x) = x ∑_{i,j} \frac{(−1)^{i+j}det(I − xW (m) : j, i)}{det(I − xW (m))},

where (A : j, i) denotes the matrix A with the j-th row and i-th column removed, and the sum ranges over all rows and columns of W (m), which is a 2^{m−1} × 2^{m−1} matrix. Thus calculating G_{m}(x) is computationally expensive. We used Mathematica to find G_{m}(x) up to m = 7 and record the approximate constant and exponential terms (that do not tend to zero) of the generating function sum in Table 1.

constant term exponential term
m = 2  2/3  3
m = 3  0.8638  4.56155
m = 4  0.21837  1.42347
1.10172  6.97196
m = 5 0.0308918  1.32083
0.323552  3.11838
1.39119  10.6829
m = 6 0.0405757  1.20258
0.359996  1.3816
0.00056118  1.68048
0.0523544  2.68963
0.454567  5.94907
1.74463  16.392

constant term exponential term
m = 7 0.0409272  1.42028
0.00119768  1.75517
0.0751216  2.48635
0.00137438  3.12982
0.526551  3.47859
0.0792136  5.14803
0.617056  10.6046
2.17679  25.1741

Table 1: The approximate terms of G_{m}(x) = ∑(constant)(exponent)^{n}, the generating function for M(m, n), up to m = 7.

As mentioned previously, not all of the locally flat-foldable Miura-ori MV assignments are globally flat-foldable. An example is shown in Figure 8. It is simply one of the non-foldable counterexamples to the postage-stamp folding problem reported by Justin [7] modified to be a Miura-ori. To see why it is impossible to fold, note that the vertices labeled v_{1} and v_{2} are Miura-ori vertices with the standard MV assignment, as we saw in Figure 1. On one hand, the mountain creases along the line l_{1} will force the parallelogram faces labeled A and B to be folded inside the Miura-ori vertex v_{1}. On the other hand, the mountain creases along the line l_{2} will force the faces A and B to be folded inside the Miura-ori vertex v_{2}. A and B cannot be folded into both of these two vertices, and thus this MV assignment is impossible to globally fold flat, even though each vertex is flat-foldable.

Such counterexamples are the result of layers of the paper being forced in incompatible orders by the MV assignment across multiple vertices. As in the postage-stamp folding problem, keeping track of such impossible layer orderings is notoriously difficult. One would need to use completely different (and as yet, undiscovered) techniques to modify our M(m, n) formulas to guarantee global as well as local flat-foldability.

Nonetheless, the fact that enumerating locally flat-foldable MV assignments is be equivalent to a graph coloring problem seems natural. Perhaps the methods presented in this paper can be generalized to other families or even to arbitrary flat-foldable crease patterns.

6 Acknowledgments

The authors would like to thank Tomohiro Tachi and Ryuhei Uehara for their suggestion of the non-foldable Miura-ori in Figure 8 (among others), to David Eppstein for pointing us to Figure 8: A locally flat-foldable 5 × 1 Miura-ori MV assignment that is not globally flatfoldable (rotated to conserve space).

the square ice model and reference [10], and to Crystal Wang and an anonymous referee for useful comments and corrections.

References

[1] P. Di Francesco, Folding and coloring problems in mathematics and physics, Bull. Amer. Math. Soc. 37 (2000), 251–307.

[2] T. Hull, The combinatorics of flat folds: a survey, in T. Hull ed., Origami^{3}: Third International Meeting of Origami Science, Mathematics, and Education, A K Peters, 2002, pp. 29–38.

[3] T. Hull, Counting mountain-valley assignments for flat folds, Ars Combin. 67 (2003), 175–188.

[4] T. Hull, Project Origami: Activities for Exploring Mathematics, 2nd ed., CRC Press, 2013.

[5] I. Jensen and A. J. Guttmann, Critical exponents of plane meanders, J. Phys. A 33 (2000), L187–L192.

[6] T. R. Jensen and B. Toft, Graph Coloring Problems, John Wiley & Sons, 1995.

[7] J. Justin, Toward a mathematical theory of origami, in K. Miura, ed., Origami Science and Art: Proceedings of the Second International Meeting of Origami Science and Scientific Origami, Seian University of Art and Design, 1997, pp. 15–29.

[8] H. Kobayashi, B. Kresling, and J. Vincent, The geometry of unfolding tree leaves, Proc. R. Soc. London Ser. B 265 (1998), 147–154.

[9] J. Koehler, Folding a strip of stamps, J. Combin. Theory 5 (1968), 135–152.

[10] E. H. Lieb, Residual entropy of square ice, Physical Review 162 (1967), 162–172.

[11] W. F. Lunnon, A map-folding problem, Math. Comp. 22 (1968), 193–199.

[12] W. F. Lunnon, Multi-dimensional map-folding, The Computer Journal 14 (1971), 75– 80.

[13] L. Mahadevan and S. Rica, Self-organized origami, Science 307 (2005), 1740.

[14] K. Miura, A note on intrinsic geometry of origami, in H. Huzita ed., Proceedings of the First International Meeting of Origami Science and Technology, self-published, 1989, pp. 239–249.

[15] J. Propp, The many faces of alternating-sign matrices, in R. Cori, J. Mazoyer, M. Morvan, and R. Mosseri eds., Discrete Models: Combinatorics, Computation, and Geometry, Discrete Math. Theor. Comput. Sci. Proc., Vol. AA, Maison Inform. Math. Discrèt., 2001, pp. 43–58.

[16] J. L. Silverberg, A. A. Evans, L. McLeod, R. Hayward, T. Hull, C. D. Santangelo, and I. Cohen, Using origami design principles to fold reprogrammable mechanical metamaterials, Science 345 (2014), 647–650.

[17] R. P. Stanley, Enumerative Combinatorics, 2nd ed., Cambridge University Press, 2011.

[18] A. Tucker, Applied Combinatorics, 6th ed., John Wiley & Sons, 2012.

[19] Z. Y. Wei, Z. V. Guo, L. Dudte, H. Y. Liang, and L. Mahadevan, Geometric mechanics of periodic pleated origami, Phys. Rev. Lett. 110 (2013), 215501–215505.

[20] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences,

    http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A99; Secondary 05A15, 05C15. Keywords: origami, Miura map fold, graph coloring.

(Concerned with sequence \underline{A078099}.)

Received July 4 2013; revised versions received July 17 2014; September 18 2014. Published in Journal of Integer Sequences, November 5 2014.

Return to Journal of Integer Sequences home page.