+0  
 
+1
115
1
avatar+5 

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. omegle xender 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.

 Aug 1, 2020
edited by LennoxConner  Aug 5, 2020
 #1
avatar+111082 
+1

Have you answered part A yet.

 

What have you done yourself?

 Aug 1, 2020

27 Online Users

avatar