The map that is not a rectangle

In how many ways can a map be folded? The question needs no notation to state, the answer is a small integer for small maps, and after sixty years there is still no formula — only a list of numbers, each found by searching every possibility.

Every one of those numbers is for a rectangle. That is not a restriction anybody imposed; it is what a map is. But the rule does not know anything about rectangles, and asking it about a shape with a bite out of it turns out to be worth doing.

The rule, with the rectangle taken out of it #

A map folds by creasing along every line between squares and stacking the squares. A stacking is legal when no two creases at the same edge of the folded square interleave: paper cannot pass through paper, so two folds that wrap at the same place have to nest rather than interlock.

Which edge a crease wraps at is decided by the square, not by the map. Square (i, j) is mirrored in one direction when j is odd and in the other when i is odd, however many neighbours it happens to have. So the whole of the generalisation is: drop the squares that are not there, and keep the creases between the ones that remain.

That is one rule rather than two, and it has a check available. Run it on the full rectangles and it must give 16, 8, 60, 320 and 1,368 — the published counts for the 1×4, 2×2, 2×3, 2×4 and 3×3 maps. It does.

Take a square out #

A three-by-three map folds 1,368 ways.

Remove one corner square. Eight squares remain, and they fold 848 ways.

Remove the centre square instead. The same eight squares, in the same three-by-three box, fold 8,016 ways.

Nearly six times the count of the map it came from, and nearly ten times the count of the other eight-square map. The bounding box is the same, the number of squares is the same, and nothing about either predicts the answer.

It is worth being clear that the eight-square counts are not a rounding of the nine-square one. 848 and 8,016 are exact — every stacking of eight squares was generated and tested, all 40,320 of them, and the survivors counted. There is no sampling anywhere in this and no estimate.

Why removing a square adds foldings #

The mechanism is not deep and it is worth stating clearly, because it is the whole content.

The number of stackings falls when a square is removed: eight squares have 40,320 orderings and nine have 362,880. But most orderings are illegal, and what makes them illegal is creases interleaving. A square that is not there takes its creases with it — a corner square takes two, the centre square takes four — so removing it removes constraints as well as candidates.

The centre square of a three-by-three map is the most constrained square there is: it borders four others, and each of those borders is a crease that can interleave with something. Taking it out relieves the whole map at once. A corner square borders two, and taking it out relieves very little.

So the count is a race between two effects — fewer squares to permute, fewer creases to forbid — and which wins depends on which square, not on how many.

There is a tidy way to put the arithmetic. A square with k neighbours contributes k creases, and a crease is an opportunity to be forbidden. Removing a square costs one factor in the permutation count and saves whatever its creases were forbidding, and the saving is not a fixed amount — it depends on how much company those creases had at their edge of the folded square.

The centre of a three-by-three has four creases, and all four of them share edges with the creases of the squares around it. It is the busiest square in the map by a distance, and it is the one whose removal opens things up.

The map with no constraints at all #

The extreme case is small enough to be checked by hand and it is the most satisfying number here.

Take a three-by-three map and remove all four corners, leaving a plus of five squares. It folds 120 ways, which is exactly 5! — every ordering of its five squares is a legal folding.

The reason is that the plus has four creases and no two of them wrap at the same edge of the folded square: one goes up, one down, one left, one right, and interleaving is a relation between two creases at the same edge. With no two creases sharing an edge, nothing can interleave, and every stacking is legal.

The tee — three squares in a row with two more above the middle one — does the same thing, for the same reason, and also folds 120 ways.

A strip of five squares, by contrast, folds 50 ways of a possible 120. All four of its creases wrap at one of two edges, so they constrain one another constantly. Same number of squares, same number of creases, and less than half as many foldings.

