主題
Search

選票問題


假設 AB 是候選人,並且有 2n 位選民,n 投票給 An 投票給 B。 有多少種方式可以計數選票,使得 B 永遠不會領先於 A? 解是 卡塔蘭數 C_n

一個相關的問題,也稱為“選票問題”,是讓 A 收到 a 票,並且 B 收到 b 票,其中 a>=b。 這個版本的選票問題然後詢問機率,即 A 始終領先於 B 當選票被計數時 (Vardi 1991)。 解是 (a-b+1)/(a+1),正如 M. Bertrand (Hilton 和 Pedersen 1991) 首次證明的那樣。 André (1887) 使用所謂的 安德烈的反射法 提供了另一個優雅的解法。

這個問題也可以被推廣 (Hilton 和 Pedersen 1991)。 此外,TAK 函式 與選票問題有關 (Vardi 1991)。


另請參閱

安德烈的反射法, 卡塔蘭數, 階梯行走, TAK 函式

使用 探索

參考文獻

André, D. “M. Bertrand 解決的問題的直接解法。” Comptes Rendus Acad. Sci. Paris 105, 436-437, 1887年。Ball, W. W. R. 和 Coxeter, H. S. M. 數學娛樂與散文,第 13 版。 紐約:Dover,第 49 頁,1987年。Carlitz, L. “某些遞迴的解法。” SIAM J. Appl. Math. 17, 251-259, 1969年。Comtet, L. 高階組合學:有限和無限展開的藝術,修訂擴充套件版。 荷蘭多德雷赫特:Reidel,第 22 頁,1974年。Feller, W. 機率論及其應用導論,第 1 卷,第 3 版。 紐約:Wiley,第 67-97 頁,1968年。Hilton, P. 和 Pedersen, J. “選票問題和卡塔蘭數。” Nieuw Arch. Wisk. 8, 209-216, 1990年。Hilton, P. 和 Pedersen, J. “卡塔蘭數、它們的推廣及其用途。” Math. Intel. 13, 64-75, 1991年。Kraitchik, M. “投票箱問題。” 數學娛樂 §6.13。 紐約:W. W. Norton,第 132 頁,1942年。Motzkin, T. “超曲面交叉比率之間的關係,以及多邊形劃分、永久優勢和非結合積的組合公式。” Bull. Amer. Math. Soc. 54, 352-360, 1948年。Vardi, I. Mathematica 中的計算娛樂。 加利福尼亞州紅木城:Addison-Wesley,第 185-187 頁,1991年。

在 上引用

選票問題

引用為

韋斯坦因,埃裡克·W. “選票問題。” 來自 —— 資源。 https://mathworld.tw/BallotProblem.html

主題分類