Combinatorics of Permutations, 2nd Edition

Do Not Look Just Yet. Solutions to Odd-Numbered Exercises. 425

9. Theorem 7.5, with its notations, shows that necessarily a

1

= k and

a

1

+ a

2

+ ···+ a

r

= r · k. Thus necessarily a

1

= a

2

= ··· = a

r

= k

and a

r+1

<k, otherwise there would be r + 1 increasing subsequences of

length k that are disjoint. This means that the size of the last column

is m

k

= r. Applying (7.1) with k variables instead of k − 1 and fixing

m

k

= r we get the proof exactly as we got the proof of Theorem 7.4.

11. In any SYT of shape F ,theentryn has to be in one of the inner corners.

So removing n from any such tableaux, we get an SYT of shape F



for

some F



that is part of the summation.

13. N