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 a \(n \ge 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 \cdot Q(2,2)+ 2 \cdot Q(2,1).\)

(b) Show that for n ≥ 2 and \($k \ge 1,$ Q(n,k)=k \cdot Q(n-1,k)+(n-k+1) \cdot Q(n-1,k-1).\)(You can assume that Q(1,1)=1, and that Q(n,0)=0 for all n.)

Explain your answer thoroughly.

______________

Help would be appreciated; this site doesn't have any complete answers, and I'm not sure how to proceed. Perhaps for part (a) we could bash the numbers; any ideas?

Thank you in advance to those helping!

Guest Apr 26, 2022