
212 Combinatorics of Permutations, Second Edition
to a P -recursive function of n by our induction hypothesis as q
is
shorter than q.
Example 5.28
If q =341652,then q
=23541;thus we lose three subsequences
of type 132 when deleting 1. Therefore, we can apply our inductive
hypothesis for r − 3, then reinsert the entry 1 to its place. If q =
3124, then we do not lose any 132-patterns when deleting the entry
1 and getting q
= 2 1 3. Thus we still need to count permutations
with r 132-patterns, but they must end with q
,notwithq.The
pattern q
is shorter than q, thus the induction hypothesis on k can
be applied.
• If q has at most r inversions, but q is no