A line in the columns, a binomial in the rows

One choice with eleven answers repaired a blind spot in the test that decides whether two folded panels overlap, and recounted the folded states of every Miura patch small enough to list. The counts rose: six states for the three-by-three patch where one had been recorded, eleven for the four-by-three. On strips two rows high they followed a rule too regular to be an accident, $2c - 3$ states for $c$ columns — three, five, seven, nine, eleven — and the essay ended by asking for an argument that would produce that rule, because the listing could go no further. Three rows high it had only two numbers, six and eleven, and could not say whether they lay on a line.

There is an argument, but the first thing it needed was a count that does not stop at eight columns. Once that exists, $2c - 3$ turns out to be one row of a table, and the whole table has a formula.

Counting without ordering what never touches #

A folded state of a patch is the order of its panels in the stack, but only the part of that order anybody could observe: which of two panels is on top, for every pair of panels that lie over one another. Two panels that never share ground are not stacked in any visible sense, and the records the earlier essays compared — the layer-order field of the interchange format, a list of free choices — store nothing about them.

The listing search does not know that. It builds complete orders of every panel, bottom upward, and only at the end collapses the orders that agree on every overlapping pair. On a two-row strip, column $i$ never touches column $i + 4$, and every such pair can go either way in a complete order while the state stays the same; the orders multiply far faster than the states do. On the eight-column strip the search exhausts its budget before it finishes, and it refuses outright past eighteen panels.

The repair is to build the states from the overlapping pairs and nothing else. Every rule a folded state must keep reads only pairs that overlap. A crease’s two panels share the crease; a panel that a crease runs through overlaps both of the crease’s panels; two folds in the same place overlap all four of theirs. So a set of above-and-below signs on the overlapping pairs is a folded state exactly when it keeps every rule and contains no cycle — no panel above a panel that is, by some chain, above it. Given such a set, any order of the panels that respects the signs is a legal stacking, because no rule can see the pairs the signs leave free.

That makes the states something that can be grown. Place the panels one at a time, column by column, and extend each partial state by every choice of sign between the new panel and the earlier panels it overlaps, keeping a choice only if the rules it completes all hold and it closes no cycle. Nothing that does not touch is ever ordered, and no state is found twice, because two extensions that differ in a sign are different states.

The two methods are compared before the second is trusted, since the first thing about layers found that every earlier answer to a layer-order question was a search, and a shortcut that disagreed with one would be worth nothing. On every patch the listing finishes — the strips three to six columns long, the three-by-three and four-by-three, the narrow patches two columns wide — the grown states are the listed states, sign for sign, not merely in number. Then the growth goes where the listing cannot: a strip eight columns long in a few milliseconds, twenty columns long with 40 panels and 236 overlapping pairs in under a tenth of a second, a patch three columns wide and nine rows high with 27 panels and 351 pairs. The printed six-by-four Miura, which the field is empty where it would say nothing could not list at all, has 37 folded states.

The formula the counts follow #

Laid out by height, the counts are straight lines in the number of columns. One row high, $c - 1$. Two rows, $2c - 3$, now confirmed to twenty columns. Three rows, $5c - 9$: six, eleven, sixteen, twenty-one and so on to forty-one at ten columns. Four rows, $9c - 17$.

Every line passes through a single state at two columns, which is the earlier finding that a patch two columns wide has exactly one folded state at every length. So each line is $1 + s_r(c - 2)$, and the whole table is decided by the slopes $s_r$: one, two, five, nine. Adding one to each gives the count at three columns — two, three, six, ten — and continuing up the three-column patches gives 20, 35, 70, 126 and 252 at five to nine rows.

Those are the central binomial coefficients, $\binom{r+1}{\lfloor (r+1)/2 \rfloor}$: the number of ways to choose half of $r + 1$ things. With $B_r$ for that number, every patch counted has

$$N(c, r) = 1 + (c - 2)(B_r - 1)$$

folded states. The formula was read off the patches up to four rows and then tested on patches it had not seen: four columns by five rows (39), four by six (69), four by seven (139), five by five (58), five by six (103), six by five (77), and ten by three (41). Every one matched.

None of that is a proof. The formula holds on every patch counted, and the counting is exact, but nothing below derives the binomial. What can be derived is why the count is a line in the columns, and the reason is visible in the stack.

Why each column adds the same number #

