Permutations Avoiding Pattern

Presented by Ondřej Bílka DIMACS REU 2009

Permutations

Permutation: a mapping {1, 2, …, n} onto {1, 2, …, n}. We call the set of permutations of order n as S_{n}. We can visualize permutations in this way:

We call permutation τ involution if τ = τ^{−1} We call set of involutions of order n as I_{n}.

Permutations

Permutation: a mapping {1, 2, …, n} onto {1, 2, …, n}. We call the set of permutations of order n as S_{n}. We can visualize permutations in this way:

We call permutation τ involution if τ = τ^{−1} We call set of involutions of order n as I_{n}.

Included pattern

Permutation σ contains pattern τ if we can by removing rows and collumns obtain permutation τ. The pattern

Wilf’s equivalence

is contained in the following permutation S_{n}(τ) = {σ|σ ∈ S_{n}, σ does not contain τ}. I_{n}(τ) = {σ|σ ∈ I_{n}, σ does not contain τ}. We call permutations σ, τ Wilf-equivalent for permutations if ∀n |S_{n}(σ)| = |S_{n}(τ)| denoted by σ ∼_{S} τ, involutions if ∀n |I_{n}(σ)| = |I_{n}(τ)| denoted by σ ∼_{I} τ. Observation: σ ∼_{S} σ^{−1} S_{n}(τ) = {σ|σ ∈ S_{n}, σ does not contain τ}. I_{n}(τ) = {σ|σ ∈ I_{n}, σ does not contain τ}. We call permutations σ, τ Wilf-equivalent for permutations if ∀n |S_{n}(σ)| = |S_{n}(τ)| denoted by σ ∼_{S} τ, involutions if ∀n |I_{n}(σ)| = |I_{n}(τ)| denoted by σ ∼_{I} τ. Observation: σ ∼_{S} σ^{−1} S_{n}(τ) = {σ|σ ∈ S_{n}, σ does not contain τ}. I_{n}(τ) = {σ|σ ∈ I_{n}, σ does not contain τ}. We call permutations σ, τ Wilf-equivalent for permutations if ∀n |S_{n}(σ)| = |S_{n}(τ)| denoted by σ ∼_{S} τ, involutions if ∀n |I_{n}(σ)| = |I_{n}(τ)| denoted by σ ∼_{I} τ. Observation: σ ∼_{S} σ^{−1}

The problem

Our problem is: Does σ ∼_{I} τ for σ, τ ∈ I_{n} imply that σ ∼_{S} τ? Converse is not true. For example:

and

The problem

Our problem is: Does σ ∼_{I} τ for σ, τ ∈ I_{n} imply that σ ∼_{S} τ? Converse is not true. For example:

and