Inversion related problem Construction the permutations of {${1,2,....,8}$} whose inversion sequences is
$$2,5,5,0,2,1,1,0$$
Can anyone help me with this problem?  I was gone from class when the professor talked about inversion and the book doesn't this explain this topic well at all.
 A: This definition of a permutation inversion sequence uniquely defines a permutation.
$2,5,5,0,2,1,1,0$ tells us that to the left of the $1$ are two entries greater than $1$:
$$.\;.\;1\;.\;.\;.\;.\;.$$
The next term means that there are five entries left of $2$ greater than $2$, so we count $5$ dots and then place $2$ on the next dot:
$$.\;.\;1\;.\;.\;.\;2\;.$$
Similarly, five entries left of $3$ greater than $3$ means $5$ dots left of $3$:
$$.\;.\;1\;.\;.\;.\;2\;3$$
Next, no entries left of $4$ that are greater than $4$:
$$4\;.\;1\;.\;.\;.\;2\;3$$
Two entries left of $5$ greater than $5$ means $5$ goes on the third dot remaining:
$$4\;.\;1\;.\;5\;.\;2\;3$$
One entry left of $6$ greater than $6$:
$$4\;.\;1\;6\;5\;.\;2\;3$$
One entry left of $7$ greater than $7$:
$$4\;.\;1\;6\;5\;7\;2\;3$$
Zero entries left of $8$ greater than $8$ (which is always the case), and also there is only one dot remaining:
$$4\;8\;1\;6\;5\;7\;2\;3$$
A: The answer is $4,8,1,6,5,7,2,3$  
A: It is easier to start from the other end. Clearly, there are no numbers larger than 8 in the sequence. Place 8 first. For 7, there is one inversion and hence we need to place it after 8. The sequence so far is $8 \, 7$. For 6, there is one inversion and hence we can not place it after 7 or before 8. Thus it must be placed in between. We have now $8, \, 6, \, 7$. For 5, there are two inversions. This forces that 5 must be between 6 and 7 in the above. This yields $8, \, 6, \, 5, \, 7$. for 4 there are no inversions. Hence 4 must be placed before 8 giving $4,\, 8, \, 6, \, 5, \, 7$. For 3, we have 5 inversions. The only place is the last. The sequence now is $4,\, 8, \, 6, \, 5, \, 7, \, 3$. For 2, there are 5 inversions.  The only place is before 3. And finally, for 1, there are 2 inversions and we place it after 8. Thus the required sequence is $4,\, 8, \, 1, \, 6, \, 5, \, 7, \, 2, \, 3$. This algorithm is easily programmable.
The algorithm is as follows:
Having placed $i+1, i+2, \ldots, n$ in the array, starting from the left count up to the number of inversions for $i$ and place $i$ at that place. 
