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. For example, suppose that Ashanti has height a Blaine has height b Charlie has height c Dakota has height d and Elia has height e and that 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 and 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 \cdot Q(2,2)+ 2 \cdot Q(2,1).\] \)

(b) Show that for \(n \ge 2\) and \(k \ge 1\) \(\[Q(n,k)=k \cdot Q(n-1,k)+(n-k+1) \cdot Q(n-1,k-1).\] \)

Guest Jul 21, 2021