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 | - | - |