The growth makes it possible to watch a column being added: take every state of a strip $c$ columns long, and ask how many states of the strip one column longer keep it when the new column is deleted. Deleting a column from a legal stack leaves a legal stack, since every rule it removes involved that column, so every longer state restricts to exactly one shorter state, and the count of the longer strip is the sum of those numbers.

On the two-row strip four columns long, four of the five states extend in exactly one way. The fifth extends in three, and the five-column strip has $5 - 1 + 3 = 7$ states. The fifth state is the one in which the last column lies outermost: every panel it overlaps is on the same side of it, so nothing is folded over it on the side where the next column has to go. Everywhere else something already lies against the last column on that side, and the new column, folding back from the last one, is measured to have exactly one place it can go. When nothing does, the stacks show the three places directly: lying against the last column, wrapped round the outside of everything else, or on the far side of the whole stack.

The same thing happens at every height and every length, and that is what makes the count a line. On strips one and two rows high there is exactly one branching state at each step, and it is always the one whose last column is outermost — at the top of the stack for an odd number of columns and at the bottom for an even one, because the folds alternate their direction column by column. It extends two ways on a single row and three on two rows. On taller patches that state branches the most and a few others with the last column partly exposed branch too: three rows high, into two, three and three; four rows high, into two, three, four and four. The branching states are the same few at every length from three columns on, and every other state is carried along unchanged, so each column adds the same number of states as the last. The extra states each step creates are new states in which the last column is buried, so they extend one way next time, and the new outermost state takes over the branching.

That is the argument the earlier essay asked for, in its exact form. It says why the count is linear in the columns and why the slope is fixed by the first step, from two columns to three, which is the step from a single state. It does not say why that first step creates $B_r - 1$ states, and that is where the binomial lives.

The binomial in the rows #

Three columns wide, a Miura patch is a middle column with an end column folded onto it from each side, which is the letter fold one sheet down found has two states: nothing decides which end is on top. A patch of $r$ rows is $r$ such letter folds joined along the straight creases between the rows. If the rows were independent there would be $2^r$ states; if they were locked together there would be two. The count is the central binomial coefficient, which sits between — it grows like $2^{r+1}/\sqrt{\pi (r+1)/2}$, so each added row very nearly doubles it — and the square root is the cost of the rows not being independent.

The shape of the number suggests what an explanation would look like. A central binomial coefficient counts the ways of arranging $r + 1$ steps, half of them one way and half the other, and the two end columns of a three-column patch are two stacks of $r$ panels that have to be merged into one. A rule that allowed the merge to switch sides only at particular rows, and forced an even split, would produce exactly this count. No such rule has been identified in the stacks, and the counts are offered as measured: from one row to nine, without exception, and without a reason.

Where the formula stops #

The formula carries a condition, and finding it took a figure the earlier essays had drawn for another purpose. Every Miura counted so far had square cells sheared by 20.05 degrees. Changing the shear alone, from three degrees to seventy-five, changes nothing on square cells except at exactly forty-five degrees, which turns out to be the edge of the condition below: every patch tested keeps its count at every other shear. Changing the cells’ width does.

A patch five columns by three rows has sixteen states while its cells are narrow and one once they are wide, and the step is sharp. It sits where a cell’s width $W$, height $H$ and shear $a$ satisfy $W \sin 2a = H$ — at 1.55 cell heights for the shear these essays draw, at 1.12 for 31.5 degrees, and at almost exactly a square cell for 43 degrees. The dial walks the step across the plot; the count on either side of it never moves.

The step is where folded columns two apart stop overlapping. Folding a Miura row slides each column one step along the folded strip from the last, and columns two apart share a parallelogram of paper only while two steps are shorter than a panel is long. Past the step, each column overlaps only its neighbours, a column can never be tucked inside one two along, and the stack has nothing left to choose.

That condition has been met before in this subject, in the units of thickness. The slant that stacks in one depth found that the pile under a point of a folded Miura is the rows times the number of column images over it, and that this number is on average $2H/(W \sin 2a)$. The folded states multiply exactly when that pile is more than two deep. At two or fewer column images per point, the stack is an accordion that can only close one way; at more than two, every third column lies over the first, and that overlap is where all $N(c, r) - 1$ alternatives come from. The essay on piles was asking how thick a folded Miura is, and this one was asking how many ways it can be stacked, and the answer to the second changes where the first passes through two.

What a record would cost #

