An Alternative Method for Generating Permutations with Inversion Seqs.

An Alternative Method for Generating Permutations with Inversion Sequences

Recall from The Inversion Sequence of a Permutation that if $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers and $(x_1, x_2, ..., x_n)$ is an $n$-permutation of the elements in $A$ then the inversion sequence of this permutation is a finite sequence $(a_i)_{i=1}^{n} = (a_1, a_2, ..., a_n)$ where for each $j \in \{1, 2, ..., n \}$ we have that $a_j$ is defined to be the number of integers to the left of $j$ in the $n$-permutation $(x_1, x_2, ..., x_n)$ that are larger than $j$.

We have already seen one method on the Generating Permutations with Inversion Sequences for generating $n$-permutations with inversion sequences. The following theorem provides another method that is somewhat less useful but still simple in applying.

Theorem 1: Let $A = \{1, 2, ..., n \}$ be a finite $n$-element set of positive integers and consider the inversion sequence $(a_i)_{i=1}^{n} = (a_1, a_2, ..., a_n)$. First write down the number $n$ with two placeholders $*$ on both sides, that is $*_0, n, *_1$. For $a_{n-1} \in \{0, 1 \}$ if $a_{n-1} = 0$ then write $n - 1$ in the position of $*_0$. If $a_{n-1} = 1$ then write $n - 1$ in the position of $*_1$. For $a_{k}$ we will have already positioned the first $k - 1$ numbers in $A$. Denote these numbers by $\wedge$ and write $k+1$ placeholders between each number, that is $*_0, \wedge_1, *_1, \wedge_2, ..., *_{k-1}, \wedge_{k-1}, *_{k}$. For $a_{k} \in \{0, 1, 2, ..., n-k \}$ if $a_k = 0$ then place $k$ in the position of $*_0$; if $a_k = 1$ then place $k$ in the position of $*_1$; …; if $a_k = n-k$ then place $k$ is the position of $*_k$.

Consider the inversion sequence $(a_i)_{i=1}^{6} = ( 5, 3, 2, 1, 1, 0 )$ from earlier. We start by writing $n = 6$ down and placing two placeholders $*_0$ and $*_1$ on both sides of $6$:

(1)

\begin{align} \quad *_0, 6, *_1 \end{align}

Now $a_{n-1} = a_{6-1} = a_5 = 1$, so we place the number $n - 1 = 5$ in the position of $*_1$:

(2)

\begin{align} \quad 6, 5 \end{align}

We now write three placeholders $*_0$, $*_1$, and $*_2$ in between each number from above to get:

(3)

\begin{align} \quad *_0, 6, *_1, 5, *_2 \end{align}

Now $a_{n-2} = a_{6-2} = a_4 = 1$ so we place the number $n - 2 = 4$ in the position of $*_1$:

(4)

\begin{align} \quad 6, 4, 5 \end{align}

We now write four placeholders $*_0$, $*_1$, $*_2$ and $*_3$ in between each number from above to get:

(5)

\begin{align} \quad *_0, 6, *_1, 4, *_2, 5, *_3 \end{align}

Now $a_{n-3} = a_{6-3} = a_3 = 2$ so we place the number $n - 3 = 3$ in the position of $*_2$:

(6)

\begin{align} \quad 6, 4, 3, 5 \end{align}

We now write five placeholders $*_0$, $*_1$, $*_2$, $*_3$, and $*_4$ in between each number from above to get:

(7)

\begin{align} \quad *_0, 6, *_1, 4, *_2, 3, *_3, 5, *_4 \end{align}

Now $a_{n-4} = a_{6-4} = a_2 = 3$ so we place the number $n - 4 = 2$ in the position of $*_3$:

(8)

\begin{align} \quad 6, 4, 3, 2, 5 \end{align}

Lastly we write six placeholders $*_0$, $*_1$, $*_2$, $*_3$, $*_4$, and $*_5$ in between each number from above to get:

(9)

\begin{align} \quad *_0, 6,*_1, 4, *_2, 3, *_3, 2, *_4, 5, *_5 \end{align}

Now $a_{n-5} = a_{6-5} = a_1 = 5$ so we place the number $n - 5 = 1$ in the position of $*_5$:

(10)

\begin{align} \quad 6, 4, 3, 2, 5, 1 \end{align}

We have thus obtained the $6$-permutation $(6, 4, 3, 2, 5, 1)$ of elements from $A = \{1, 2, 3, 4, 5, 6 \}$ that has the corresponding $(a_i)_{i=1}^{6} = (5, 3, 2, 1, 1, 0)$.