Generate meanders and stamp foldings

Generate meanders, stamp foldings, and relatives of length $n$.
 Object type open meanders semi-meanders stamp foldings symmetric meanders symmetric semi-meanders unlabeled stamp foldings String length $n$ (max. 20) Output format graphics (≤500 objects) text (≤10000 objects) file (≤100000 objects)
Output  numbering graphics

Object info

Consider a strip of $n$ stamps numbered $1,2,\ldots,n$. Such a strip 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 may be stretched around any number of other stamps. Any such way of folding the stamps to a flat pile is called a stamp folding, where we always orient the pile vertically with the perforations facing up and down, so that the perforation between stamps 1 and 2 is at the bottom. We can represent such a folding as a permutation $\pi=(\pi(1),\pi(2),\ldots,\pi(n))$, where $\pi(i)$ is the stamp at position $i$ in the pile when considering it from left to right.

By ignoring the labeling of the stamps (stamp $i$ is identified with stamp $n+1-i$) and the orientation of the pile (we may swap left and right) we obtain unlabeled stamp foldings. A semi-meander is a stamp folding in which stamp 1 can be seen from above. A symmetric semi-meander is a semi-meander in which stamp 2 is left of stamp 1. An open meander is a stamp folding in which stamp 1 can be seen from above left, and stamp $n$ can be seen from above right if $n$ is even and from the bottom (right) if $n$ is odd. Meanders count the number of ways that a river flowing from west to east, starting in the north-west and ending in the north-east if $n$ is even and the south-east if $n$ is odd, crosses a straight line. Symmetric meanders are obtained by considering open meanders modulo east-west symmetry. The following figure shows all the different variants for $n=4$, where stamp 1 is marked by a little dot, and the gray horizontal line shows the left-to-right order in which we consider the pile of stamps.

 permu-tations stampfoldings unlabeledstampfoldings semi-meanders symmetricsemi-meanders openmeanders symmetricmeanders 1 4321 =16 2 3421 =15 3 3214 =12 =12 4 2431 =13 5 2341 =12 6 4213 =13 7 2143 8 2134 =15 9 4312 =15 10 3412 =7 11 3124 =13 12 1432 =5 13 1342 =4 14 4123 =12 =3 15 1243 =2 16 1234 =1

The algorithms running on this website are described in Sawada and Li's paper [SL12].

Enumeration (OEIS)

The number of symmetric semi-meanders is exactly half the number of semi-meanders, but apart from this, there are no other trivial relations between those six sequences.

Links to the objects in the Online Encyclopedia of Integer Sequences:

References

• [SL12] J. Sawada and R. Li. Stamp foldings, semi-meanders, and open meanders: fast generation algorithms. Electron. J. Combin., 19(2):Paper 43, 16, 2012.