What is a permutation pattern?

Question

The wikipedia entry for permutation pattern gives this as an example:

For example, in the permutation π = 391867452, π₁=3 and π₉=2. A permutation π is said to contain the permutation σ if there exists a subsequence of (not necessarily consecutive) entries of π that has the same relative order as σ, and in this case σ is said to be a pattern of π, written σ ≤ π. Otherwise, π is said to avoid the permutation σ. For example, the permutation π = 391867452 contains the pattern σ = 51342, as can be seen in the highlighted subsequence of π = 391867452 (or π = 391867452 or π = 391867452). Each subsequence (91674, 91675, 91672) is called a copy, instance, or occurrence of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234.

In that example, is a pattern of 51342 the same as a pattern of, say, 62453 or 92483? I mean, is it the just the the increase/decrease as well as the relative magnitude of each digit with respect to every other digit in the sequence that makes a pattern? Or must a pattern be "reduced" so that the value of the lowest digit in the pattern is 1 and the difference between the two values in the "sort" of the pattern is no more than 1?

Answer 1

Typically a pattern of length $k$ is written as a permutation of $\{1,\dotsc,k\}$. This has at least two advantages. First, the pattern itself is a permutation of a simple set, making things simpler. Second, it gives each pattern a unique representation. Sure you could define patterns to include $413$ (in place of or in addition to $312$) but that does not seem to add anything to its utility.

Answer 2

Rather than thinking of a pattern as a single permutation, think of it as an equivalence class with respect to order isomorphism (i.e. if positions compare in the same way, then the entries in those positions compare in the same way, too). That equivalence class has a canonical representative where the $k$th smallest position/letter is $k$. In your example, $51342$, $62453$ and $92483$ are order-isomorphic, and the canonical representative of their equivalence class is $51342$.