+0

0
200
1

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