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:
“When the apple is ripe it will fall.”
—Irish proverb.
An English equivalent to this might be, “To everything there is a season.”
“The proper method of philosophy consists in clearly conceiving the insoluble problems in all their insolubility and then in simply contemplating them, fixedly and tirelessly, year after year, without any hope, patiently waiting.”
—Simone Weil (1909–1943)