Skip to main content

MA 415G course notes

Benjamin Braun

Section 3.7 Stack Sortable Permutations

Our final classification problem arises in the context of sorting permutations. The sorting problem is as follows: given a permutation \(\pi\in \ss_n\text{,}\) produce an efficient algorithm to sort the permutation so that the result is the identity element.
🔗
One way to think about sorting a permutation is that we would need to eliminate inversions one at a time, until no inversions remain -- this would yield the identity permutation. A simple sorting algorithm of this type that is horribly inefficient and never used is bubble sort, defined as follows.
🔗

Definition 3.7.1.

A pass in the bubble sort algorithm applied to a permutation \(\pi\) does the following:
  • For \(i\) from \(1\) to \(n-1\text{:}\)
    🔗
    • if \(\pi_i\gt \pi_{i+1}\text{,}\) swap those entries.
      🔗
      🔗
    🔗
🔗
The bubble sort algorithm consists of making \(n-1\) passes through the permutation.
🔗
🔗

Example 3.7.2.

Bubble sort applied to the permutation \(35142\) does the following on pass 1:
\begin{equation*} 35142, 31542, 31452, 31425 \end{equation*}
Note that the effect of the first pass is to move \(5\) to the final position.
🔗
On pass 2, we start with \(31425\) and obtain:
\begin{equation*} 13425, 13425, 13245 \end{equation*}
Note that the effect of the second pass is to move \(4\) to the second to last position.
🔗
On pass 3, we start with \(13245\) and obtain:
\begin{equation*} 13245, 12345, 12345 \end{equation*}
Note that the effect of the second pass is to move \(3\) to the third to last position.
🔗
We would run through the remaining passes without making any further changes, since the permutation is now sorted.
🔗
🔗

Checkpoint 3.7.3.

Apply the bubble sort algorithm to \(624135\text{.}\)
🔗
🔗
There are many interesting sorting algorithms! See https://en.wikipedia.org/wiki/Sorting_algorithm for a list. Our next goal is to investigate a sorting algorithm created by Knuth that does not always work, but leads to very interesting mathematics.
🔗

Definition 3.7.4.

Given a permutation \(\pi\in \ss_n\text{,}\) we create two additional objects: a "vertical stack" \(S\) that starts empty and a list \(L\) that starts empty. First, add \(\pi_1\) to the stack. Second, if \(\pi_2\lt \pi_1\text{,}\) place \(\pi_2\) on the stack above \(\pi_1\text{;}\) otherwise, place \(\pi_1\) into the list and add \(\pi_2\) to the stack.
🔗
For each subsequent step, compare the next element \(\pi_i\) in the permutation with the top element of the stack.
  • If \(\pi_i\) is smaller than the top entry of the stack, add \(\pi_i\) to the stack.
    🔗
    🔗
  • Otherwise, while \(\pi_i\) is larger than the top entry, iterate moving the top entry of the stack to the right end of the list. Once \(\pi_i\) is smaller than the top entry of the stack, move \(\pi_i\) to the top of the stack.
    🔗
    🔗
Continue until every element of the permutation has been analyzed, and any elements that are left in the stack we pop sequentially and add to the right side of the list.
🔗
If a permutation is correctly sorted by this operation, then we call it 1-stack sortable, or just stack sortable.
🔗
🔗
In the notes, I will use the vector transpose notation \(S=(s_1,s_2,s_3,s_4,\ldots,s_k)^T\) to denote the vertical stack with \(s_1\) on top and \(s_k\) at the bottom of the stack.
🔗

Example 3.7.5.

Consider \(4132\text{,}\) with stack \(S\) and list \(L\text{.}\) We start by setting \(S=(4)\text{.}\) The next element is \(1\text{,}\) which is less than \(4\text{,}\) so we put \(1\) at the top of the stack yielding \(S=(1,4)^T\text{.}\)
🔗
The next element is \(3\text{,}\) which is greater than \(1\text{,}\) so we move \(1\) to the list \(L=1\) and put \(3\) in the stack \(S=(3,4)^T\text{.}\)
🔗
The next element is \(2\text{,}\) which is less than \(3\text{,}\) so we put \(2\) at the top of the stack to yield \(S=(2,3,4)^T\text{.}\)
🔗
At this point, we sequentially pop each remaining element from the top of the stack, appending to \(L\text{,}\) yielding \(L=1234\text{.}\)
🔗
🔗

Example 3.7.6.

Consider \(\pi=624351\text{,}\) with stack \(S\) and list \(L\text{.}\) Then our process yields:
  1. \(\pi=24351\text{,}\) \(S=(6)\text{,}\) \(L\) empty.
    🔗
    🔗
  2. \(\pi=4351\text{,}\) \(S=(2,6)^T\text{,}\) \(L\) empty.
    🔗
    🔗
  3. \(\pi=351\text{,}\) \(S=(4,6)^T\text{,}\) \(L=2\text{.}\)
    🔗
    🔗
  4. \(\pi=51\text{,}\) \(S=(3,4,6)^T\text{,}\) \(L=2\text{.}\)
    🔗
    🔗
  5. \(\pi=1\text{,}\) \(S=(5,6)^T\text{,}\) \(L=234\text{.}\)
    🔗
    🔗
  6. \(S=(1,5,6)^T\text{,}\) \(L=234\text{.}\)
    🔗
    🔗
  7. \(L=234156\text{.}\)
    🔗
    🔗
🔗
Note that the resulting list is not correctly ordered.
🔗
🔗

Checkpoint 3.7.7.

