The count counts labels

In how many ways can a map be folded is the oldest open problem in this subject. The question needs no notation to state, the answers for a strip of stamps are 1, 2, 6, 16, 50, 144, 462, 1392, and after sixty years there is no formula — only a list of numbers, each found by searching every possibility.

Something has been true of every one of those numbers since the first of them was computed and is not usually said out loud: the stamps are numbered. The sequence counts foldings of a strip whose segments are distinguishable, and two arrangements that differ only in which end the counting started from are two entries in it.

A folded strip of blank paper has no first stamp. It also has no top side — a pile of paper turned over is the same pile. So there are two operations that leave the object alone and move the record of it, and the number of objects is the number of orbits.

Which is not the number of foldings over four, and finding out why is this essay.

The two operations #

Reverse is a relabelling. Segment i becomes segment n−1−i: the strip is read from the other end, and every layer stays exactly where it is. Nothing about the pile changes; the record of it does.

Turn is a change to the pile that changes nothing observable. The layer at height h moves to height n−1−h, which is the pile upside down, and a pile of blank paper upside down is the same pile seen from underneath.

Both map legal foldings to legal foldings, and both are involutions, so together with their composition and the identity they form a group of four acting on the set of foldings.

The reason the group is exactly these two and not more is worth a sentence, because a reader might expect a third. There is no rotation to include: a folded strip lives in a line, its folded image is an interval, and the only isometries of an interval are the identity and the flip — which is reverse. And there is no relabelling of the layers to include, because the layers are the paper and the paper is what is being counted.

Neither of them ever fixes a folding #

The first result is a pair of zeros and they hold everywhere the computation reaches.

No folding of a strip is fixed by reading it from the other end. Not at two stamps, not at eight, not at any size measured.

No folding is fixed by turning it over either.

The reverse case has a short reason. A folding fixed by reversal would have to be symmetric about the middle of the strip; the two end segments are the outermost pieces of paper at the two ends of the folded image, and in a folding fixed by reversal they would have to be at the same height as each other and at each other’s positions — which puts two pieces of paper in one place.

The turn case is shorter still. Turning the pile over exchanges the top layer with the bottom, and a folding fixed by it would need the top layer to be the bottom layer.

Neither argument is deep and neither had been made, because nobody had needed the fixed-point counts. What needed them is what comes next.

Doing both does fix some #

The composition — read from the other end and turn over — is a different operation and it is not fixed-point-free.

At two stamps it fixes both foldings. At three it fixes two of six, at four it fixes four of sixteen, at five six of fifty, at six eight of 144, at seven eighteen of 462, and at eight twenty of 1,392.

A folding fixed by the composition is one that looks the same read backwards and upside down, which is a real and picturable thing: fold a strip so that it is centrally symmetric about the middle of the pile. Those exist, there are not many, and their number is what makes the arithmetic below come out where it does.

Burnside’s lemma, and the check it supplies #

The number of orbits of a group acting on a set is the average number of points each group element fixes. The identity fixes everything; reverse and turn fix nothing; the composition fixes what it fixes. So the number of objects is

(foldings + 0 + 0 + fixed by both) ÷ 4

At eight stamps that is (1392 + 20)/4 = 353. And 1392/4 is 348, so the twenty fixed points are worth five extra objects — which is the whole reason this is not a division.

The lemma is not being used as the method here. The orbits are counted directly, by putting every folding through all four operations and keeping the alphabetically smallest record of it. The lemma is used as the check, and the two agree at every size: 1, 2, 5, 14, 38, 120, 353.

Two routes to one number, one of them a canonicalisation and the other an average over a group, and they are not allowed to disagree. That is the site’s habit, and it is worth having here because a group action is exactly the sort of thing where an off-by-one in the orbit code produces a plausible sequence.

What the object sequence is #

Written out: 1, 2, 5, 14, 38, 120, 353 for two to eight stamps.

The first four are the Catalan numbers, which is a coincidence and stops being one at six — Catalan continues 42, 132, 429 and this sequence goes 38, 120, 353. Nobody should read anything into the agreement at the start; small counting sequences agree with the Catalan numbers all the time.

What can be said is the growth. The ratio of consecutive terms runs 2.0, 2.5, 2.8, 2.71, 3.16, 2.94 — which is the same shape as the ratio in the labelled sequence, climbing past three and still climbing where the computation stops. That is expected: quotienting by a group of fixed order changes a sequence by a bounded factor and cannot change its exponential growth rate.

So the object sequence has the same open problem attached to it. The growth constant nobody has proved exists for the labelled count is the same constant for the unlabelled one, and the four-fold division does not make the problem any easier.

Why the fixed points are so few #

Twenty of 1,392 is one and a half per cent, and the share falls with size: 100 per cent at two stamps, 33 at three, 25 at four, 12 at five, 5.6 at six, 3.9 at seven, 1.4 at eight. That is worth a paragraph because it is the reason the object count is nearly a quarter of the labelled one, and why nobody who did the division in their head would have noticed.

A folding fixed by the composition has to be centrally symmetric: the whole arrangement carried onto itself by reading it backwards and turning it over. That is a condition on the whole object rather than on any part of it, and the number of arrangements satisfying a whole-object condition falls off against the number of arrangements as the object grows — in this case fast enough that the quotient converges to a quarter from above.

So the error in dividing by four is 1.4 per cent at eight stamps and shrinking. It is not a large error and it is not the point. The point is that the correction exists, has a mechanism, and is computable — and that a sequence quoted as a count of objects for sixty years is a count of records.

The fixed points have a pattern, and it splits by parity #

The counts of foldings fixed by the composition are 2, 2, 4, 6, 8, 18 and 20 for strips of two to eight stamps, and they are quoted above only as inputs to a division. Read as a sequence in their own right they do something worth reporting.

