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.
-
Show that $$Q(3,2)= 2 \cdot Q(2,2)+ 2 \cdot Q(2,1).$$
-
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).$$
Assume that $Q(1,1)=1,$ and that $Q(n,0)=0$ for all $n.$
For the first part of the problem, can we just bash certain values as our proof? (e.g. $Q(3, 2)$)
Part $2$ so far: For every queue of $n-1$ people with $k$ blockers, there are $k$ corresponding queues with $n$ people and $k$ blockers. For every queue of $n-1$ people with $k-1$ blockers, there are $n-k+1$ corresponding queues with $n$ people and $k$ blockers; and that these queues together make up all queues with $n$ people and $k$ blockers.
Best Answer
For every sequence of $n$ people with $k$ blockers, consider what happens when you remove the tallest person from the line, while keeping everyone else in the same order. How many blockers will new lineup have? It turns out it depends on where the tallest person was removed from. Let $n$ be the tallest person, and suppose they are behind person $a$ and in front of person $b$: $$ \dots a\gets n \gets b \dots $$ There are two cases:
If $a$ is shorter than $b$, then removing $n$ reduces the number of blockers by $1$, since $n$ is a blocker.
If $a$ is taller than $b$, then removing $n$ does not change the number of blockers, since the blocker $n$ is removed, but $a$ becomes a blocker.
You also have to consider what happens when $n$ is at the beginning or end of the line.
With these observations in mind, here is a big hint towards a proof. Every lineup of $n$ people can be obtained by inserting a person with height $n$ into a lineup of people with heights $1$ to $n-1$. In order to create a lineup of $n$ people with $k$ blockers, you have to either
start with a lineup of $n-1$ with $k-1$ blockers, and insert $n$ in a place which causes the number of blockers to increase, or
start with a lineup of $n-1$ with $k$ blockers, and insert $n$ in a place which causes the number of blockers to stay the same.
In each of these cases, count the number of places where you can insert $n$.