What caused the permutation above to NOT be sorted correctly by the stack sorting process?
🔗
🔗

Checkpoint 3.7.8.

Which of the following permutations are 1-stack sortable?
  1. \(\displaystyle 83426517\)
    🔗
    🔗
  2. \(\displaystyle 21436587\)
    🔗
    🔗
  3. \(\displaystyle 87654321\)
    🔗
    🔗
  4. \(\displaystyle 43218756\)
    🔗
    🔗
  5. \(\displaystyle 31527864\)
    🔗
    🔗
🔗
🔗
We will see that there is a simple criteria that characterizes whether or not a permutation is stack sortable, involving the following definition.
🔗

Definition 3.7.9.

We say that a permutation \(\pi\in \ss_n\) contains the pattern \(231\) if there exist indices \(i\lt j\lt k\) such that
\begin{equation*} \pi_j\gt \pi_i\gt \pi_k \, . \end{equation*}
If \(\pi\) does not contain the pattern \(231\text{,}\) then we say that \(\pi\) is \(231\)-avoiding.
🔗
🔗

Example 3.7.10.

The permutation \(\pi=364512\) contains the pattern \(231\text{,}\) for example since
\begin{equation*} \pi_1=3, \pi_2=6, \pi_6=2 \end{equation*}
and this is a \(231\) pattern.
🔗
🔗

Checkpoint 3.7.11.

Which of the following permutations are \(231\)-avoiding?
🔗
  1. \(\displaystyle 83426517\)
    🔗
    🔗
  2. \(\displaystyle 21436587\)
    🔗
    🔗
  3. \(\displaystyle 87654321\)
    🔗
    🔗
  4. \(\displaystyle 43218756\)
    🔗
    🔗
  5. \(\displaystyle 31527864\)
    🔗
    🔗
🔗

Proof.

We first prove that if \(\pi\) is stack sortable then it is \(231\)-avoiding. Suppose that the opposite happened, i.e., that there exist \(i\lt j\lt k\) where
\begin{equation*} \pi_j=b \gt \pi_i=a \gt \pi_k=c \, , \end{equation*}
where we use the names \(a,b,c\) to simplify notation. When we get to \(c\) in the stack sorting process, there are several possibilities for what has occurred previously in the process.
  • If \(a\) or \(b\) have already been popped from the stack, then that value will appear before \(c\) in the list, which would result in the final list being out of order. So, we must have both \(a\) and \(b\) in the stack when \(c\) is considered in the sorting process.
    🔗
    🔗
  • Note that in the stack when \(c\) is considered, we must have \(a\) below \(b\) in the stack, because \(a\) was pushed onto the stack before \(b\) since \(a\) was considered first in the sorting process:
    \begin{equation*} S=(s_1,\ldots,b,\ldots,a,\ldots,s_k)^T \end{equation*}
    We must pop \(c\) before \(a\) and \(b\text{,}\) and as the process continues, we must pop \(b\) from the stack before we pop \(a\text{.}\) However, this will result in \(b\) appearing before \(a\) in the final list, which would put the elements out of order. Therefore, cannot have a \(231\)-pattern in \(\pi\text{.}\)
    🔗
    🔗
🔗
We next prove that if \(\pi\) avoids \(231\) then it is stack sortable. For any two elements \(a\) and \(b\) such that \(a\) comes before \(b\) in \(\pi\text{,}\) if \(a\gt b\) then there is not a value \(c\gt a\) between \(a\) and \(b\) in \(\pi\text{.}\) Thus, \(a\) will enter the stack and will not leave until \(b\) has left the stack, meaning that \(b\) will come before \(a\) in the list, as desired. If \(a\lt b\text{,}\) then \(a\) will enter and leave the stack before \(b\) enters the stack, and again they will appear in the correct order in the list. Since this is true for all pairs \(a\) and \(b\text{,}\) the stack sorting procedure will correctly sort the permutation.
🔗
🔗

Checkpoint 3.7.13.

Discuss the proof above. Does it make sense? Why or why not? Compare this proof with the examples you computed earlier.
🔗
🔗
There is a beautiful connection between the classification of stack sortable permutations and enumeration.
🔗

Checkpoint 3.7.15.

Use the recurrence to compute the first seven Catalan numbers.
🔗
🔗

Proof.

Let \(\pi\in \ss_n\) be \(231\)-avoiding. In this case, every entry to the left of \(n\) in \(\pi\) must be less than every entry to the right of \(n\) in \(\pi\text{.}\) Thus, if \(\pi_{i}=n\text{,}\) we have
\begin{equation*} \pi=\tau n\sigma \end{equation*}
where \(\tau\) is a \(231\)-avoiding permutation of \(\{1,\ldots,i-1\}\) and \(\sigma\) is a \(231\)-avoiding permutation of \(\{i,\ldots,n-1\}\text{.}\) Thus, there are \(C_i\) possible \(\tau\) and \(C_{n-1-i}\) possible \(\sigma\text{.}\) As \(n\) can be in any position in \(\pi\text{,}\) this shows that there are
\begin{equation*} \sum_{i=0}^{n-1}C_iC_{n-1-i} \end{equation*}
possible \(231\)-avoiding permutations in \(\ss_n\text{.}\)
🔗
We will omit the proof that the formula
\begin{equation*} C_n=\frac{1}{n+1}\binom{2n}{n} \end{equation*}
satisfies the Catalan recurrence, but if you are interested in seeing it then you can search online and easily find proofs using the technique of generating functions (i.e., power series).
🔗
🔗
🔗
PrevTopNext