# Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this

If i number of people voted for A and j number of people voted for B then dp[i][j] counts the number of ways voting can happen.

dp[ i ] [ j ] = dp[ i ] [ j - 1 ] + dp[ i - 1 ] [ j ] .

basically, I want to find the number of ways candidate A is in the winning position throughout. Can anyone explain the logic behind the dp equation ? I think it works like this. We have a sequence of A and B.In which A wins throughout. Now we add one more A to that sequence or add one more B to it.

• Your question is missing something very basic: what does dp[i][j] count? – Yuval Filmus Feb 23 '19 at 18:39
• If i number of people voted for A and j number of people voted for B then dp[i][j] counts the number of ways voting can happen. – Manoharsinh Rana Feb 23 '19 at 19:04
• You should update your post with this information. – Yuval Filmus Feb 23 '19 at 19:05

Let $$N(p,q)$$ be the number of sequences containing $$p$$ many A's and $$q$$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $$N(p,q) = 0$$ if $$q \geq p$$ and $$q > 0$$. When $$p = q = 0$$ there are no non-empty prefixes, and so $$N(p,q) = 1$$.
Suppose therefore that $$p > q$$, and consider any sequence satisfying the condition. If we remove the last element, we still get a sequence satisfying the condition. Conversely, whatever element we add, the resulting sequence will satisfy the condition, since $$p > q$$. We conclude that $$N(p,q) = \begin{cases} 1 & \text{ if } p=q=0, \\ 0 & \text{ if } q \geq p \text{ and } q > 0, \\ N(p-1,q) + N(p,q-1) & \text{ if } p > q > 0, \\ N(p-1,q) & \text{ if } p > q = 0. \end{cases}$$