Generate meanders and stamp foldings

Generate meanders, stamp foldings, and relatives of length $n$.
Object type
String length $n$ (max. 20)
Output format
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 horizontally 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		 stamp
foldings		 unlabeled
stamp
foldings		 semi-
meanders		 symmetric
semi-
meanders		 open
meanders		 symmetric
meanders
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:

Download source code

[Zipped C source code (GNU GPL)]

References