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<b<c<d<e.$ 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 $n ge 1$ and $k ge 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 ge 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.$)
I think if I somehow prove part b it proves part a so I’m focusing on part b but I don’t know what to do.