IMO 1984 SL 17

Origin: FRG

Problem

In a permutation (x1, x2, . . . , xn) of the set 1, 2, . . . , n we call a pair (xi, xj) discordant if i < j and xi > xj. Let d(n, k) be the number of such permutations with exactly k discordant pairs. Find d(n, 2) and d(n, 3).

Solution

For any m = 0, 1, . . ., n −1, we shall find the number of permutations (x1, x2, . . . , xn) with exactly k discordant pairs such that xn = n −m. This xn is a member of exactly m discordant pairs, and hence the permu- tation (x1, . . . , xn−1 of the set {1, 2, . . ., n}{m} must have exactly k −m discordant pairs: there are d(n −1, k −m) such permutations. Therefore d(n, k) = d(n −1, k) + d(n −1, k −1) \cdot \cdot \cdot + d(n −1, k −n + 1) = d(n −1, k) + d(n, k −1) (note that d(n, k) is 0 if k < 0 or k >
n  ). We now proceed to calculate d(n, 2) and d(n, 3). Trivially, d(n, 0) = 1. It follows that d(n, 1) = d(n −1, 1) + d(n, 0) = d(n −1, 1) + 1, which yields d(n, 1) = d(1, 1) + n −1 = n −1.

Further, d(n, 2) = d(n −1, 2) + d(n, 1) = d(n −1, 2) + n −1 = d(2, 2) + 2 + 3 + \cdot \cdot \cdot + n −1 = (n2 −n −2)/2. Finally, using the known formula 12 + 22 + \cdot \cdot \cdot + k2 = k(k + 1)(2k + 1)/6, we have d(n, 3) = d(n −1, 3) + d(n, 2) = d(n −1, 3) + (n2 −n −2)/2 = d(2, 3) + n i=3(n2 −n −2)/2 = (n3 −7n + 6)/6.