
Permutations and the Rest. Algebraic Combinatorics of Permutations. 305
38. Let ρ(n) be the size of the largest set of n-permutations in which every
pair of elements is colliding. Prove that ρ(n) ≥ ρ(n − 1) + ρ(n − 2).
39. Prove that for all positive integers n,wehaveS
n
(231, 312) = I
n
(231, 312).
Problems Plus
1. Let D
k
(n)bethenumberofn-permutations in which the longest in-
creasing subsequences have k elements and they all have at least one
element in common. Prove that D
k
(n)isaP -recursive function of n.
2. We have seen in Theorem 7.11 that the Robinson–Schensted–Knuth
correspondence naturally defines a bijection between inversions of length
n and SYT ...