TAOCP 5.2.1 Exercise 11

Let \pi = (1,2,5,3,7,4,8,6,9,11,10,12).

taocpmathematicsalgorithmsvolume-3math-simple

Section 5.2.1: Sorting by Insertion

Exercise 11. [M10] [M10] What path in a lattice like that of Fig. 11 corresponds to the permutation 12537486911 10 12?

Verified: yes
Solve time: 2m59s

Let

$$ \pi = (1,2,5,3,7,4,8,6,9,11,10,12). $$

We use the standard TAOCP boundary construction: the lattice path from $(0,0)$ to $(n,n)$ is determined by

$$ x_k = #{, i \le k : \pi(i) \le k ,}, \qquad k=1,\dots,n. $$

At each stage $k$, the path takes one east step, and then a number of north steps equal to $x_k - x_{k-1}$, with $x_0=0$.

Step 1: Compute $x_k$

We evaluate $x_k$ directly from the permutation.

  • $k=1$: only $\pi(1)=1$, so $x_1=1$.
  • $k=2$: $\pi(1),\pi(2)=1,2$, so $x_2=2$.
  • $k=3$: values $1,2,5$, so $x_3=2$.
  • $k=4$: values $1,2,5,3$, so $x_4=3$.
  • $k=5$: values $1,2,5,3,7$, so $x_5=4$.
  • $k=6$: values $1,2,5,3,7,4$, so $x_6=5$.
  • $k=7$: values $1,2,5,3,7,4,8$, so $x_7=6$.
  • $k=8$: values $1,2,5,3,7,4,8,6$, so $x_8=8$.
  • $k=9$: values $1,2,5,3,7,4,8,6,9$, so $x_9=9$.
  • $k=10$: values $1,2,5,3,7,4,8,6,9,11$, so $x_{10}=9$.
  • $k=11$: values $1,2,5,3,7,4,8,6,9,11,10$, so $x_{11}=11$.
  • $k=12$: all elements $1,\dots,12$, so $x_{12}=12$.

Thus

$$ (x_1,\dots,x_{12}) = (1,2,2,3,4,5,6,8,9,9,11,12). $$

Step 2: Compute vertical increments

Let $\Delta_k = x_k - x_{k-1}$. Then

$$ (\Delta_1,\dots,\Delta_{12}) = (1,1,0,1,1,1,1,2,1,0,2,1). $$

Step 3: Construct the lattice path

The path consists of 12 east steps, with north steps inserted according to the increments:

  • $k=1$: $E,N$
  • $k=2$: $E,N$
  • $k=3$: $E$
  • $k=4$: $E,N$
  • $k=5$: $E,N$
  • $k=6$: $E,N$
  • $k=7$: $E,N$
  • $k=8$: $E,N,N$
  • $k=9$: $E,N$
  • $k=10$: $E$
  • $k=11$: $E,N,N$
  • $k=12$: $E,N$

Final answer

The lattice path corresponding to

$$ (1,2,5,3,7,4,8,6,9,11,10,12) $$

is the monotone path from $(0,0)$ to $(12,12)$ obtained by the step sequence above, equivalently the path with east steps at each $k$ and north steps distributed according to

$$ (x_1,\dots,x_{12}) = (1,2,2,3,4,5,6,8,9,9,11,12). $$

This uniquely determines the required boundary path.