[Information Index] [Generation Index] [COS homepage]

Information on Stamp Foldings

Consider a strip of stamps as shown in the figure below. There are n stamps numbered 1,2,...,n, from left to right and each stamp has a side with a design (the top side) and a side with gum (the bottom side).

Such a strip of stamps may be folded in a variety of ways along the perforations to create a "flat" pile of n stamps. In creating this folding we assume that the perforations are perfectly elastic and so may be stretched any distance. How many such foldings are there?

Mathematically, a Stamp Folding is a permutation of numbers from 1 through n which represent a folding of a strip of n stamps. The stamps are considered to be labelled from 1 through n, with a connection (or perforation) between stamp k and stamp k + 1. Each stamp is considered to have a right and left side. A permutation of {1, ..., n} represents a folding of a strip of n such stamps so long as it corresponds to an actual stamp folding obtained in the following way:

Repeatedly fold the strip of n stamps at the perforations until the folding is the size of one stamp. Orient the folding so the stamp labelled 1 is facing up and oriented with respect to its right and left sides. Read the stamp labels from the top of this pile downwards. (This is the order the permutation occurs in).

Here is an example diagramming all the stamp foldings of length 4.

Using the above scenario, some diagrams of stamp foldings will be almost identical to others (compare 1234 and 4321 in the diagram above). In order to remove some of the symmetries, we can restrict the orientations to those in which the first stamp in the sequence has a lower value than the last. Thus 1234 will occur, but 4321 will not. Shown below is a diagram of all stamp foldings of length 4 with this one type of symmetry removed. There are exactly half as many folding as with the unrestricted case. Thus, these sequences will have a count which equals half of N(n) (mentioned below).

Another symmetry still exists in the above diagram. For example, compare 3214 and 1432. By ignoring top and bottom faces and which free end is labelled 1 (as opposed to being labelled n), these stamp foldings are the same. The following diagram illustrates stamp foldings of length 4 with this additional symmetry removed as well. These lists will have a count which equals U(n) (mentioned below), as the removal of both symmetries is identical to considering that the strips are not labelled. The lexicographically lowest element is taken as canonical.

Similar to a stamp folding is what V.I. Arnol'd calls a meander. A meander is the number of ways a river flowing from the South-West to the East can cross a West-East road n times. These objects are similar to stamps, and correspond precisely to those stamp foldings which have unenclosed ends on the diagram. The generation program considers the South-West (i.e. lower) entrance to be labelled 1 and the East (i.e. upper) exit to be labelled n, similar to stamps. The diagram below illustrates all the meanders of length 5. The length of each list corresponds to M(n) (mentioned below).

A variation of the meander is the closed meander. These are all meanders as described above such that the two ends of the river are joined together. This joining of the ends creates an extra crossing of the road. Also, all closed meanders must have an even number of crossings (for obvious reasons). In fact the number of closed meanders with 2n crossings is equal to M(2n - 1). The generation program inputs the value n and generates closed meanders of length 2n. Shown below is a diagram illustrating all the closed meanders of length 6 (i.e. n = 3).

N(n) = number of labelled oriented foldings.

S(n) = number of symmetric foldings.

U(n) = number of unlabelled foldings.

M(n) = number of meanders. Also number of simple alternating transit mazes.

In Sloane's database of integer sequences, N(n) corresponds to sequence A000136(M1664), S(n) is sequence A001010(M0323), U(n) is sequence, A001011(M1455), and M(n) is found as sequence A005316(M0874)

n N(n) S(n) U(n) M(n)
1 1 1 1 1
2 2 2 1 1
3 6 2 2 2
4 16 4 5 3
5 50 6 14 8
6 144 8 38 14
7 462 18 120 42
8 1392 20 353 81
9 4536 56 1148 262
10 14060 48 3527 538
11 46310 178 11622 1828
12 146376 132 36627 3926
13 485914 574 121622 13820
14 1557892 348 389560 30694
15 5202690 1870 1301140 110954
16 16861984 1008 4215748 252939
17 56579196 6144 13976335 933458
18 184940388 2812 46235800 2172830
19 622945970 20314 155741571 8152860
20 2050228360 8420 512559185 19304190
21 6927964218 67534 1732007938 73424651
22 22930109884 24396 5732533570 176343390
23 77692142980 225472 - 678390116
24 258360586368 74756 - 1649008456
25 877395996200 755672 - -
26 2929432171328 222556 - -
27 9968202968958 2540406 - -
28 33396290888520 693692 - -
29 113837957337750 8564622 - -


Related Links

Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.