(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)