19. The Ballot Problem. In an election, candidate A receives n votes and candidate B receives m votes, where n > m. Assuming that all of the (n + m)!/n! m!

orderings of the votes are equally likely, let P, denote the probability that A is always ahead in the counting of the votes.

(a) Compute P_2,1, P_3,1, P_3,2, P_4,1, P_4,2, P_4,3

(b) Find P_n,1, P_n,2.

(c) Based on your results in parts

(a) and (b), conjecture the value of P_n,m

(d) Derive a recursion for P_n,m in terms of P_n-1,m and P_n-1,m-1 by condition-

ing on who receives the last vote.

(e) Use part

(d) to verify your conjecture in part

(c) by an induction proof on n + m.