
172 Combinatorics of Permutations, Second Edition.
that all their ancestors have a positive label. If that happens, we resort to the
following proposition to locate the vertex associated with n.
PROPOSITION 4.51
Suppose p
n
= n.Thenn is the leftmost entry of p that has the property that
each of its ancestors (including itself ) has a positive label.
PROOF Suppose p
k
and n both have this property and that p
k
is on
the left of n. (If there are several candidates for the role of p
k
, choose the
rightmost one). If p
k
beats an element y on the right of n by participating in
the 132-pattern xp
k
y,thenxp
k
ny is a 1342-pattern, which is a contradiction.
So p
k
does