TAOCP 5.1 Exercise 1
Let the inversion table of a permutation $a_1a_2\cdots a_n$ be the sequence $b_1b_2\cdots b_n$, where $b_i$ is the number of entries greater than $i$ that occur to the left of $i$ in the permutation.
Section 5.1: Combinatorial Properties of Permutations
Exercise 1. [**] [10] What is the inversion table for the permutation 271845936? What permutation has the inversion table 50121200?
Verified: no
Solve time: 40m04s
Let the inversion table of a permutation $a_1a_2\cdots a_n$ be the sequence $b_1b_2\cdots b_n$, where $b_i$ is the number of entries greater than $i$ that occur to the left of $i$ in the permutation.
1. Inversion table of $271845936$
The permutation is
$$ 2;7;1;8;4;5;9;3;6. $$
For each $i$, count the entries greater than $i$ that precede $i$.
$$ \begin{aligned} b_1 &= 2, &&\text{since }2,7\text{ precede }1;\[2mm] b_2 &= 0, &&\text{since nothing precedes }2;\[2mm] b_3 &= 5, &&\text{since }7,8,4,5,9\text{ precede }3;\[2mm] b_4 &= 2, &&\text{since }7,8\text{ precede }4;\[2mm] b_5 &= 2, &&\text{since }7,8\text{ precede }5;\[2mm] b_6 &= 3, &&\text{since }7,8,9\text{ precede }6;\[2mm] b_7 &= 0, &&\text{since no entry greater than }7\text{ precedes it};\[2mm] b_8 &= 0, &&\text{since no entry greater than }8\text{ precedes it};\[2mm] b_9 &= 0, &&\text{since no entry greater than }9\text{ precedes it}. \end{aligned} $$
Hence the inversion table is
$$ \boxed{205223000}. $$
2. Permutation with inversion table $50121200$
We are given
$$ (b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8) =(5,0,1,2,1,2,0,0). $$
To reconstruct the permutation, process $i=8,7,\ldots,1$. When inserting $i$, all elements already present are larger than $i$. Therefore $b_i$ is the number of larger elements that must lie to the left of $i$.
Equivalently, if there are $m$ larger elements already present, insert $i$ so that exactly $b_i$ of them are to its left.
$$ \begin{array}{c|c} i & \text{Current list} \ \hline 8 & [8] \[1mm] 7 & [7,8] \quad (b_7=0) \[1mm] 6 & [7,8,6] \quad (b_6=2) \[1mm] 5 & [7,5,8,6] \quad (b_5=1) \[1mm] 4 & [7,8,4,5,6] \quad (b_4=2) \[1mm] 3 & [7,3,8,4,5,6] \quad (b_3=1) \[1mm] 2 & [2,7,3,8,4,5,6] \quad (b_2=0) \[1mm] 1 & [2,7,3,8,4,5,1,6] \quad (b_1=5) \end{array} $$
Thus the permutation is
$$ \boxed{27384516}. $$
Verification:
$$ \begin{aligned} b_1 &= 5 &&\text{( }2,7,3,8,4\text{ precede }1),\ b_2 &= 0,\ b_3 &= 1 &&\text{( }7\text{ precedes }3),\ b_4 &= 2 &&\text{( }7,8\text{ precede }4),\ b_5 &= 1 &&\text{( }7\text{ precedes }5),\ b_6 &= 2 &&\text{( }7,8\text{ precede }6),\ b_7 &= 0,\ b_8 &= 0. \end{aligned} $$
Therefore the inversion table is indeed $50121200$.
Hence the answers are
$$ \boxed{205223000} $$
and
$$ \boxed{27384516}. $$