
280 Combinatorics of Permutations, Second Edition
anywhere before position j +1.
On the other hand, x cannot enter the first row anywhere after position j+1
either. Indeed, assume this happens; this implies that when x starts looking
for a position, there is an entry y<xin position j +1ofthe firstrow. By
our induction hypothesis, that entry cannot have rank less than j +1. That
is a contradiction, however, for we could affix x to the end of any increasing
subsequence ending in y, yielding that the rank of x is at least j +2.
The result of Lemma 7.3 provides an obvious alternative proof of the fact
that S
n
(123 ···k) ≤ (k − 1)
2n
. There is, however, a muc