+0

0
241
2

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.)

______________

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!

Apr 26, 2022

#1
-1

This is trivial if you use recursion.

Apr 26, 2022
#2
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