1
$\begingroup$

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.

  1. Show that $$Q(3,2)= 2 \cdot Q(2,2)+ 2 \cdot Q(2,1).$$

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

$\endgroup$
2
  • $\begingroup$ For part $1,$ do I just bash $Q(3, 2)$ and other values of $Q,$ e.g. $Q(2, 2)$ and $Q(2, 1)?$ This wouldn't then be a rigorous proof, though. $\endgroup$ – Bongocat Apr 28 '20 at 3:51
  • $\begingroup$ Please help :). Thank you in advance. $\endgroup$ – Bongocat Apr 28 '20 at 4:15
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ For part a, do we just bash the values and equalize them? $\endgroup$ – Bongocat Apr 28 '20 at 16:27
  • $\begingroup$ Yes, I think that is the best way. $\endgroup$ – Mike Earnest Apr 28 '20 at 16:27
  • $\begingroup$ Thank you so much for your help. :) $\endgroup$ – Bongocat Apr 28 '20 at 16:28
  • $\begingroup$ So, you helped me do two cases, and I have to do the ones where $n$ is in the front and back. I'm not sure what will happen when $n$ is in the front. If we remove it either way, I don't think it changes how many blockers are in the queue in any way. $\endgroup$ – Bongocat Apr 28 '20 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.