2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your question is missing something very basic: what does dp[i][j] count? $\endgroup$ – Yuval Filmus Feb 23 at 18:39
  • $\begingroup$ 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. $\endgroup$ – Manoharsinh Rana Feb 23 at 19:04
  • 2
    $\begingroup$ You should update your post with this information. $\endgroup$ – Yuval Filmus Feb 23 at 19:05
2
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.