That is worth holding onto because it identifies what the difficulty in map folding actually is. It is not the number of squares and it is not the number of creases — the plus and the strip of five have five and four of each — it is how many creases share an edge of the folded square. A map whose creases are spread across all four edges is easy in the strongest possible sense: nothing forbids anything. A map whose creases pile onto one edge is the one-dimensional case, where all of them share, and where the counting has been hard since the nineteen-thirties.

Five squares is the ceiling, and it is provable #

The plus and the tee folding every way their squares can stack is reported above as a curiosity of two shapes. It is the whole of a small theorem, and the theorem says exactly which shapes can do it and how large they can be.

Which edge of the folded square a crease wraps at is decided by parity. A crease between two horizontally adjacent squares wraps at the left edge or the right, according to the parity of the column it sits between; a crease between vertically adjacent squares wraps at the top or the bottom by the parity of its row. There are four edges, so there are four classes of crease and no more.

Two creases can interleave only if they wrap at the same edge — that is what the rule says. So a map has no constraints at all exactly when no two of its creases fall in the same class, which is to say when it has at most four creases, one per class.

Now count creases. A polyomino of $n$ squares that is connected has at least $n - 1$ creases, and exactly that many when its squares form a tree. So no constraints at all requires $n - 1 \le 4$, and five squares is the largest polyomino that can fold in every way its squares could stack. At six squares the pigeonhole is unavoidable: five creases into four classes puts two of them together, and two creases at one edge is a constraint.

Which shapes reach it #

Five squares is necessary and not sufficient, and the difference is what separates the plus from the strip.

A five-square tree has four creases, and they reach all four classes only if its two horizontal creases sit between columns of different parity and its two vertical creases between rows of different parity. The plus does exactly that — its four arms leave the centre in four directions, one crease each way — and so does the tee, whose two horizontal creases straddle a middle column and whose two vertical creases climb two rows.

The strip of five does not. All four of its creases are horizontal, so they fall into two classes with two apiece, and each pair can interleave. Fifty foldings of a hundred and twenty is what that costs, and it is the one-dimensional case in miniature — every crease sharing an edge with every other is the maximally constrained arrangement, and a strip is the shape that arranges it.

So the ceiling has two parts and both are exact. No polyomino of six or more squares is unconstrained, whatever its shape; and among the five-square shapes, the unconstrained ones are those whose creases reach all four edges. That turns the plus from a pleasing coincidence into the extreme point of a small classification — which is the kind of thing a count of labels rather than objects tends to obscure, and which shows up immediately once the constraint is read as a partition into four classes rather than as a property of a shape.

What it says about the counting problem #

The map-folding numbers are famous for having no formula, and the usual way of putting that is that the sequence 1, 8, 1368, 300608 has no pattern anybody has found.

The polyomino counts sharpen that. If a formula existed for rectangles, one would want it to be a function of the shape — and the eight-square maps show that the shape has to mean more than the box and more than the count. What it has to know about is which squares neighbour which, and how many creases wrap at each edge, and that is a description of the whole map rather than a summary of it.

That is the same shape of finding as the two directions of a map not separating: the two-dimensional count is not the product of the one-dimensional counts, and the ratio between them grows. In both cases the answer refuses to be a function of anything smaller than the map itself.

The smaller cases, and one more surprise #

The two-by-three map folds 60 ways. Remove a corner and the five remaining squares fold 40.

That is a fall, where the three-by-three’s corner removal was also a fall — 1,368 to 848 — and the plus’s was a rise. So the direction is not even consistent: it depends on the shape the removal leaves.

The proportion of stackings that survive is the quantity that makes the comparison fair, and it ranges from about a fifth for the strip of five to all of them for the plus. That range across shapes of the same size is the essay’s whole content in one number.

Why anybody would want a map with a bite out of it #

The obvious objection is that maps are rectangles, so who cares.

Two answers. The first is that the question was never about maps: it is about how many ways a set of connected squares can be stacked, and rectangles are the case somebody happened to ask about first. Restricting a combinatorial question to the shapes its name came from is not usually a good way to understand it, and here it has hidden the fact that the answer depends on connectivity rather than on size.

