Counting Mountain-Valley Assignments for Flat Folds

Abstract

We develop a combinatorial model of paperfolding for the purposes of enumeration. A planar embedding of a graph is called a crease pattern if it represents the crease lines needed to fold a piece of paper into something. A flat fold is a crease pattern which lies flat when folded, i.e., can be pressed in a book without crumpling. Given a crease pattern \(C = (V, E)\), a mountain-valley (MV) assignment is a function \(f : E \to \{M, V\}\) which indicates which crease lines are convex and which are concave, respectively. A MV assignment is valid if it doesn’t force the paper to self-intersect when folded. We examine the problem of counting the number of valid MV assignments for a given crease pattern. In particular, we develop recursive functions that count the number of valid MV assignments for flat vertex folds, crease patterns with only one vertex in the interior of the paper. We also provide examples, especially those of Justin, that illustrate the difficulty of the general multivertex case.