The earlier essays measured the layer-order field against what it has to say, and the formula makes that measurement possible on any patch. The field stores a sign for each overlapping pair, and a reader who holds the crease pattern needs only $\log_2 N(c, r)$ bits to know which state the folded object is. On the printed six-by-four Miura that is 228 signs against 5.2 bits. On a strip of twenty columns, 236 signs against 5.2 bits as well, since a line in the columns grows its logarithm slowly. Three columns by nine rows, 351 signs against eight bits.

That puts a number on what one choice with eleven answers argued in words, and on the gap a file has no paper found between a crease pattern and the object folded from it: a folded Miura is best recorded as an index into its list of states, and the list is short. The formula also says how short it stays. Lengthening a Miura adds states in a straight line, so a long strip’s record grows like the logarithm of its length. Making it taller multiplies the states by nearly two a row, so a tall patch’s record grows by nearly a bit a row. A Miura’s ambiguity lives in its height, and a designer who wants a folded model with few stackings can add columns far more cheaply than rows.

Stacks, not sequences #

Which state a folder reaches. Every state counted is a legal stack, and none of them is a sequence of folds. What a dashed line can say is about the diagrams that build a stack one fold at a time, and whether a standard collapse picks one particular state, or several, or whether some states need a sequence nobody would perform, is not decided here.

Whether the three folding rules are all the rules. The count is of stacks that keep the crease letters, keep panels out of folds they would pass through, and keep two folds in one place from interleaving. Those are the conditions a flat folded state is usually held to, and they are necessary. They are not a proof that each stack can be reached by a continuous motion of the paper.

Any reason for the binomial, as said above, and any patch taller than nine rows.

Zero thickness and the standard Miura #

The paper has no thickness. Every folded panel is a zero-thickness parallelogram, and the stack is an order rather than a pile of heights. A real sheet’s thickness separates layers that the count treats as touching, and the states differ in how much paper sits where, which the slant that stacks in one depth measures and this essay does not.

The patch is the standard Miura: straight creases between rows, zigzag creases between columns, every cell the same parallelogram, and the letters every printed Miura carries. Grading the cells, as the slant belongs to the line does, changes which columns overlap, and the formula would have to be recounted for it.

Two panels overlap when they share area. Panels that meet only along an edge — which is exactly what happens at the step, where $W \sin 2a = H$ — are degenerate, and near that point the overlap is a sliver too thin to compute reliably. The step’s position is stated as a limit approached from both sides.

Grown against listed, sign for sign #

The growth must equal the listing, sign for sign, on ten patches the listing finishes — strips of three to six columns, the three-by-three, the four-by-three, narrow patches two columns wide and single rows. Every figure here repeats that comparison before it draws anything.

Every counted patch must equal the formula, on all forty-four patches from two to twelve columns and one to four rows, and on the twelve in the comparison table; and every patch three columns wide from one to nine rows must equal its central binomial coefficient.

At every step from three to seven columns, on every height from one to four rows, the states of the longer patch must restrict to states of the shorter, and the branching states must be the same in number and multiplicity at every length.

At every shear on the dial, the five-by-three patch must have sixteen states for every cell narrower than $1/\sin 2a$ cell heights and one for every cell wider.

Still open: the binomial, and the first column’s choice #

The line in the columns is explained; the slope is not. The first step, from two columns to three, makes $B_r - 1$ new states, and every later step copies that number, so the whole formula reduces to one question about the three-column patch: why its states are counted by choosing half of $r + 1$ things. The candidates are the merges of its two end columns’ stacks, and a rule saying at which rows a merge may cross from one end to the other would settle it. The grown states are small enough to read row by row — six at three rows, twenty at five — and the rule, if it exists, is in them.

The second question is reachability, carried from the essay before: which of the 37 states of the printed Miura a standard collapse produces, and whether any needs a sequence nobody has written down. With the count settled, that is a question about 37 objects rather than an unknown number of them.

Sideways from here, the growth method is not about the Miura, and it bears on where the exponent comes from, which asks how fast the folded states of a map multiply with its size. A Miura with its letters fixed is the opposite case in one direction: its states grow in a straight line along its length and do not multiply at all, while along its height they nearly double a row. Any pattern whose panels overlap only near their neighbours can be counted the same way, and the map counted from the layers counts flat maps by building layer orders over every panel. A map’s panels all overlap once folded, so the growth would buy nothing there; a tessellation that drifts as it folds, as the Miura does, is where it reaches furthest.

The habit worth carrying is about what a search pays for. Before deciding that something can only be counted by listing it, ask what the listing orders that nobody can observe. The search was right on every patch it finished and spent nearly all of its effort ordering panels that never touch, and the count it could not reach was a straight line the whole time.