Penguin Brainteaser : 321-avoiding permutations

There are $k$ penguins, $k\ge 3$. They are all different heights. How many ways are there to order the penguins in a line, left to right, so that we cannot find any three that are arranged tallest to shortest (in left to right order)? The penguin triples do not have have to be adjacent.

This problem is courtesy of someone I know only as "DaMancha."

Solution 1:

Nice problem! I'd like to offer the combinatorial bijection that I found. This isn't a rigorous proof but it should give the idea.

Consider a sequence $S$ of penguins such that there are no three descending penguins from left to right, as described above. Let us say that a penguin is a leader if it is taller than all penguins to its left. An important property of the sequence $S$ is that if a penguin is not a leader, then it must be shorter than all penguins to its right.

The penguins will naturally huddle together for warmth leftwards towards the nearest leader; this arranges them into clumps. For example, if $S = 31452$, they will arrange themselves thus: $$(31)(4)(52)$$ In this notation, the clumps are enclosed in parentheses, and the leaders are the first member of each clump: in this case, $3,4,5$.

Let us now draw the peaks and valleys of a Catalonian mountain range corresponding to $S$, as follows: the relative height of each leader with respect to all penguins (not just those in its clump) to its right determines the absolute height of the peak, and the size of the clump determines the relative depth of the next valley below that peak.

For instance, with $(31)(4)(52)$, the first leader, 3 is the $3$rd shortest of all five penguins, and is in a clump of size $2$. The first mountain therefore has a height of $3$ and the following valley is at a distance of $2$ below that peak. The next leader, 4, is the $2$nd shortest among the remaining penguins, and is all alone in his clump. This indicates that the next mountain will have a height of $2$, and the next valley will fall a distance of $1$. The final leader, 5, is also the $2$nd shortest among the now remaining penguins, and is in a clump of size $2$, so the last mountain has height $2$ and the last valley falls a distance of $2$, as it should, back to ground level.

I've made an illustration showing this correspondence: the numbers above the mountains show the height of the peaks and the distance of the valleys below the peaks.

$\hskip2in$

