Combinatorics of Permutations, 2nd Edition

348 Combinatorics of Permutations, Second Edition

9

8

7

5

3

2

4

1

6

9

8

6

7

4

5

3

1

2

TTT T

123

4

FIGURE 8.11

Finding a preimage for p = 213547689.

q and then reading it in postorder. Now let us assume that s(q)=p.

Thenanytimewepassinp from one ascending run to the next, in the

postorder reading of T

q

, we must jump from the left subtree of a vertex

to the right subtree of a vertex as that is the only way we can obtain a

descent. This observation justifies the following algorithm.

To obtain a permutation q so that s(q)=p, take the ascending run

decomposition r

1

,r

2

, ···,r

k

of p,andforeachi, take the decreasing

binary tree that is corresponding to the reverse of r

i

.Denotethe