Generating Permutations with Inversion Sequences

Table of Contents

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 will now look at one of two common and easy methods for generating $$n$$ -permutations from a finite $$n$$ -term inversion sequence.

The following theorem shows us that each of these inversion sequences correspond to a unique $$n$$ -permutation.

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)

. Set up an empty

$n$

-permutation

$(*, *, ..., *)$

where each

$*$

represents a remaining position in the

$n$

-permutation. The number

$1$

in to be placed in the

(a_1 + 1)^{\mathrm{th}}

remaining position. The number

$2$

in to be placed in the

(a_2 + 1)^{\mathrm{th}}

remaining position. The number

$k$

in to be placed in the

(a_k + 1)^{\mathrm{th}}

remaining position. We continue this process and the number

$n$

is to be placed in the last remaining position.

For example, consider the inversion sequence $(a_i)_{i=1}^{n} = (5, 3, 2, 1, 1, 0)$ .

$$a_1 = 5$$ and so we place $$1$$ in the $a_1 + 1 = 5+1 = 6^{\mathrm{th}}$ remaining position to get $$( *, *, *, *, *, 1)$$ .

$$a_2 = 3$$ and so we place $$2$$ in the $a_2 + 1 = 3+1 = 4^{\mathrm{th}}$ remaining position to get $$(*, *, *, 2, *, 1)$$ .

$$a_3 = 2$$ and so we place $$3$$ in the $a_3 + 1 = 2 + 1 = 3^{\mathrm{rd}}$ remaining position to get $$(*, *, 3, 2, *, 1)$$ .

$$a_4 = 1$$ and so we place $$4$$ in the $a_4 + 1 = 1 + 1 = 2^{\mathrm{nd}}$ remaining position to get $$(*, 4, 3, 2, *, 1)$$

$$a_5 = 1$$ and so we place $$5$$ in the $a_5 + 1 = 1 + 1 = 2^{\mathrm{nd}}$ remaining position to get $$(*, 4, 3, 2, 5, 1)$$

We place $$6$$ in the remaining position to get the $$6$$ -permutation $$(6, 4, 3, 2, 5, 1)$$ corresponding to the given inversion sequence.

The other common method for generating permutations with inversion sequences can be found when we look at An Alternative Method for Generating Permutations with Inversion Sequences.

Mathonline

Learn Mathematics

Generating Permutations with Inversion Sequences