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.

SpicyP Jul 31, 2020

#1**+1 **

AoPS problem, eh?

Check here, has some hints, I used them for this problem: https://math.stackexchange.com/questions/3647594/single-file-queue-with-people-as-blockers

CoolStuffYT Jul 31, 2020