Where the exponent comes from

A strip of n stamps folds in some number of ways, and the numbers are: 1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376.

Twelve terms, every one obtained by exhaustive search, none by a formula. That is the entire published state of knowledge about a question a child can ask. What can be said about a sequence in that position is what this essay is about, and the answer is: one thing, and it is a ratio.

Reading a growth rate off a list #

Given a sequence with no formula, the first question is how fast it grows, and the crude instrument for that is the ratio of consecutive terms.

Take the numbers above two at a time. 2/1 = 2. 6/2 = 3. 16/6 = 2.667. 50/16 = 3.125. 144/50 = 2.88. 462/144 = 3.208. 1392/462 = 3.013. 4536/1392 = 3.259. 14060/4536 = 3.100. 46310/14060 = 3.294. 146376/46310 = 3.161.

The pattern is immediate and it is not a smooth climb. The ratios alternate high and low, and both alternating subsequences are rising: the odd-indexed ones from 3.000 through 3.125, 3.208, 3.259 to 3.294, and the even-indexed ones from 2.000 through 2.667, 2.880, 3.013, 3.100 to 3.161.

Two monotone sequences approaching each other from opposite sides is the classic picture of a limit, and it is what makes the growth constant plausible rather than proved. A number squeezed between two convergent sequences exists; a number squeezed between two sequences that merely appear to be converging is a conjecture.

Why the terms alternate #

The oscillation has a cause, and identifying it is worth more than the ratio itself, because it says something about the objects rather than about the arithmetic.

A folded strip is a pile of segments, and the folds at each end of the pile wrap around one of two places — the left end or the right. The condition that makes a stacking legal is that two folds wrapping the same place must nest or stand clear and may never interleave.

Add one more stamp to a strip and the new segment’s fold wraps the other end from the previous one. So the constraint an added stamp imposes depends on the parity of n: an even-length strip has its folds distributed evenly between the two ends, an odd-length strip has one more at one end than the other, and the number of ways the extra one can be accommodated differs.

That is a hand-waving version of an argument nobody has completed. It explains the shape of the oscillation and it does not give the amplitude, the rate of convergence, or the limit.

The constant has a ceiling, and it is provable #

Something firmer than a ratio is available, and it comes from the same non-interleaving condition the parity argument rests on.

Every folding of a strip is determined by two things: which folds wrap the left end of the pile and in what nesting, and the same at the right end. Folds wrapping the same end must nest or stand clear, so each end carries a non-crossing family of arcs, and non-crossing families are what Catalan numbers count. A family of $m$ arcs on a line numbers at most the Catalan number $C_m$, which grows as $4^{m}$.

With about $n/2$ folds at each end, the number of foldings is at most $C_{n/2}^{2}$, which grows as $4^{n/2} \times 4^{n/2} = 4^{n}$.

So the growth constant is at most four, and that is an argument rather than an extrapolation. It is loose — most pairs of non-crossing families do not fit together into a single legal pile, which is the whole content of the problem — and it is a ceiling nothing can exceed.

Which brackets the number #

Put the two together and the sequence’s growth constant is confined.

From below, the observed ratios are climbing and the highest computed is 3.294. If the ratios really are monotone — which the twelve terms show and nobody has proved — the limit is at least that.

From above, the non-crossing bound gives four.

So the constant lies between about 3.3 and 4, with the upper end secure and the lower end resting on a monotonicity nobody has established. That is a bracket of about twenty per cent on a quantity the essay opens by saying only one thing can be said about, and the twenty per cent is where sixty years of work has left it.

The gap between the two ends is also informative about where the difficulty is. The bound of four counts the arc families independently; the true constant is smaller because the two ends have to agree with one another. The whole content of stamp folding is that discrepancy, and its size — somewhere around a fifth — is the closest thing available to a measure of how much the two ends constrain each other.

What an unproved growth constant means #

It is worth spelling out what is and is not open here, because “the growth rate is unknown” covers several very different situations.

It is not known that the limit exists. The ratios could in principle oscillate forever without settling, or drift upward without bound at a decreasing rate. Nothing rules those out. What is known is that the sequence is bounded above by something exponential — a folding of n stamps is in particular a permutation of n segments, so the count is at most n!, and much better upper bounds follow from the nesting conditions.

