In a solitary record line of n individuals with particular statures, characterize a blocker to be somebody who is either taller than the individual standing promptly behind them, or the last individual in the line. For instance, assume that Ashanti has stature a, Blaine has tallness b, Charlie has tallness c, Dakota has tallness d, and Elia has statured, and that a < b < c < d < e. In the event that these five individuals arranged in the request Ashanti, Elia, Charlie, Blaine, Dakota (from front to back), at that point there would be three blockers: Elia, Charlie, and Dakota.

For numbers n ≥ 1 and k ≥ 0 let Q (n, k) be the number of ways that n individuals can line up with the end goal that there are actually k blockers.

(a) Show that for n ≥ 2 and k ≥ 1,

Q(n, k) = k * Q(n – 1, k) + (n – k + 1) * Q(n – 1, k – 1).

(b) Show that

Q(3, 2) = 2 * Q (2, 2) + 2 * Q(2, 1).

You can assume that Q(1,1) = 1, and that Q(n,0) = 0 for all n.

shivdaya Nov 25, 2020