
Do Not Look Just Yet. Solutions to Odd-Numbered Exercises. 415
Solutions for Chapter 5
1. We claim that S
132,1
(n)=
2n−3
n−3
. See [42] for a proof. The main idea is
the following. In a permutation enumerated by S
132,1
(n), there is either
one or no front entry that is smaller than a back entry. If there is one
such front entry, then its position and size is very restricted. If there is
no such front entry, then the single 132-pattern of the permutation is
formed either by front entries only, or by back entries only. This leads
to a recursive formula involving the numbers S
132,1
(n) and the Cata-
lan numbers, and solving that recursion, we obtain the a