In how many ways can you fold a strip of stamps?

When was the last time you used a postage stamp? Even if it was a long time ago, you may have hold in your hands a strip of stamps. Maybe you have even tried to fold it into a stack, one stamp wide, so that the strip was easier to store. Have you ever wondered how many ways are there to do so?

Credit: Joe Haupt's flickr
Credit: Joe Haupt’s flickr

This problem was stated by Lucas 1 in 1891 and today, more than 120 years later, there is still no formula answering the question. A recent paper by Stéphane Legendre2 reviews the problem and adds some new results.

First, the labeled case is considered, where the stamps can be distinguished (as in the previous picture). For a mathematical model, you can label them 1,2,\ldots,n consecutively along the unfolded strip. The goal is then to find all the possible stacks being 1 stamp wide and n stamps tall.

The following figure shows all the possibilities for a strip of n=4 stamps. Horizontal segments represent the stamps, while vertical segments represent the perforations. In addition, the label of each stamp is depicted next to it.

Credit: Legendre (2014)
Credit: Legendre (2014)

Those strings of numbers suggest to consider a useful notion in Mathematics, that of a permutation. Reading the labels downwards, from the top of the stack to the bottom, we can unambiguously identify a folding with a permutation. Interestingly, not all the possible permutations lead to feasible foldings: For an example, the permutation (1324) is not a folding because a crossing would show up.

The question of which permutations do correspond to a folding was settled by Koehler3 in 1968:

A permutation p is a folding if, and only if, neither the inequalities

p(i)%%less_than%%p(j)%%less_than%%p(i+1)%%less_than%%p(j+1)

nor any of their circular rearrangement occur with i and j having both the same parity (odd or even).

Note that in the example (1324) above, the inequalities arise for i=1 and j=3.

As for the question of the number of foldings, Sainte-Laguë4 observed in 1937 that:

The number of elements of the set T_n of foldings of n labeled stamps is

t(n)=n\cdot r(n),

where r(n) is the number of elements of the set R_n of n-foldings of type (1\ldots), i.e., with stamp 1 on top.

This allows to focus on the set R_n which, usefully, can be constructed in an inductive way by using a tree of depth n. The following figure shows the tree describing the sets R_n for n=1,\ldots,5.

Credit: Legendre (2014)
Credit: Legendre (2014)

It turns out that, below the second level, the left and the right subtrees are topologically identical. The reason is that if (1ab\ldots yz) is a folding, then the “reversed” permutation (1zy\ldots ba) is also a folding.

Thus, each folding (1\ldots 2\ldots 3\ldots) in the left subtree is uniquely associated with a folding (1\ldots 3\ldots 2\ldots) in the right subtree. This implies that r(n) is even for n\geq 3 and, more important, that the problem can be reduced to focusing on foldings of type (1\ldots 2\ldots 3\ldots). Lunnon5 proposed an algorithm for listing these foldings, using a depth-first search.

The above results have allowed to compute the number t(n) of labeled foldings up to n=45, for which 37384929247793935264200 possibilities arise. The whole list of numbers can be checked as the sequence A000136 of the On-Line Encyclopedia of Integer Sequences6.

The case of blank stamps is also considered by Legendre. In this case the stamps are not labeled, so that the foldings have to be distinguished according to their shapes. In particular, different labeled foldings might lead to the same unlabeled folding. For an example, consider the second and fourth cases (left to right) in the first row of Figure 2, being one a reflection of the other.

Luckily enough, the corresponding set of unlabeled foldings can also be constructed inductively using a tree. The following figure shows the foldings of n blank stamps for n=1,\ldots,5.

Credit: Legendre (2014)
Credit: Legendre (2014)

Again, the number b(n) of different unlabeled foldings is known up to n=45, for which 9346232311986692725748 possibilities arise. The whole list of numbers is available as the sequence A001011 of the On-Line Encyclopedia of Integer Sequences7.

Provided that there is no formula for the number of foldings, a classical question is wondering about the asymptotics. I.e., how is this number growing when n grows? Legendre cites several authors to support the general believing that the number of n-foldings is of the form K\cdot n^{\alpha}\cdot \lambda^{n}, with K,\alpha being constants which, of course, are not known. That is, an exponential growth.

In order to provide an estimation of lambda, Legendre shows that the number of foldings for all the cases considered above, t(n),r(n),b(n), share the same \lambda. Then, he uses the best known values to obtain an estimation up to the tenth decimal position.

Overall, this is a nice review of a problem which, despite seeming harmless, explodes for not so large cases due to the exponential growth of the number of combinations.

References

  1. E. Lucas. Théorie des Nombres, Vol. 1, Gauthier-Villars, Paris, 1891, page 120.
  2. Legendre S. (2014). Foldings and meanders, Australasian Journal of Combinatorics, 58 (2) 275-291. DOI:
  3. J.E. Koehler. Folding a strip of stamps, Journal of Combinatorial Theory, 5:2 (1968), pages 135-152.
  4. A. Sainte-Laguë. Avec des Nombres et des Lignes, Vuibert, Paris, 1937, pages 147-162.
  5. W.F. Lunnon. A map folding problem, Mathematics of Computation, 22:101 (1968), pages 193-199.
  6. Sequence A000136, On-Line Encyclopedia of Integer Sequences.
  7. Sequence A001011, On-Line Encyclopedia of Integer Sequences.

Written by

8 comments

Leave a Reply

Your email address will not be published.Required fields are marked *