It is not known what the limit is, if it exists. Numerical estimates from long computations put it somewhere above 3.3; the terms available here reach 3.294 and are still rising.

No formula for any term is known, and this is the strongest statement of the three. Not merely no closed form: no recurrence either. The eleventh term is not computed from the tenth by any known rule; it is computed from scratch.

That last point is what makes the sequence unusual rather than merely unsolved. Most combinatorial sequences without closed forms still have recurrences — that is how their terms get extended past the point where enumeration is affordable. This one does not, so every additional term costs the whole enumeration, and the enumeration is exponential in exactly the way the sequence is.

Why the obvious attacks fail #

Four standard techniques, each of which works on sequences that look very like this one, and each of which fails here for a reason worth naming.

A transfer matrix. Count objects built left to right by tracking a bounded amount of state at the frontier, and the count becomes a matrix power whose growth rate is the largest eigenvalue. It fails because the state at the frontier is not bounded: whether a new fold may be added depends on the whole nesting structure built so far, which needs the entire pile to describe.

A generating function. Encode the sequence as a power series and find an equation it satisfies. It fails for the same reason — the recursive decomposition that would produce the equation does not exist.

A bijection. Match the foldings with objects already counted. It fails at n = 4: the sequence begins 1, 2, 6, 16, which is close enough to the Catalan numbers 1, 2, 5, 14 to raise hopes and different enough to end them. Sixteen against fourteen, and nothing standard sits at 1, 2, 6, 16, 50, 144.

A decomposition. Cut the strip in half and combine the halves’ counts. It fails because a fold at one end of the strip can constrain a fold at the other, so the halves are not independent — which is the same non-locality that makes the two-dimensional problem a different problem.

The strips underneath the sequence #

It helps to see the objects the numbers count, at the two or three sizes where a page can hold them, because the sequence’s fourth term is where the intuition breaks and the drawings are what break it.

That last comparison is worth a moment. Four squares in a row fold sixteen ways; the same four squares in a two-by-two block fold eight. More creases, fewer foldings — because the block’s folds constrain each other in both directions while the strip’s constrain each other in one.

Keeping those two apart matters for reading anything written about stamp folding. The sequence 1, 2, 6, 16, 50 counts the ways an evenly creased strip of n stamps can be stacked, over all assignments at once. The number 2ⁿ counts the assignments. Neither is the other, and an evenly creased strip is the case where every assignment folds, which is precisely why the two get muddled.

What was computed here, and how far #

Everything in the figures on this page was computed by lib/mapfold.js while the page was built, up to nine stamps. The tenth takes 0.6 seconds, the eleventh four, the twelfth forty, and the build budget stops at the ninth.

The three larger terms appear as hollow points, quoted with the time they took. That distinction is on the figure’s own face rather than in this text, because a chart that ends at the last cheap point without saying so is a chart about the machine that drew it.

The check that makes those numbers worth anything is not internal. foldcheck requires the enumerator’s output to match the published stamp-folding sequence term by term, including the eleventh, which costs the gate four seconds and is worth it: two different enumeration rules can each be perfectly self-consistent and both wrong, and agreement with a sequence computed by somebody else on a different machine in a different decade is the only evidence that this one counts the same objects.

What is actually being counted #

There is a definitional question hiding under the whole sequence and it deserves stating, because different answers give different numbers and the published sequence uses one particular answer.

A folding is a linear order on the n segments. Two orders are the same folding when — and this is the choice — they are literally the same order, or the reverse of it. Turning the whole pile over does not make a new folding. Nothing else is quotiented out: two orders that differ only by swapping segments that never touch are counted as two.

A folder would object to that last part, and the objection is reasonable: if two layers never overlap, no physical measurement distinguishes their order. Counting them separately is a convention, and it is the convention that produces 1, 2, 6, 16, 50. A different convention produces a different sequence with a different growth rate and the same difficulty.

This is why the machine simulator checks a stacking and its reverse before accepting one: the reverse is the same object under this convention, and a checker that rejected it would be enforcing a different convention than the one the counts are stated in.

