TAOCP 5.1.1 Exercise 21
**Solution** We begin by recalling the relevant definitions.
Exercise 21. ▶ [M25] (G. D. Knott.) Show that the permutation $a_1 \ldots a_n$ is obtainable with a stack, in the sense of exercise 2.2.1–5 or 2.3.1–6, if and only if $C_j \le C_{j+1} + 1$ for $1 \le j < n$ in the notation of exercise 7.
Verified: yes
Solve time: 1h25m
Solution
We begin by recalling the relevant definitions.
Stack‑obtainable permutations.
A permutation (a_1a_2\ldots a_n) is obtainable with a stack (exercises 2.2.1-5 and 2.3.1-6) if it can be the output of a stack whose input is (1,2,\ldots,n).
It is well known (and follows from those exercises) that a permutation is stack‑obtainable iff it avoids the pattern 312, i.e. there are no indices (i<j<k) with (a_i>a_k>a_j).
The inverse permutation and the numbers (C_j).
For a permutation (\pi = a_1a_2\ldots a_n) let (\pi^{-1} = a_1'a_2'\ldots a_n') be its inverse, defined by (a_{\pi_i'}=i) or equivalently (\pi_j' = i \iff a_i = j).
Exercise 7 defines (C_j) as the number of elements that lie to the left of (j) in the inverse permutation (\pi^{-1}) and are greater than (j). In other words, (C_1C_2\ldots C_n) is exactly the inversion table of (\pi^{-1}).
The exercise asks us to prove:
[ \pi \text{ is stack‑obtainable} \quad\Longleftrightarrow\quad C_j \le C_{j+1}+1 ;\text{ for all } 1\le j<n. ]
We shall establish this by combining three facts:
- (\pi) is stack‑obtainable (\iff \pi) avoids 312.
- (\pi) avoids 312 (\iff \pi^{-1}) avoids 231.
- A permutation avoids 231 (\iff) its inversion table (b_1\ldots b_n) satisfies (b_j\le b_{j+1}+1) for all (j).
Since (C_j = b_j(\pi^{-1})), the desired equivalence follows immediately.
1. (\pi) avoids 312 (\iff \pi^{-1}) avoids 231
Proof.
(\pi) contains a 312 pattern (\iff) there exist indices (i<j<k) with (\pi_i > \pi_k > \pi_j).
Set (u = \pi_j,; v = \pi_k,; w = \pi_i). Then (u<v<w) and their positions in (\pi) are (j,;k,;i) with (i<j<k).
In the inverse permutation (\pi^{-1}), the entries at indices (u,v,w) are (\pi^{-1}_u=j,; \pi^{-1}_v=k,; \pi^{-1}_w=i). Because (u<v<w), the values (j,k,i) appear at increasing indices (u,v,w) in (\pi^{-1}). Since (i<j<k), the triple ((j,k,i)) is ordered as middle, largest, smallest - precisely a 231 pattern.
Hence (\pi) contains 312 (\iff \pi^{-1}) contains 231, and the avoidance statements are equivalent. ∎
2. Inversion‑table characterisation of 231‑avoiding permutations
Let (\sigma) be a permutation of ({1,\ldots,n}) with inversion table (b_1,\ldots,b_n) (so (b_j) is the number of elements to the left of (j) that are greater than (j)). We prove:
[ \sigma \text{ avoids 231} \quad\Longleftrightarrow\quad b_j \le b_{j+1}+1 ;\text{ for all } 1\le j<n. ]
((\Rightarrow)) If (\sigma) avoids 231 then (b_j \le b_{j+1}+1).
Fix (j) and let (p=\operatorname{pos}(j)), (q=\operatorname{pos}(j+1)).
Case 1: (p<q) ((j) precedes (j+1)).
Every element (>j+1) left of (j) is also left of (j+1). Hence (b_j \le b_{j+1}), so (b_j \le b_{j+1}+1) holds trivially.
Case 2: (q<p) ((j+1) precedes (j)).
Now (j+1) itself contributes (1) to (b_j). All elements (>j+1) left of (j+1) are counted in both (b_{j+1}) and (b_j). Let (Y) be the number of elements (>j+1) strictly between (q) and (p). Then (b_j = 1 + b_{j+1} + Y).
If (Y>0), choose such an element (x). The three values (j+1,;x,;j) satisfy (j < j+1 < x) and appear in the order (j+1,;x,;j) - a 231 pattern, contradicting the hypothesis. Therefore (Y=0) and (b_j = b_{j+1}+1), so the inequality holds. ∎
((\Leftarrow)) If (b_j \le b_{j+1}+1) for all (j) then (\sigma) avoids 231.
We reconstruct (\sigma) from its inversion table by inserting the numbers (n,n-1,\ldots,1) one by one.
At step (k) (starting with (k=n)) we have a permutation (\tau_{k+1}) of ({k+1,\ldots,n}) (for (k=n) this is the empty list). We insert (k) into (\tau_{k+1}) so that exactly (b_k) elements of (\tau_{k+1}) lie to its left; the new list is (\tau_k).
Note that (b_n=0) so (n) is placed first, giving (\tau_n = (n)).
We prove by induction on (k) (from (n) down to (1)) that each (\tau_k) avoids 231.
Base: (\tau_n = (n)) trivially avoids 231.
Inductive step: Assume (\tau_{k+1}) avoids 231. We insert (k) at position (q = b_k+1) (1‑indexed) in (\tau_{k+1}).
Let (p = b_{k+1}+1) be the position of the smallest element (k+1) in (\tau_{k+1}).
The hypothesis (b_k \le b_{k+1}+1) is exactly (q \le p+1).
Because (\tau_{k+1}) avoids 231, the elements left of (k+1) form a strictly decreasing sequence. (Indeed, if there were an increasing pair (u<v) left of (k+1), then (u,v,k+1) would be a 231 pattern with (k+1) as the smallest element.)
Since (q-1 \le p), the elements that end up left of (k) in (\tau_k) form a prefix of that decreasing sequence, hence they contain no increasing pair.
Now any 231 pattern in (\tau_k) would either lie entirely in (\tau_{k+1}) (impossible by induction) or would have (k) as its smallest element (because (k) is the overall minimum). For the latter, there would have to be an increasing pair to the left of (k), which we have just ruled out.
Therefore (\tau_k) avoids 231.
By induction, (\tau_1 = \sigma) avoids 231. ∎
3. Putting everything together
Let (\pi) be a permutation of ({1,\ldots,n}). Denote by (C_1\ldots C_n) the inversion table of (\pi^{-1}) (exercise 7).
[ \begin{aligned} \pi \text{ is stack‑obtainable} &\iff \pi \text{ avoids 312} \qquad\text{(exercises 2.2.1-5, 2.3.1-6)} \ &\iff \pi^{-1} \text{ avoids 231} \qquad\text{(proved in §1)} \ &\iff \text{the inversion table of } \pi^{-1} \text{ satisfies } C_j \le C_{j+1}+1 ;; (1\le j<n) \qquad\text{(proved in §2)}. \end{aligned} ]
This is exactly the statement to be shown. ∎