Combinatorics of Permutations, 2nd Edition

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