+5 In a single-file queue of n people with distinct heights, define a blocker to be someone who is either taller than the person standing immediately behind them, or the last person in the queue. omegle xender For example, suppose that Ashanti has height a, Blaine has height b, Charlie has height c, Dakota has height d, and Elia has height d, and that a < b < c < d < e. If these five people lined up in the order Ashanti, Elia, Charlie, Blaine, Dakota (from front to back), then there would be three blockers: Elia, Charlie, and Dakota.
For integers n ≥ 1 and k ≥ 0 let Q (n, k) be the number of ways that n people can queue up such that there are exactly k blockers.
(a) Show that
Q(3, 2) = 2 * Q (2, 2) + 2 * Q(2, 1).
(b) Show that for n ≥ 2 and k ≥ 1,
Q(n, k) = k * Q(n – 1, k) + (n – k + 1) * Q(n – 1, k – 1).
You can assume that Q(1,1) = 1, and that Q(n,0) = 0 for all n.
