A permutation p is said to contain a permutation sigma =s1s2s3…sk if there is a subsequence tau of p such that the relative ordering of the letters in tau is the same as the relative ordering of the letters in p. Note that a subsequence does not necessarily mean a subsequence of consecutive letters.

If a permutation does not contain sigma, it is said to avoid sigma.

Let S_n(q) denote the number of n-permtuations that avoid a pattern q. Then S_n(123) is given by the nth Catalan number. Surprisingly, S_n(123)=S_n(132) = S_n(213) = S_n(231) = S_n(321) = S_n(312) = C_n, where C_n is the nth Catalan number.
In other words, we can say that

Let q be any pattern of length 3. Then S_n(q) = C_n = (2n choose n)/(n+1).

It turns out that S_n(123…n) = (k-1)^(2n)

(Stanley Wilf Conjecture: Let q be any pattern. Then there exists a constant c_q such that

S_n(q) < c_q^n

for any n.
Stanley Wilf Conjecture, alternative form: Let q be any pattern, then the limit

S_n(q)^(1/n)

exists.