\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Counting Miura-ori Foldings } \vskip 1cm \large Jessica Ginepro\footnote{Research supported by the National Science Foundation grant EFRI-1240441 ``Mechanical Meta-Materials from Self-Folding Polymer Sheets".} \\ Department of Mathematics\\ University of Connecticut\\ 196 Auditorium Road, Unit 3009\\ Storrs, CT 06269-3009\\ USA\\ \href{mailto:jessica.ginepro@uconn.edu}{\tt jessica.ginepro@uconn.edu} \\ \ \\ Thomas C.~Hull\footnotemark[\value{footnote}]\\ Department of Mathematics\\ Western New England University\\ 1215 Wilbraham Road\\ Springfield, MA 01119\\ USA\\ \href{mailto:thull@wne.edu}{\tt thull@wne.edu} \end{center} \vskip .2 in \begin{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\times n$ grid graph with one vertex pre-colored. \end{abstract} \section{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 \cite{Justin, Koehler, Lunnon}. Furthermore, origami enumeration problems emerge naturally from the study of crumpling polymer membranes, where asymptotic results are obtained for restricted families of crease patterns \cite{DiF}. 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 {\em mountains} (convex) or {\em valleys} (concave) while being able to fold into a flat square without the paper self-intersecting. This problem is unsolved \cite{Justin}. 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 \cite{Koehler} wrote an early paper while Jensen and Guttmann \cite{JenGut} 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 \cite{Lunnon, Lunnon2}. 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 \cite{Hull3}. 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 {\em Miura map fold}, also known as the {\em Miura-ori} \cite{Maha1, Miura1, Silverberg, Wei}. Its crease pattern is made of an $m\times n$ array of congruent parallelograms in a herringbone pattern. Figure \ref{fig1} shows this crease pattern; each vertex consists of two congruent acute angles $\alpha$ and two congruent obtuse angles $\pi-\alpha$, where $0<\alpha<\pi/2$. \begin{figure} \centerline{\includegraphics[scale=.25]{gh-fig1.eps}} \caption{A $4\times 4$ Miura-ori with the standard MV assignment. Bold creases are mountains and non-bold creases are valleys.}\label{fig1} \end{figure} We can determine how a crease pattern folds up from its {\em 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 $\mu:E(C) \rightarrow \{-1,1\}$, where $-1$ indicates a valley and $+1$ a mountain crease. In order for the crease pattern to fold, the function $\mu$ must obey certain rules, as will be described in Section \ref{sec2}. The MV assignment shown in Figure \ref{fig1} is the standard way in which the Miura-ori is folded flat since it allows the paper to fold and unfold smoothly and rigidly \cite{Miura1}. Many other MV assignments are possible, however, that guarantee each vertex will fold flat. Unfortunately, as we will discuss in Section \ref{sec5}, not every Miura-ori MV assignment that {\em locally} folds flat will {\em globally} fold flat. In this paper we discuss enumerating the number of MV assignments for an $m\times n$ Miura-ori 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\times n$ grid graph with one vertex pre-colored. \section{Local flat folding conditions}\label{sec2} 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 \cite{Hull2}. {\em 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 $$\alpha-\alpha+(\pi-\alpha)-(\pi-\alpha) = 0,$$ and therefore each vertex will fold flat. {\em 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 \ref{fig1}. 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 \ref{fig2}, we cannot have $\mu(e_4)=V$ and $\mu(e_i)=M$ for $i=1,2,3$. Readers are encouraged to try this for themselves and discover how the two acute angles $\alpha$ cannot contain the obtuse angles if $e_1$, $e_2$, and $e_3$ creases are all mountains. We refer to this phenomenon as the {\em 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 $\mu(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 \ref{fig2}. \begin{figure} \centerline{\includegraphics[scale=.4]{gh-fig2.eps}} \caption{A Miura-ori vertex and the six MV assignments it can have, following the bird's foot forcing. }\label{fig2} \end{figure} We say that a MV assignment $\mu:E(C)\rightarrow \{\pm 1\}$ is {\em locally flat foldable} if $\mu$ matches one of the MV assignments shown in Figure \ref{fig2} 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 $\mu$ that can be made for a $m\times n$ Miura-ori (with $m$ rows and $n$ columns of parallelograms). Figure \ref{fig2} shows that $M(2,2)=6$. In the next section we develop some closed formulas for cases of $M(m,n)$. \section{Recursions and formulas}\label{sec3} 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) = 3 M(2,n-1)$, $M(2,2) = 6$. Therefore $$M(2,n) = 2 \cdot 3^{n-1}.$$ Notice that this same argument works to show that $M(m,2)=2\cdot 3^{m-1}$. In fact, $M(m,n) = M(n,m)$ always holds, but we will delay a proof of this until Section \ref{sec5}. Looking at a larger case than $m \times 2$ presents new problems. For this, a Lemma will prove useful. We say that a Miura-ori vertex {\em points left} if the ``heel" of the bird's foot points left, as they do in Figure \ref{fig2}. {\em Points right} is defined similarly. \begin{lemma}\label{lem:1xn} Let $C$ be the crease pattern for a $2\times n$ Miura-ori with all the vertices pointing left, and let $\mu$ be a MV assignment for $C$. Let $c$ be the left-most crease in $C$ and let $\gamma$ be a simple closed curve around all the vertices in $C$ (i.e., crossing all the non-internal creases). Let $M_\gamma$ (resp., $V_\gamma$) be the number of mountain (resp., valley) creases that $\gamma$ crosses. Then we have: If $\mu$ is locally flat-foldable then $\mu(c) = (M_\gamma-V_\gamma)/2$. \end{lemma} \begin{figure} \centerline{\includegraphics[scale=.4]{gh-fig22.eps}} \caption{As per Lemma \ref{lem:1xn}, a $2\times 5$ Miura-ori with $M_\gamma=6$, $V_\gamma=4$, and $\mu(c)=1$ (left) and a $2\times n$ Miura-ori as used in the proof (right).}\label{fig2-2} \end{figure} As will be seen in the proof, what Lemma \ref{lem:1xn} is really saying is that $M_\gamma-V_\gamma$ will always equal $\pm 2$, just as in Maekawa's theorem, and that the MV parity of the crease $c$ will control the plus/minus parity of $M_\gamma-V_\gamma$. See Figure \ref{fig2-2} for an example. (Note that these properties are not typically present in multiple-vertex flat origami crease patterns. See \cite[Activity 23]{Hull4} for examples.) \begin{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_\gamma-V_\gamma=\pm 2$ and consulting the six possible MV assignments in Figure \ref{fig2} confirms the result. Now let $C$ be a $2\times n$ Miura-ori with MV assignment $\mu$ as in the statement of the lemma and label the external creases $c_1, \ldots, 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 \ref{fig2-2}. Suppose that $\mu$ is locally flat-foldable in $C$. Then $\mu$ is also locally flat-foldable on the crease pattern $C-v$, which is a $2\times (n-1)$ Miura-ori. Using the induction hypotheses, we may assume without loss of generality that $M_{\gamma'}-V_{\gamma'}=2$ for $\gamma'$ surrounding this $2\times(n-1)$ Miura-ori, so that $c_1$ is a M. (The $M_{\gamma'}-V_{\gamma'}=-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 $\gamma'$ to $\gamma$ which includes $v$ then we still have $M_\gamma-V_\gamma=2$ since $\gamma$ 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 $\mu(c_1) = (M_\gamma-V_\gamma)/2$. This completes the proof of the lemma. \end{proof} \begin{figure} \centerline{\includegraphics[scale=.5]{gh-fig25.eps}} \caption{The last row of vertices in an $m\times 3$ Miura-ori crease pattern.}\label{fig2.5} \end{figure} We will now develop recursive equations for $M(m,3)$ by looking at cases. For an $m\times 3$ crease pattern $C$, denote the creases adjacent to the bottom-most row of two vertices as in Figure \ref{fig2.5}. Then let \begin{eqnarray*} A_m & = & \mbox{the number of $m\times 3$ MV assignments with }\mu(e_4)=\mu(e_5),\mbox{ and}\\ B_m & = & \mbox{the number of $m\times 3$ MV assignments with }\mu(e_4)\not=\mu(e_5). \end{eqnarray*} We start with the initial conditions $A_1=2$ and $B_1=2$, which makes sense if we think of the $1\times 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 $\gamma$ as in Figure \ref{fig2.5}, Lemma \ref{lem:1xn} tells us that $M_\gamma-V_\gamma=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 $\mu(e_1)\not=\mu(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_\gamma-V_\gamma = -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_\gamma-V_\gamma=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_\gamma-V_\gamma=-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., \cite[Sec.\ 7.5]{Tucker}), we obtain the generating function $(1-x)/(1-5x+2x^2)$ for $M(m,3)$. The zeros of the denominator are $\alpha_{\pm}=(5\pm\sqrt{17})/4$, giving us the closed form $$M(m,3)=c_+(1/\alpha_+)^m + c_-(1/\alpha_-)^m$$ where $c_{\pm}=(17\pm3\sqrt{17})/34$. The $m\times 4$ and $m\times 5$ cases are handled similarly, but with many more cases and details to check, which we skip here for brevity. For $m\times 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 \begin{eqnarray*} A_m & = & \text{the number of MV assignments with }\mu(e_1)=\mu(e_2)=\mu(e_3),\\ B_m & = & \text{the number of MV assignments with }\mu(e_1)=\mu(e_2)\not=\mu(e_3),\\ C_m & = & \text{the number of MV assignments with }\mu(e_1)=\mu(e_3)\not=\mu(e_2), \text{ and}\\ D_m & = & \text{the number of MV assignments with }\mu{e_1}\not= \mu(e_2)=\mu(e_3). \end{eqnarray*} 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 $\alpha_1\approx 1.65406$, $\alpha_2\approx 0.702511$, and $\alpha_3\approx 0.143432$, but their expression using radicals is quite messy. The approximate formula is $$M(m,4) = c_1(1/\alpha_1)^m+c_2(1/\alpha_2)^m+c_3(1/\alpha_3)^m$$ where $c_1\approx 0.0132428$, $c_2\approx 0.21837$, and $c_3\approx 1.10172$. The recurrence equations obtained for the $m\times 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+\cdots+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. \section{Coloring bijection} The formulas and recurrences generated thus far can be used to produce the following table of data for $M(m,n)$: \bigskip \centerline{ \begin{tabular}{c|cccccccccc} $n\backslash m$ & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 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{tabular} } \bigskip This table of numbers fits exactly the sequence \seqnum{A078099} in the On-Line Encyclopedia of Integer Sequences \cite{OEIS}, 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 {\em $m\times 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\times n$ grid graphs with one vertex pre-colored and the number of locally flat-foldable $m\times n$ Miura-ori crease patterns by defining a finite sequence $s_k$ for both of them. Given a properly 3-vertex colored $m\times n$ grid graph, let the colors be the elements of $\mathbb{Z}_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 {\em grid graph coloring sequence} $s_k$. For example, the grid graph coloring shown in Figure \ref{fig3} is $$s_k: 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 1$$ \begin{figure} \centerline{\includegraphics[scale=.7]{gridsequence.eps}} \caption{A $3\times 5$ grid graph with proper 3-vertex coloring and arrows showing the order of constructing the coloring sequence $s_k$.}\label{fig3} \end{figure} 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\not= 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)\mbox{ is adjacent to }v(s_j)\mbox{ if }j-i=2n-1-(2i\bmod 2n)$$ where $j>i$. We now describe a way to generate a sequence $s_k$ from an $m\times n$ locally flat-foldable Miura-ori crease pattern with MV assignment $\mu: C\rightarrow\{-1,1\}$. We will call such a sequence a {\em Miura-ori sequence}. First orient our crease pattern so that the top row of vertices all point left. Then imagine an $m\times 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\equiv s_{i-1}+\mu(c_i)\ \pmod 3.$$ See Figure \ref{fig4} for an example of creating a Miura-ori sequence. \begin{figure} \centerline{\includegraphics[scale=.7]{miurasequence.eps}} \caption{A $3\times 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$.}\label{fig4} \end{figure} In the following Lemma we prove that our recursion rule for generating the Miura-ori sequence holds for horizontal creases as well. \begin{lemma}\label{lem:Miura-consistent} Given a Miura-ori sequence $s_k$ generated by an $m\times n$ Miura-ori crease pattern, consider non-negative integers $i$, $j$ with $j-i=2n-1-(2i \bmod 2n)$ and let $d_i$ be the crease between $v(s_i)$ and $v(s_j)$. Then $s_j \equiv s_i + \mu(d_i)$ ({\rm mod} 3). \end{lemma} \begin{proof} If $j-i=2n-1-(2i \bmod 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 \equiv s_i + \sum_{k=i+1}^{j}\mu(c_k) \pmod 3.$$ Therefore we want to show that $\mu(d_i) = \sum_{k=i+1}^{j}\mu(c_k)$. For this, we apply Lemma \ref{lem:1xn}. Let $\gamma$ be a simple closed curve through the creases, in order, $c_{i+1}, \ldots, c_{j}, d_i$. Then, by Lemma \ref{lem:1xn} we have $$2\mu(d_i) = M_\gamma-V_\gamma = \mu(d_i) + \sum_{k=i+1}^{j}\mu(c_k),$$ where the second equality is obtained by simply adding all the values of $\mu$ along $\gamma$. Thus $\mu(d_i) = \sum_{k=i+1}^{j}\mu(c_k)$ and we are done. \end{proof} Lemma \ref{lem:Miura-consistent} shows that every $m\times n$ Miura-ori sequence also gives an $m\times 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\times 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\times n$ Miura-ori crease pattern (with the top row vertices pointing left) and generate a MV assignment from the recurrence $s_i\equiv s_{i-1}+\mu(c_i)$ (mod 3). That is, $$\mu(c_i) = \begin{cases} 1, & \text{if }s_i-s_{i-1}\equiv 1 \pmod 3; \\ -1, & \text{if }s_i-s_{i-1}\equiv 2 \pmod 3.\end{cases}$$ Note, however, that this does not define $\mu$ 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 $\mu$ defined thus far will generate the same sequence $s_k$ that the grid graph coloring generated. Therefore we can use the result of Lemma \ref{lem:Miura-consistent} to assign $\mu$ 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 $$\mu(d_i) = \begin{cases} 1, & \text{if }s_j-s_i\equiv 1 \pmod 3; \\ -1, & \text{if }s_j-s_i\equiv 2 \pmod 3.\end{cases}$$ \begin{lemma}\label{lem:Miura-folds} The $m\times n$ Miura-ori MV assignment $\mu$ created by the above procedure is locally flat-foldable. \end{lemma} \begin{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. \begin{figure} \centerline{\includegraphics[scale=.7]{localflatvertex.eps}} \caption{Two Miura-ori vertices that point left with the creases labeled and superimposed grid graph section.}\label{fig5} \end{figure} 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 \ref{fig5}. From the construction of $\mu$, we have \begin{eqnarray*} s_i & \equiv & s_{i-1} + \mu(c_i) \pmod 3\\ s_j & \equiv & s_i + \mu(d_i) \pmod 3\\ s_{j+1} & \equiv & s_j + \mu(c_{j+1}) \pmod 3\\ s_{j+1} & \equiv & s_{i-1} + \mu(d_{i-1}) \pmod 3 \end{eqnarray*} Substituting the first three equations into one another, we obtain $s_{j+1} \equiv s_{i-1} + \mu(c_i) + \mu(d_i) + \mu(c_{j+1})$ (mod 3), and since each of the $\mu$ values are only $\pm 1$, we have $$\mu(d_{i-1}) = \mu(c_i) + \mu(d_i) + \mu(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. \end{proof} Therefore we have that the $m\times 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\times n$ grid graph where the upper-left vertex is colored 0 and $m\times n$ Miura-ori locally flat-foldable MV assignments is injective. We conclude that the correspondence between grid graph colorings with one vertex pre-colored 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\times n$ grid graph ($m$ rows and $n$ columns of squares) with the upper-left vertex pre-colored, then we have proven the following: \begin{theorem}\label{thm:color} $T(m,n) = M(m,n)$ for all $m,n\geq 1$. \end{theorem} Unfortunately, there are no known formulas for 3-coloring grid graphs, e.g. the problem of finding the chromatic polynomial of an $n\times m$ grid graph is unsolved \cite[Problem 14.7]{Jensen}. However, in the OEIS listing for \seqnum{A078099} a recursive transfer matrix for $T(m,n)$ is given. Specifically, define matrices $M(1) = [1]$, $$M(m+1) =\left[ \begin{array}{cc} M(m) & M(m)^T\\ 0 & M(m) \end{array}\right], $$ 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 \begin{equation}\label{matrix} W(m+1) =\left[ \begin{array}{cc} W(m) & M(m)^T\\ M(m) & W(m) \end{array}\right]. \end{equation} 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\times 1$ grid graph with colors in $\mathbb{Z}_3$, where two such colorings $\vec{x},\vec{y}\in \mathbb{Z}_3^m$ are equivalent if either $\vec{x}+(1)^m$ or $\vec{x}+(2)^m$ is equivalent to $\vec{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 $\mathbb{Z}_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 $\vec{x}\in C_i$ and $\vec{y}\in 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 \eqref{matrix}. \section{Further observations and questions}\label{sec5} One immediate consequence of Theorem \ref{thm:color} is the following: \begin{corollary}\label{cor5} $M(m,n) = M(n,m)$ for all $m,n\geq 1$. \end{corollary} This simply follows from the symmetry of the grid graph colorings, giving us $T(n,m) = T(m,n)$. Corollary \ref{cor5} is surprising because the Miura-ori crease pattern itself does not follow this symmetry; an $m\times n$ Miura-ori does not look the same as an $n\times m$ Miura-ori. We are fortunate that statistical mechanics results exist for enumerating our $m\times 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\times n$ grid graph on a torus, which is exactly the antiferroelectric model for two-dimensional ice lattices, called the {\em square ice} model \cite{Lieb, Propp}. 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 (\ref{matrix}) can be used to find more generating functions for $M(m,n)$ than were shown in Section \ref{sec3}. That is, following Stanley \cite[Sec.\ 14.7]{Stanley}, the generating function $G_m(x)$ for $M(m,n)$ for a fixed $m$ will be $$G_m(x)=x\sum_{i,j} \frac{(-1)^{i+j}{\rm det}(I-xW(m) : j,i)}{{\rm 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}\times 2^{m-1}$ matrix. Thus calculating $G_m(x)$ is computationally expensive. We used {\em 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 \ref{table1}. \begin{table} \centerline{ \begin{tabular}{l|c|c} & constant term & exponential term \\ \hline $m=2$ & 2/3 & 3\\ \hline $m=3$ & 0.8638 & 4.56155\\ \hline $m=4$ & 0.21837 & 1.42347 \\ & 1.10172 & 6.97196 \\ \hline $m=5$ & 0.0308918 & 1.32083 \\ & 0.323552 & 3.11838\\ & 1.39119 & 10.6829\\ \hline $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 \end{tabular} \raisebox{.51in}{ \begin{tabular}{l|c|c} & constant term & exponential term \\ \hline $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 \end{tabular} } } \caption{The approximate terms of $G_m(x) = \sum$(constant)(exponent)$^n$, the generating function for $M(m,n)$, up to $m=7$.}\label{table1} \end{table} As mentioned previously, not all of the locally flat-foldable Miura-ori MV assignments are globally flat-foldable. An example is shown in Figure \ref{fig10}. It is simply one of the non-foldable counterexamples to the postage-stamp folding problem reported by Justin \cite{Justin} 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 \ref{fig1}. 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. \begin{figure} \centerline{\includegraphics[scale=.5]{gh-fig10.eps}} \caption{A locally flat-foldable $5\times 1$ Miura-ori MV assignment that is not globally flat-foldable (rotated to conserve space).}\label{fig10} \end{figure} 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. \section{Acknowledgments} The authors would like to thank Tomohiro Tachi and Ryuhei Uehara for their suggestion of the non-foldable Miura-ori in Figure \ref{fig10} (among others), to David Eppstein for pointing us to the square ice model and reference \cite{Lieb}, and to Crystal Wang and an anonymous referee for useful comments and corrections. \begin{thebibliography}{99} \bibitem{DiF} P. Di Francesco, Folding and coloring problems in mathematics and physics, {\em Bull. Amer. Math. Soc.} {\bf 37} (2000), 251--307. \bibitem{Hull2} T. Hull, The combinatorics of flat folds: a survey, in T. Hull ed., {\em Origami$^3$: Third International Meeting of Origami Science, Mathematics, and Education}, A K Peters, 2002, pp.~29--38. \bibitem{Hull3} T. Hull, Counting mountain-valley assignments for flat folds, {\em Ars Combin.} {\bf 67} (2003), 175--188. \bibitem{Hull4} T. Hull, {\em Project Origami: Activities for Exploring Mathematics, 2nd ed.}, CRC Press, 2013. \bibitem{JenGut} I. Jensen and A. J. Guttmann, Critical exponents of plane meanders, {\em J. Phys. A} {\bf 33} (2000), L187--L192. \bibitem{Jensen} T. R. Jensen and B. Toft, {\em Graph Coloring Problems}, John Wiley \& Sons, 1995. \bibitem{Justin} J. Justin, Toward a mathematical theory of origami, in K. Miura, ed., {\em 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. \bibitem{Kob} H. Kobayashi, B. Kresling, and J. Vincent, The geometry of unfolding tree leaves, {\em Proc. R. Soc. London Ser. B} {\bf 265} (1998), 147--154. \bibitem{Koehler} J. Koehler, Folding a strip of stamps, {\em J. Combin. Theory} {\bf 5} (1968), 135--152. \bibitem{Lieb} E. H. Lieb, Residual entropy of square ice, {\em Physical Review} {\bf 162} (1967), 162--172. \bibitem{Lunnon} W. F. Lunnon, A map-folding problem, {\em Math. Comp.} {\bf 22} (1968), 193--199. \bibitem{Lunnon2} W. F. Lunnon, Multi-dimensional map-folding, {\em The Computer Journal} {\bf 14} (1971), 75--80. \bibitem{Maha1} L. Mahadevan and S. Rica, Self-organized origami, {\em Science} {\bf 307} (2005), 1740. \bibitem{Miura1} K. Miura, A note on intrinsic geometry of origami, in H. Huzita ed., {\em Proceedings of the First International Meeting of Origami Science and Technology}, self-published, 1989, pp.~239--249. \bibitem{Propp} J. Propp, The many faces of alternating-sign matrices, in R. Cori, J. Mazoyer, M. Morvan, and R. Mosseri eds., {\em Discrete Models: Combinatorics, Computation, and Geometry}, Discrete Math. Theor. Comput. Sci. Proc., Vol. AA, Maison Inform. Math. Discr\`{e}t., 2001, pp.~43--58. \bibitem{Silverberg} 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, {\em Science} {\bf 345} (2014), 647--650. \bibitem{Stanley} R. P. Stanley, {\em Enumerative Combinatorics}, 2nd ed., Cambridge University Press, 2011. \bibitem{Tucker} A. Tucker, {\em Applied Combinatorics}, 6th ed., John Wiley \& Sons, 2012. \bibitem{Wei} Z. Y. Wei, Z. V. Guo, L. Dudte, H. Y. Liang, and L. Mahadevan, Geometric mechanics of periodic pleated origami, {\em Phys. Rev. Lett.} {\bf 110} (2013), 215501--215505. \bibitem{OEIS} The OEIS Foundation Inc., {\em The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A99; Secondary 05A15, 05C15. \noindent \emph{Keywords: } origami, Miura map fold, graph coloring. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A078099}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 4 2013; revised versions received July 17 2014; September 18 2014. Published in {\it Journal of Integer Sequences}, November 5 2014. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}