# probability – Queues and blockers

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