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! smiley

 Apr 26, 2022

This is trivial if you use recursion.

 Apr 26, 2022

Hi, thanks for your response; however, this isn't supposed to be done using recursion. Would you care to show your method/explain it further?

Guest Apr 26, 2022

13 Online Users