+0  
 
0
71
1
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  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).\] \)
 

 Jul 21, 2021
 #1
avatar
0

This is very easy when you use recursion.

 Sep 4, 2021

58 Online Users

avatar