Patterns in Permutations and Words

Chapter 1. What is a pattern？

Roughly speaking, for our purposes, patterns in permutations are permutations with additional restrictions, and patterns in words are certain restricted Words (possibly permutations).

Reduced form of a permutation：把一个$r$ permutation里的元素重新命名，使得他们成为一个$\{1,\cdots r\}$排列，大小顺序不变。例如： $$Red(3174)=2143$$ Reverse of a permutation：$\sigma=\sigma_1\sigma_2\cdots\sigma_n$的reverse $r(\sigma)=\sigma_n\sigma_{n-1}\cdots\sigma_1$。
Complement of a permutation：用$\{1,\cdots r\}$里面最小的替换$\sigma=\sigma_1\sigma_2\cdots\sigma_n$里最大的，第二小的替换第二大的，以此类推，记为$c(\sigma)$。
Inverse of a permutation：The $\sigma_i$-th position of the inverse $i(\sigma)$ is occupied by $i$。

这三个变换称为$S_n$的trivial bijections。

Permutation matrix：Permutation可以描述为第$i$个位置是几($\sigma_i$)，用矩阵表示，列用值index，行用位置index。

Ascent是Permutation里的一个字母，后面接比它大的字母；Descent后面接比它小的字母的。n-permutation里面Ascent的个数加Descent的个数是$n-1$；如果一个Permutation以Ascent开始，然后Descent，然后Ascent，以此类推，这个Permutation称为Alternating Permutation。

Interval of a Permutation是里面的一个factor，而且他们的值是相邻的(不要求按值的大小排列)，例如423 is an interval in 1642375。如果一个Permutation里全部proper initial factor都不是Interval。