主题
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 函数

使用 Wolfram|Alpha 探索

参考文献

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年。

在 Wolfram|Alpha 上引用

选票问题

引用为

韦斯坦因,埃里克·W. “选票问题。” 来自 MathWorld—— Wolfram Web 资源。 https://mathworld.net.cn/BallotProblem.html

主题分类