+0  
 
0
89
2
avatar

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
 #1
avatar
-1

This is trivial if you use recursion.

 Apr 26, 2022
 #2
avatar
0

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

31 Online Users

avatar
avatar
avatar
avatar