
100 Combinatorics of Permutations, Second Edition
had to expand p
j+a
(resp. q
j+a
)intop
j+a+1
(resp. q
j+a+1
). At the end
of the procedure, we define Φ(p, q)=(q
n
,p
n
).
Example 3.23
Let n =6andk = 2, and let p = (125463), and q = (13)(24)(56). It is then
clear that j =4,andp
4
= (1243) and q
4
= (13)(24). After swapping, we
get the pair
(q
4
,p
4
) = ((13)(24), (1243)).
To make further computations easier, we note that p
5
= (12543) and
q
5
= (13)(24)(5).
The entry 5 would have to be inserted into the second gap position of p
4
to get p
5
, and into the fifth gap position of q
4
to get q
5
.Soweinsert5
into the second gap position of q
4
and in