Incidentally, you can see that the sequence $123 \cdots k$ corresponds to a row of $k$ foothills of height $1$, while the sequence $k123 \cdots (k-1)$ corresponds to one giant mountain (perhaps Pica d'Estats?).

Finally, given a mountain range, it is rather straightforward to list off the heights of the penguins; I encourage you to work out the details for yourself!

Solution 2:

For my own benefit last night I worked through a complete argument demonstrating a bijection between the $321$-avoiding permutations of $[n]$ and the Dyck paths of length $2n$. I see that Théophile has posted a delightful sketch of another argument, but I’m going to post this anyway, if only to be able to have easy access to it later. I believe that this bijection is essentially due to Krattenthaler.

Let $\pi=\pi_1\pi_2\dots\pi_n$ be a permutation of $[n]$. A number $\pi_k$ is a left-to-right maximum of $\pi$ at position $k$ if $\pi_k>\pi_i$ for $1\le i<k$. Let $s$ be the number of left-to-right maxima; if they occur at positions $k_1<\ldots<k_s$, let $p_\pi=\langle k_1,\dots,k_s\rangle$ and $m_\pi=\langle\pi_{k_1},\dots,\pi_{k_s}\rangle$. Clearly $\pi_{k_1}<\ldots<\pi_{k_s}=n$, and $k_1=1$. It’s not hard to see that $\pi$ is $321$-avoiding iff the non-maxima occur in increasing order from left to right. Consequently, a $321$-avoiding permutation $\pi$ of $n$ is completely determined by $p_\pi$ and $m_\pi$.

Example: If $n=9$, $p_\pi=\langle1,2,5,7\rangle$, and $m_\pi=\langle 2,5,6,9\rangle$, and $\pi$ is $321$-avoiding, $\pi$ must have the skeleton $25xx6x9xx$, and the remaining members of $[9]$, $1,3,4,7$, and $8$, must appear in that order, so $\pi$ must be $251364978$.

Since $k_1$ is always $1$ and $\pi_{k_s}$ is always $n$, they’re superfluous. Let $r=s-1$, for $i=1,\dots,r$ set $a_i=\pi_{k_i}$, and let $a_\pi=\langle a_1,\dots,a_r\rangle$. It will be convenient to shift the position numbers down by $1$, so for $i=1,\dots,r$ set $d_i=k_{i+1}-1$, and let $d_\pi=\langle d_1,\dots,d_r\rangle$. Note that $\pi$ is still completely determined by $n,a_\pi$, and $d_\pi$.

Example (cont.): For this permutation we have $a_\pi=\langle2,5,6\rangle$ and $d_\pi=\langle1,4,6\rangle$.

Now I’ll show how to use $a_\pi$ and $d_\pi$ to construct a Dyck path of length $2n$. The sequences $a_\pi$ and $d_\pi$ are necessarily increasing, so they can be thought of as the sequences of partial sums of positive sequences $\bar a_\pi$ and $\bar d_\pi$, where $$\bar a_\pi=\langle a_1,a_2-a_1,a_3-a_2,\dots,a_r-a_{r-1}\rangle=\langle\bar a_1,\dots,\bar a_r\rangle$$ and $$\bar d_\pi=\langle d_1,d_2-d_1,d_3-d_2,\dots,d_r-d_{r-1}\rangle=\langle\bar d_1,\dots,\bar d_r\rangle\;.$$

The numbers $\bar a_i$ and $\bar d_i$ are the lengths of the path’s ascents and descents, respectively, consecutively from left to right. That is, the path begins with $\bar a_1$ up-steps, which are followed by $\bar d_1$ down-steps, $\bar a_2$ up-steps, and so on. This produces a path of length $a_r+d_r$, which is always less than $2n$, so we pad it with one more peak consisting of $n-a_r$ up-steps followed by $n-d_r$ down-steps.

Example (cont.): We have $\bar a_\pi=\langle 2,3,1\rangle$ and $\bar d_\pi=\langle 1,3,2\rangle$. Writing $u$ for an up-step and $d$ for a down-step, we have the path $uuduuudddudd$. This is too short: $n=9$, so we want a Dyck path of length $18$, so we pad this one with a single ascent and descent, in this case each of length $3$, to bring it up to the right length: $uuduuudddudduuuddd$.

Of course we have to show both that this procedure is guaranteed to yield a Dyck path, and that every Dyck path of length $2n$ can be obtained in this way.

In order for $\bar a_\pi$ and $\bar d_\pi$ to generate a Dyck path, it must be the case that $a_i\ge d_i$ for $i=1,\dots,r$. By definition $\pi_{k_i}$ must be the largest of the $k_{i+1}-1$ numbers to the left of $\pi_{k_{i+1}}$, so it must be at least $k_{i+1}-1$, and therefore $a_i=\pi_{k_i}\ge k_{i+1}-1=d_i$, and $\bar a_\pi$ and $\bar d_\pi$ do generate a Dyck path.

Conversely, consider a Dyck path of length $2n$ with $s$ peaks. Clearly $s\le n$. Let $r=s-1$. For $i=1,\dots,r$ let $\bar a_i$ be the number of up-steps in the $i$-th peak, and let $\bar d_i$ be the number of down-steps. Let $\bar a=\langle\bar a_1,\dots,\bar a_r\rangle$ and $\bar d=\langle\bar d_1,\dots,\bar d_r\rangle$. For $i=1,\dots,r$ let $a_i=\sum_{j=1}^i\bar a_j$ and $d_i=\sum_{j=1}^i\bar d_j$, and let $a=\langle a_1,\dots,a_r\rangle$ and $d=\langle d_1,\dots,d_r\rangle$. Note that since we started with a Dyck path, necessarily $a_i\ge d_i$ for $i=1,\dots,r$.

We want to construct a $321$-avoiding permutation $\pi$ of $[n]$ such that $a=a_\pi$ and $d=d_\pi$. To construct $\pi$, we place the numbers $a_1,\dots,a_r$, and $n$ at positions $1,d_1+1,\dots,d_r+1$, respectively, and fill in the remaining slots with the members of $[n]\setminus\{a_1,\dots,a_r,n\}$ arranged in increasing order from left to right. The numbers $a_1,\dots,a_r,n$ are distinct, so this certainly produces a permutation $\pi$ of $[n]$ for which $a_\pi=a$ and $d_\pi=d$; the only question is whether $\pi$ is $321$-avoiding.

The permutation $\pi$ will be $321$-avoiding if the numbers $a_1,\dots,a_r,n$ are the left-to-right maxima. Clearly $n$ is a left-to-right maximum, so consider one of the $a_i$: $a_{i+1}$ is in position $d_i+1$, so $a_i$ is a left-to-right maximum iff $a_i\ge\pi_j$ for $j=1,\dots,d_i$, which by construction is the case iff $a_i\ge\pi_{d_i}$. The construction ensures that the $\pi_j$ with $j=1,\dots,d_i$ are $a_1,\dots,a_i$ and the $d_i-i$ smallest remaining positive integers, so $\pi_{d_i}\le d_i\le a_i$, and $\pi$ is $321$-avoiding.

This establishes the desired bijection between $321$-avoiding permutations of $[n]$ and Dyck paths of length $2n$. Since it’s well-known that there are $C_n$ of the latter, where $C_n$ is the $n$-th Catalan number, it follows that there are $C_n$ $321$-avoiding permutations of $[n]$.

Solution 3:

The relevant keyword here is pattern-avoiding permutation and this is actually a surprisingly big area of combinatorics. This particular type of pattern is called 321 and the corresponding permutations are called 321-avoiding permutations.

As it turns out, (xyz)-avoiding permutations of $n$ elements, where (xyz) is any pattern of length $3$, are enumerated by the Catalan numbers $C_n$. One can prove this either by induction or by bijecting to another combinatorial object counted by the Catalan numbers but unfortunately I have forgotten the details of both proofs...