+4 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 d, 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 ≥ 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.
(a) Show that
Q(3, 2) = 2 * Q (2, 2) + 2 * Q(2, 1).
(b) Show that for n ≥ 2 and k ≥ 1,
Q(n, k) = k * Q(n – 1, k) + (n – k + 1) * Q(n – 1, k – 1).
You can assume that Q(1,1) = 1, and that Q(n,0) = 0 for all n.
+624 (a) There are two ways to create a queue with 3 people and 2 blockers:
The first person is a blocker, and the other two people are in any order.
The second person is a blocker, and the other two people are in any order.
The first case can be achieved in Q(2,2) ways, and the second case can be achieved in Q(2,1) ways. Therefore, the total number of ways to create a queue with 3 people and 2 blockers is 2∗Q(2,2)+2∗Q(2,1).
(b) To create a queue with n people and k blockers, we can either:
Have the first person be a blocker, and the other n−1 people be in any order. This case can be achieved in k∗Q(n−1,k) ways.
Have the second person be a blocker, and the other n−1 people be in any order. This case can be achieved in (k−1)∗Q(n−1,k) ways.
...
Have the $k$th person be a blocker, and the other n−1 people be in any order. This case can be achieved in 1∗Q(n−1,k) ways.
Have the $k + 1$st person be a blocker, and the other n−1 people be in any order. This case can be achieved in 0∗Q(n−1,k) ways.
Note that the last case is impossible, because there would be more blockers than people.
Therefore, the total number of ways to create a queue with n people and k blockers is:
k * Q(n - 1, k) + (k - 1) * Q(n - 1, k) + ... + 1 * Q(n - 1, k)
This can be simplified to:
(k * Q(n - 1, k)) + ((k - 1) * Q(n - 1, k)) + ... + (Q(n - 1, k) + Q(n - 1, k - 1) + ... + Q(n - 1, 0))
The last term in this sum is equal to Q(n−1,k−1), because it is the number of ways to create a queue with n−1 people and k−1 blockers. Therefore, the total number of ways to create a queue with n people and k blockers is:
(k * Q(n - 1, k)) + ((k - 1) * Q(n - 1, k)) + ... + (Q(n - 1, k - 1))
This can be rewritten as:
k * Q(n - 1, k) + (n - k + 1) * Q(n - 1, k - 1)
Therefore, we have shown that for n≥2 and k≥1,
Q(n, k) = k * Q(n - 1, k) + (n - k + 1) * Q(n - 1, k - 1)
