+0  
 
+1
993
2
avatar+133 

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. 

 Jul 31, 2020
 #1
avatar+1253 
+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

 Jul 31, 2020
 #2
avatar+133 
+1

I found that website but I didn't really understand their answer so I came here :)

SpicyP  Jul 31, 2020

3 Online Users

avatar
avatar