The second is that non-rectangular sheets are not exotic in this subject. The tree method’s leftover polygons are not rectangles; a sheet with a graft added is not a rectangle; and anything cut from a larger sheet is whatever shape it was cut into. Counting how many ways a region folds is a question that arises the moment the region stops being the whole sheet.

A third answer, and it is the one that makes the ladder worth continuing: the rectangle is the hardest shape of its size, or very nearly. Its creases are as crowded onto shared edges as they can be, so the proportion of stackings that survive is as low as it gets. Anything with a bite out of it is easier, and knowing by how much is knowing something about where the difficulty lives.

There is also a small pedagogical benefit. The plus that folds every way it can is the easiest possible demonstration that the constraint in map folding is interleaving rather than stacking — a five-square map with no constraints at all, next to a five-square map with plenty, made from the same amount of paper.

The counts, all together #

It is worth having the numbers in one place, because the comparison is the argument.

Nine squares in a full three-by-three: 1,368 foldings of 362,880 stackings, which is four in a thousand. Eight squares with a corner gone: 848 of 40,320, two in a hundred. Eight squares with the centre gone: 8,016 of 40,320, one in five. Five squares as a plus: 120 of 120, all of them. Five squares as a strip: 50 of 120.

The proportion is the honest comparison because it takes the permutation count out. Read that way the three-by-three is the hardest object in the list by two orders of magnitude, and the plus is not an object of that kind at all — it is a set of five squares with four creases that never meet, and calling its count a folding count rather flatters it.

Where the model stops #

Small maps only. Everything counted here is nine squares or fewer, because the search is exhaustive and exhaustive searches stop. What happens at twenty squares is not known and is not guessed at.

No claim about how hard it is. How expensive the search is, how it might be made cheaper, and what complexity class the counting problem sits in are questions about algorithms and belong elsewhere. What is reported is what the counts are.

Simply-connected shapes. Every polyomino here is one piece with no holes. A ring-shaped map — squares forming a loop — is a different object and is not counted, and given what a hole does to a folded sheet there is every reason to expect it to behave differently.

The rule is the standard one. No two creases at the same edge may interleave, which is the condition the published rectangular counts are computed under. Nothing here revisits whether that condition is the right model of paper.

Who counted what #

The rectangular map-folding numbers are Lunnon’s, computed in the nineteen-sixties and extended since; the one-dimensional stamp-folding numbers are older and go back to Touchard and to Koehler. Polyomino folding is not virgin territory either — the combinatorics literature has looked at folding non-rectangular shapes — and the counts above are small enough that anyone with a search could have produced them.

What this site adds is the comparison rather than the numbers: the two eight-square maps side by side, in the same box, differing by a factor of nearly ten, with the reason spelled out in creases rather than in squares.

Where the ladder goes next #

The obvious continuation is the one the missing-square result invites: which square is the most constraining, in general? The centre of a three-by-three is the most connected square and taking it out relieves the most, which suggests the count is governed by something like the degree sequence of the map’s adjacency — and that is a hypothesis with a small experiment behind it and no evidence beyond it.

There is a third direction, and it is the one a person with a computer would take first. The counts above are the fifty or so shapes that fit inside a three-by-three box. Enumerating every polyomino up to nine or ten squares and folding all of them is an afternoon’s work at these sizes, and it would turn the observation that the count depends on connectivity into a data set — which is the sort of thing from which somebody eventually extracts a formula, or proves that there is not one. The exponent nobody has proved exists is the standing example of what such a data set is worth.

The other direction is the map with a hole. Squares arranged in a ring have a folded state whose layers have to come back to themselves, which is a condition the rectangular rule has never had to express, and it is the same shape of question a sheet with a hole raises about flat-foldability. Whether the counting rule survives is not obvious, and finding out is a modest amount of work.