Permutation Patterns, Statistics on Permutations and Sorting by Shuffling

Patterns in permutations have been extensively studied in the past, as a topic within the area of enumerative combinatorics, and they have turned out to be useful when answering various questions in computer science, statistics, computational biology and other fields. Suppose that we have two permutations $\sigma = \sigma_{1}\cdots \sigma_{k}\in S_{k}$ and $\pi = \pi_{1}\cdots \pi_{n}\in S_{n}$, where $k\leq n$ and $S_m$ denotes the set of permutations of size $m$. We say that $\pi$ contains the classical pattern $\sigma$, if there exist indices $1\leq i_{1}<\cdots