What the figure cannot show #

The ratio plot is a plot of eleven numbers, and eleven numbers cannot distinguish a sequence converging to 3.4 from one converging to 3.6, or from one not converging at all. The figure is drawn because it is the best summary available and it should be read as a summary rather than as evidence about the limit.

The other thing it cannot show is what a typical folding looks like. A growth rate says how many there are and nothing about their shape. Somewhere in the 146,376 foldings of a twelve-stamp strip there are some with a deep nested structure and some with almost none, and the count is blind to the difference. Every question of that kind — how deep is a typical folding, how many layers sit over a typical point — needs sampling rather than counting, and sampling from a set nobody can count is its own difficulty.

And the figure shows a strip, so it shows nothing about maps. The two-dimensional growth rate is a separate unknown about a separate sequence, and the analogy between them is an analogy.

What the cost of a term looks like #

The reason the sequence has twelve terms rather than twenty is worth seeing as a curve rather than as a sentence.

Each new stamp multiplies the number of stackings by about three and multiplies the search space by n. So the enumeration gets relatively more efficient as n grows — a larger fraction of what it examines turns out to be an answer — and absolutely more expensive, because both quantities are growing.

A sequence whose growth rate is unknown is a sequence whose cost of extension is also unknown. If the ratio really settles near 3.3, the twentieth term is around 10¹⁰ and out of reach on any machine anybody will build soon. If it climbs, worse. The open question and the computational wall are the same question asked twice.

The idealisation this rests on #

Zero thickness, once again, and here it does something specific rather than general.

A twelve-stamp strip folded flat is twelve layers of paper in one place. Real paper at 0.1 mm makes that 1.2 mm, and the outer folds have to travel further than the inner ones, so the segments would need to be progressively longer to keep the edges aligned. Under that constraint most of the 146,376 foldings stop being achievable, and the ones that survive are the ones whose nesting is shallow.

So the sequence counts an idealised object, and the count grows much faster than the number of foldings anybody could make from real stamps. That is not a criticism of the sequence — it is a reminder that a combinatorial explosion in the geometry does not imply one in the workshop, and that the two questions have not been asked of each other.

What a growth constant would buy #

It is fair to ask what changes if somebody proves the limit exists and names it. Three things, and the third is the one that matters to this subject rather than to the sequence.

The terms become estimable. A growth constant with an error term turns the twentieth stamp number from unknown into approximately known, which is what everybody wants from a sequence they cannot extend.

The enumeration becomes checkable. A computed term that disagreed with the asymptotic prediction by an order of magnitude would be evidence of a bug rather than of a discovery, which is a useful thing to have when every term costs an afternoon and is produced by a single program.

And the structure would have been found. This is the real prize. Growth constants are not proved by staring at ratios; they are proved by finding the decomposition, the recurrence or the subadditivity argument that makes convergence follow. Nobody would prove the stamp numbers converge without in the process discovering why, and the why is what the subject is short of. The constant is the receipt, not the purchase.

That is the honest reason a numerical estimate of 3.3-something is unsatisfying rather than nearly sufficient. It is an answer to the question that was asked and no answer at all to the question underneath it, which is what a folded strip is made of.

Who computed these, and when #

The stamp-folding sequence appears in the recreational literature well before anybody counted many terms of it. W. F. Lunnon computed the values in 1968 and 1971 along with the two-dimensional map counts, and the terms have been extended since by brute force alone. Stanisław Ulam is usually credited with putting the map version into circulation as a problem.

The growth-rate question is the one that has attracted the most work and yielded the least. That the ratios oscillate is elementary; that they appear to converge is numerical; that they do converge is not known. A sequence with twelve published terms, sixty years of attention and no recurrence is a good advertisement for how far a subject’s difficulty can be from its subject’s simplicity.

Where the ladder goes next #

This is a rung about what can be said when a computation is all there is. The next one turns the same scrutiny on this site’s own machinery: assertFlatFoldable is a filter with a blind spot, the blind spot is exactly the region these counting problems live in, and naming it precisely is more useful than any of the reassurance a green check mark provides.