Consider the permutations of 1, 2, 3, 4. The permutation 1432, for instance, is said to have one ascent - namely, 14 (since 1 < 4). This same permutation also has two descents - namely, 43 (since 4 > 3) and 32 (since 3 > 2). The permutation 1423, on the other hand, has two ascents, at 14 and 23 - and the one descent 42.
(a) How many permutations of 1, 2, 3 have k ascents, for k = 0, 1, 2?
(b) How many permutations of 1, 2, 3, 4 have k ascents, for k = 0, 1, 2, 3?
(c) If a permutation of 1, 2, 3, 4, 5, 6, 7 has four ascents, how many descents does it have?
(d) Suppose a permutation of 1, 2, 3, . . ., m has k ascents, for 0 < k < m - 1. How many descents does the permutation have?
(e) Consider the permutation p = 12436587. This permutation of 1, 2, 3, . . . , 8 has four ascents. In how many of the nine locations (at the start, end, or between two numbers) in p can we place 9 so that the result is a permutation of 1, 2, 3, . . ., 8, 9 with (i) four ascents; (ii) five ascents?
(f) Let πm.k jk denote the number of permutations of 1, 2, 3,. . . , m with k ascents. Note how π4,2 = 11 = 2(4) + 3(1) = (4 - 2)π3,1 + (2 + 1)π3,2. How is πm,k related to πm-1,k-1 and πm-1,k]?