Week 5 Writing Exercise
Problem Statement
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 integers n ≥ 1 and k ≥ 0, let Q(n, k) be
the number of ways that n people can queue up such that there are exactly k
blockers.
Part (a): Show that Q(3, 2) = 2 · Q(2, 2) + 2 · Q(2, 1)
Consider the case where a < b < c.
2-Person Case
For 2 people, let’s consider a < b.
• Q(2, 2) = 1: The queue ba where both a and b are blockers.
• Q(2, 1) = 1: The queue ab where only b is a blocker.
3-Person Case
For 3 people, we have:
Q(3, 2) = 2 · Q(2, 2) + 2 · Q(2, 1) = 2 · 1 + 2 · 1 = 4
The possible queues with exactly 2 blockers are:
• bca
• bac
• cab
• acb
1
Explanation
• The Q(2, 2) case ba (where both a and b are blockers) can be transformed
into a 3-person queue with 2 blockers by placing the tallest person c behind
a blocker. This yields bca and bac.
• The Q(2, 1) case ab (where only b is a blocker) can be transformed into a
3-person queue with 2 blockers by placing the tallest person c in the first
position or behind a non-blocker. This yields cab and acb.
Part (b): General Case for n ≥ 2 and k ≥ 1
We need to show that:
Q(n, k) = k · Q(n − 1, k) + (n − k + 1) · Q(n − 1, k − 1)
Base Cases
• Q(1, 1) = 1: Only one person, who is a blocker.
• Q(n, 0) = 0 for all n: No blockers is impossible.
Recurrence Relation
WLOG, consider adding the n-th person X (the tallest person) to a queue of
n − 1 people. Adding a person to the queue can only be done in 2 ways:
• Inserting directly behind a blocker
• Inserting directly behind a nonblocker or in the first position.
Case 1: Inserting X Behind a Blocker
If X is inserted behind a blocker, the number of blockers does not change. The
person in front of X ceases to be a blocker (as he is not taller than X), and X
becomes a blocker since he is always taller than the one behind him. There are
k blockers to choose from, so the number of ways to form a group of n with k
blockers (from a group of n with k-1 blockers) is:
k · Q(n − 1, k)
Case 2: Inserting X Behind a Non-Blocker or in the First Position
If X is inserted behind a non-blocker or in the first position, X becomes a
blocker (he is the tallest) without affecting the status quo of the rest of the
queue. This is because if X has a nonblocker in front of him, this person will
remain a nonblocker after the insertion. The person behind him will not be
affected as blocker status does not depend on the individual that comes before.
2
This scenario adds exactly one blocker to the queue. There are n−k+1 positions
where X can be inserted to achieve this, so the number of ways is:
(n − k + 1) · Q(n − 1, k − 1)
Combining the Cases
Thus, the total number of ways to form a queue of n people with k blockers is:
Q(n, k) = k · Q(n − 1, k) + (n − k + 1) · Q(n − 1, k − 1)
