Exercise 1. [**] [16] What tableaux $(P,Q)$ correspond to the two-line array

$$\begin{array}{ccccccccc} 1&2&3&4&5&6&7&8&9\ 6&4&9&5&7&1&2&8&3 \end{array}$$

in the construction of Theorem A? What two-line array corresponds to the tableaux

1 [4 | 7]   1 [3 | 7]
P = |2|8 » , Q = |4|5 ?
5 | 9 8) 9

Verified: yes
Solve time: 43m18s

Let

$$ \begin{pmatrix} a_1&a_2&\cdots&a_9\ b_1&b_2&\cdots&b_9 \end{pmatrix}

\begin{pmatrix} 1&2&3&4&5&6&7&8&9\ 6&4&9&5&7&1&2&8&3 \end{pmatrix}. $$

By Theorem A, we construct $P$ by successive applications of Algorithm I to the sequence

$$ 6,4,9,5,7,1,2,8,3, $$

and record in $Q$ the index $i$ of each insertion.

Construction of $P$ and $Q$

Insert $6$:

$$ P_1= \begin{array}{|c|} \hline 6\ \hline \end{array}, \qquad Q_1= \begin{array}{|c|} \hline 1\ \hline \end{array}. $$

Insert $4$. Since $4<6$, $4$ bumps $6$ from the first row and $6$ starts a second row:

$$ P_2= \begin{array}{|c|} \hline 4\ \hline 6\ \hline \end{array}, \qquad Q_2= \begin{array}{|c|} \hline 1\ \hline 2\ \hline \end{array}. $$

Insert $9$. It is appended to the first row:

$$ P_3= \begin{array}{|c|c|} \hline 4&9\ \hline 6\ \hline \end{array}, \qquad Q_3= \begin{array}{|c|c|} \hline 1&3\ \hline 2\ \hline \end{array}. $$

Insert $5$. In the first row, $5$ bumps $9$; then $9$ is appended to the second row:

$$ P_4= \begin{array}{|c|c|} \hline 4&5\ \hline 6&9\ \hline \end{array}, \qquad Q_4= \begin{array}{|c|c|} \hline 1&4\ \hline 2&3\ \hline \end{array}. $$

Insert $7$. It is appended to the first row:

$$ P_5= \begin{array}{|c|c|c|} \hline 4&5&7\ \hline 6&9\ \hline \end{array}, \qquad Q_5= \begin{array}{|c|c|c|} \hline 1&4&5\ \hline 2&3\ \hline \end{array}. $$

Insert $1$. It bumps $4$ from row $1$; $4$ bumps $6$ from row $2$; $6$ starts a third row:

$$ P_6= \begin{array}{|c|c|c|} \hline 1&5&7\ \hline 4&9\ \hline 6\ \hline \end{array}, \qquad Q_6= \begin{array}{|c|c|c|} \hline 1&4&5\ \hline 2&3\ \hline 6\ \hline \end{array}. $$

Insert $2$. It bumps $5$; then $5$ bumps $9$; then $9$ is appended to the third row:

$$ P_7= \begin{array}{|c|c|c|} \hline 1&2&7\ \hline 4&5\ \hline 6&9\ \hline \end{array}, \qquad Q_7= \begin{array}{|c|c|c|} \hline 1&4&5\ \hline 2&3\ \hline 6&7\ \hline \end{array}. $$

Insert $8$. It is appended to the first row:

$$ P_8= \begin{array}{|c|c|c|c|} \hline 1&2&7&8\ \hline 4&5\ \hline 6&9\ \hline \end{array}, \qquad Q_8= \begin{array}{|c|c|c|c|} \hline 1&4&5&8\ \hline 2&3\ \hline 6&7\ \hline \end{array}. $$

Insert $3$. It bumps $7$; then $7$ is appended to the second row:

$$ P_9= \begin{array}{|c|c|c|c|} \hline 1&2&3&8\ \hline 4&5&7\ \hline 6&9\ \hline \end{array}, \qquad Q_9= \begin{array}{|c|c|c|c|} \hline 1&4&5&8\ \hline 2&3&9\ \hline 6&7\ \hline \end{array}. $$

Therefore

$$ \boxed{ P= \begin{array}{|c|c|c|c|} \hline 1&2&3&8\ \hline 4&5&7\ \hline 6&9\ \hline \end{array}, \qquad Q= \begin{array}{|c|c|c|c|} \hline 1&4&5&8\ \hline 2&3&9\ \hline 6&7\ \hline \end{array} }. $$

For the second part,

$$ P= \begin{array}{|c|c|c|} \hline 1&4&7\ \hline 2&8\ \hline 5&9\ \hline \end{array}, \qquad Q= \begin{array}{|c|c|c|} \hline 1&3&7\ \hline 4&5\ \hline 8&9\ \hline \end{array}. $$

To reconstruct the permutation, remove entries from $P$ in decreasing order of the labels in $Q$.

Label $9$

The entry $9$ of $Q$ occupies the corner cell containing $9$ in $P$.

Delete that corner. No reverse bumping occurs. Hence

$$ p_9=9, $$

and

$$ P= \begin{array}{|c|c|c|} \hline 1&4&7\ \hline 2&8\ \hline 5\ \hline \end{array}. $$

Label $8$

The entry $8$ of $Q$ corresponds to the corner containing $5$.

Delete that corner. Again no reverse bumping occurs:

$$ p_8=5, $$

and

$$ P= \begin{array}{|c|c|c|} \hline 1&4&7\ \hline 2&8\ \hline \end{array}. $$

Label $7$

The entry $7$ of $Q$ corresponds to the corner containing $7$.

Deleting it gives

$$ p_7=7, $$

and

$$ P= \begin{array}{|c|c|} \hline 1&4\ \hline 2&8\ \hline \end{array}. $$

Label $5$

The entry $5$ of $Q$ corresponds to the corner containing $8$.

Delete $8$. No reverse bumping is needed:

$$ p_5=8, $$

and

$$ P= \begin{array}{|c|c|} \hline 1&4\ \hline 2\ \hline \end{array}. $$

Label $4$

The entry $4$ of $Q$ corresponds to the corner containing $2$.

Delete $2$. No reverse bumping occurs:

$$ p_4=2, $$

and

$$ P= \begin{array}{|c|c|} \hline 1&4\ \hline \end{array}. $$

Label $3$

The entry $3$ of $Q$ corresponds to the corner containing $4$.

Delete $4$. Thus

$$ p_3=4, $$

and

$$ P= \begin{array}{|c|} \hline 1\ \hline \end{array}. $$

At this stage the remaining labels in $Q$ are $1,2,6$, all in the first row. Their corresponding entries are the remaining first-row entries of $P$, namely $1,3,6$, in the same positions. Successive deletions therefore give

$$ p_6=6,\qquad p_2=3,\qquad p_1=1. $$

Collecting the values,

$$ (p_1,p_2,\ldots,p_9)

(1,3,4,2,8,6,7,5,9). $$

Hence the corresponding two-line array is

$$ \boxed{ \begin{pmatrix} 1&2&3&4&5&6&7&8&9\ 1&3&4&2&8&6&7&5&9 \end{pmatrix} }. $$

TAOCP 5.1.4 Exercise 1