
240 Combinatorics of Permutations, Second Edition
n
q
q
q
FIGURE 6.5
Random choices leading to the placement of n.
The entry n is placed as follows. First, a box in F denoted by q is chosen
at random. (Here, and throughout this proof, all eligible boxes have the same
chance to be chosen.) Then, q is moved to any of the other h
q
−1 positions of
the original hook H
q
.Callthisnewboxq now. Then repeat the same for the
new q, that is, move it to a different position within the new H
q
,andcallthat
box q. Continue this until q becomes an inner corner,thatis,aboxwhose
hook consists of one box only, namely q itself. When that happens, place the
entry n into q.
Example ...