Separate them by the length of the strip. The odd lengths give 2 at three stamps, 6 at five and 18 at seven — a factor of three for every two stamps added, exactly, on all three terms available. The even lengths give 2, 4, 8 and 20, which is a factor of two three times and then two and a half, and has no clean shape over four terms.

There is a reason to expect the two parities to differ rather than agree. A folding fixed by the composition is centrally symmetric — carried onto itself by reading it backwards and turning it over — and on an odd-length strip that symmetry has a middle segment, which must be carried to itself and therefore sits at the middle height of the pile. On an even-length strip there is no middle segment and the symmetry pairs every stamp with another. Those are different combinatorial problems, and there is no reason for their counts to lie on one curve.

So the odd sequence’s factor of three is a prediction: nine stamps should give fifty-four centrally symmetric foldings and eleven should give a hundred and sixty-two. Three terms are three terms and this is an observation rather than a result, but it is exactly the kind of observation the enumeration already written can settle — the foldings of a nine-stamp strip are already being counted for the labelled sequence, and testing this needs one extra tally.

Which would sharpen the object count #

The value of settling it is not the fixed points themselves. It is that the object count is the labelled count plus the fixed points, all over four, so a formula for either of the two would carry across.

Nobody expects a formula for the labelled count — that is the sixty-year-old open problem. But the fixed-point count is a much smaller object: 20 against 1,392 at eight stamps, one and a half per cent of the population, and defined by a symmetry condition rather than by an enumeration. A sequence that small with a factor of three in it is the kind of thing that sometimes does have a closed form, and if the odd terms really are twice a power of three then half of the correction is settled outright.

That would not solve anything. It would mean the object sequence is the labelled sequence plus a known term over four — which is to say the two sequences are the same problem, with one of them differing from the other by something computable. That is a small and definite statement, it is checkable at one more size, and it is the only part of this whole area where a closed form looks plausible at all.

The same question about a marked strip #

Everything above is a count over all markings: for each way of lettering the creases, every legal stacking, all thrown into one set. That is what the classical sequence counts, and it is the right set for the question “in how many ways does this strip fold”.

There is a second question underneath it and the group answers that one too. Fix a marking — say the four-segment strip lettered MMV — and ask how many objects it has. The two operations do not preserve a marking: turning a folding over swaps every mountain for every valley, so it carries a marking’s foldings to the reversed marking’s foldings, and reading from the other end reverses the letters’ order.

So within one marking the group is not acting at all; it acts on the union. Which means the per-marking counts this site has published — three stackings here, four there, seven at the eight-crease vertex — are counts of objects already, with no quotient to take, provided one is careful to say of that marking.

That distinction resolves something that looks like a contradiction. The whole-strip count needs a quotient and the per-marking count does not, because the operations that move the record of a folded strip also move which strip it is a folding of.

Which count is the right one #

Both, and which one depends on what is being counted for.

The labelled count is right for a map. A map has printing on it, and a road atlas folded so that page one is on the outside is a different object from one folded so that page eight is. The problem’s name is map folding and its original motivation was maps, so the sequence in the literature is counting the thing it was asked about.

The object count is right for paper. A folder with a blank strip who produces two foldings related by reversal has produced one thing twice, and any statement about how many shapes a strip can take should be quotienting.

The distinction has bitten this site before in the other direction. The waterbomb tessellation’s thirty-two surviving repeating rules fold to one object — same panels, same places, same areas — and the thirty-two differ only in which side of the paper is showing. That was a count of labels on one object; this is a count of objects that had been reported as labels. A count that comes out at a power of two has a group underneath it, and so does one that comes out at four times something.

Where the group does and does not apply #

Two limits, and both are about the strip rather than about the group.

It is a one-dimensional statement. A genuine map has rows and columns, and its symmetry group is bigger — a rectangle has four symmetries of its own before anything is turned over. The orbit counts for two-dimensional maps would need that larger group and the computation is not done here, because the two-dimensional counts are what nobody can compute anyway.

And it says nothing about which foldings are reachable. A machine that folds every layer at once reaches every state an evenly creased strip has, so the reachability question and the counting question happen to agree on this object — but a quotient by a group is not a statement about how a folding is arrived at, and nothing here should be read as one.

What it costs to compute #

The orbit count is not harder than the folding count and it is worth saying so, because a reader might expect the quotient to be the expensive part.

Every folding is already being enumerated to get the labelled number. Canonicalising one under a group of four is four permutations of an array and three string comparisons. So the object count is the labelled count plus a constant factor, and the constant is small enough that the two computations take the same time to the nearest second at eight stamps.

What is expensive is the enumeration itself, and it is expensive in the way this subject’s counting problems always are: the answer is exponentially larger than the question, so writing it down costs more than deciding anything about it. At nine stamps there are 4,536 foldings and at ten 14,616, and the wall this computation stops at is memory rather than patience.

That is also why the sequence is only taken to eight here. It could be taken further; nothing in the argument would change, and the two things that would be learnt — one more term of a sequence somebody has already computed further, and one more fixed-point count — are not worth the page.

What the states are, and why they are counted that way #

One convention underlies every number above and it is worth stating because it is the one place a different choice would give a different sequence.

A folding is recorded as a state: for every pair of segments that actually lie over one another, which of them is higher. Two segments that never overlap are not stacked in any observable sense, and recording a total order over them would count bookkeeping as paper.

On an evenly creased strip the distinction is empty, because every segment lands on every other — which is exactly why the counts here reproduce the published sequence without adjustment, and why the convention could be adopted without disturbing anything. On an unevenly creased strip it is not empty at all, and any attempt to extend this essay’s group action to one would have to be careful about it.