A notation for 321-avoiding permutations

A permutation can be represented geometrically by placing it above the trivial (sorted) permutation, and drawing a line segment between the two copies of each permuted element. The intersection graph of these line segments is called a permutation graph; it has an edge for every pair of elements whose order is swapped by the permutation.

The permutation graph is bipartite (as it is in this example) exactly when the permutation that it comes from has no three elements whose ordering is reversed; that is, when it avoids the pattern 321. In this case, we can describe the permutation more succinctly with a convenient textual representation. For a permutation of \( n \) elements, look at the tops and bottoms of the line segments in each of the \( n \) positions in left to right order, and write down one of the five symbols ">", "/", "\", "<", or "|" to match the orientations of the two segment endpoints in each position. In this example, for instance, in the first position (with a 3 on top and a 1 on the bottom) both endpoints are of segments that extend rightward, matching the orientation of the top and bottom points in the symbol ">", so we would write a ">" in this position. The notation for the permutation 312479568 given in the example would be ">/<|>></<". You can recover the line segments that this string describes (and therefore also the permutation that we started with) by drawing segments that connect the top and bottom points of each vertical bar, the \( i \)th rightward-pointing endpoint on the top to the \( i \)th leftward-pointing endpoint on the bottom, and the \( i \)th leftward-pointing endpoint on the top to the \( i \)th rightward-pointing endpoint on the bottom.

A string composed of the five characters ">", "/", "\", "<", and "|" represents a valid 321-avoiding permutation whenever the ">" and "<" characters are arranged (like parentheses) into nesting pairs, whenever the "|" character is not enclosed within any of these nested pairs, and whenever the "/" and "\" characters are all enclosed in at least one such pair. If there is any position in the middle of the string that is not enclosed in a nested pair of ">" and "<" characters, then the graph is disconnected. If there are x consecutive slash characters (or \( x \) consecutive backslash characters) inside \( y \) nested pairs of ">" and "<" characters, then the graph contains a complete bipartite subgraph of the form \( K_{y,x+y}. \)

These strings can also be interpreted as a sequence of instructions for constructing a bipartite permutation graph directly, using two queue data structures for the two color classes (red and blue) of vertices in the graph. A ">" character is an instruction to enqueue two new vertices, one of each color, and attach them to each vertex of the opposite colors in the queues (including each other). A "<" character is an instruction to dequeue two vertices, one of each color. A "/" character is an instruction to enqueue a new blue vertex, adjacent to all vertices in the red queue, and dequeue another blue vertex; similarly a "\" character is an instruction to enqueue a new red vertex and dequeue an old one. A "|" character is an instruction to create a new isolated vertex.

How many of these character sequences of length \( n \) (and 321-avoiding permutations of \( n \) elements) are there? It's easy to write down a recurrence relation describing the requirements that the ">" and "<" characters be nested properly, that the "|" characters be outside the nesting, and that the slash and backslash characters be inside the nesting. When you do, and then solve the recurrence, you'll find that you get the Catalan numbers! These numbers count nested sequences of \( 2n \) parentheses, but what happened to the bars and slashes? Why don't they change the form of the enumeration?

Here's a partial explanation. It turns out that we can translate our five characters into pairs of parentheses in an unambiguous way. The translations are:

• ">" → "(("
• "<" → "))"
• "|" → "()"
• "/" → "()"
• "\" → ")("

For example, the string ">/<|>></<" from our example would be translated in this way into the string "((()))()(((())()))". We can reverse the translation by breaking a sequence of \( 2n \) parenthesis characters into pairs of characters and looking up the reverse translation for each pair. One pair, "()", has two different reverse translations, "|" or "/", but which of these two to use can be determined by whether the pair occurs within some other nested parentheses or not. In this way, we get a one-to-one transformation between length-\( n \) strings that represent of 321-avoiding permutations and length-\( 2n \) strings of balanced parentheses. Since the strings of parentheses are counted by the Catalan numbers, so are the 321-avoiding permutations.

---

Comments: