Combinatorics of Permutations, 2nd Edition

300 Combinatorics of Permutations, Second Edition

1

1

22

3

2

1

1

1212

1111

3

2

F(p)

F

<1>

F

<2>

FIGURE 7.17

Decomposing F (p)into(F

1

,F

2

).

We are going to decompose F (p)intoak-tuple of northeastern lattice paths,

(F

1

,F

2

, ···,F

k

), each of which will consist of one vertical step and n − 1

horizontal steps. The unique vertical step of F

i

will be in the same position

as the ith vertical step of F (p). In other words, the unique vertical edge of

F

i

will be its (d

i

+ 1)st, corresponding to the ith descent of p. We still have

to specify the labels of the edges of F

i

.Lete

i,j

be the label of the jth edge

of F

i

.Wethenset

e

i,j

=

⎧

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎩

1ifj ≤ d

i

,

e

j

if d

i

+1≤ j ≤