
152 Combinatorics of Permutations, Second Edition.
Note that the conjectured number c
n
q
is very small compared to the number
of all n-permutations, which is n!. In other words, this is a quite ambitious
conjecture.
The following conjecture may look even more ambitious, but that is a false
appearance.
CONJECTURE 4.9 [Stanley–Wilf conjecture, alternative version] Let
q be any pattern. Then the limit
L(q) = lim
n→∞
n
'
S
n
(q)
exists.
The first published proof of the fact that the above two versions of the
conjecture are equivalent is given in [12]. On one hand, it is obvious that
Conjecture 4.9 implies Conjecture 4.8. On the other hand, to prove the im-
plication ...