Equivalent Problems
Rather than computing the probability that a random vote counting order has the desired property, one can instead compute the number of favourable counting orders, then divide by the total number of ways in which the votes could have been counted. (This is the method used by Bertrand.) The total number of ways is the binomial coefficient ; Bertrand's proof shows that the number of favourable orders in which to count the votes is (though he does not give this number explicitly). And indeed after division this gives .
Another equivalent problem is to calculate the number of random walks on the integers that consist of n steps of unit length, beginning at the origin and ending at the point m, that never become negative. Assuming n and m have the same parity and n ≥ m ≥ 0, this number is
When m = 0 and n is even, this gives the Catalan number .
Read more about this topic: Bertrand's Ballot Theorem
Famous quotes containing the words equivalent and/or problems:
“Distinctions drawn by the mind are not necessarily equivalent to distinctions in reality.”
—Thomas Aquinas (c. 1225–1274)
“More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
—Anna Quindlen (b. 1952)