Bertrand投票定理在C / C ++中的应用

在Bertrand的原始论文中,他解释了一种证明,该证明依赖于一般公式来实现实现递归关系的有利序列的数量。

示例

假设有5名选民,其中3名候选人A投票,2名候选人B 2投票(所以p = 3和q = 2)。投票顺序有十种可能-

  • AAABB

  • 阿巴巴

  • 阿巴

  • 银行

  • 阿巴

  • 阿巴巴

  • 巴巴

  • 阿巴

  • 巴巴

  • BBAAA

对于命令AABAB,随着选举的进行,投票结果汇总如下:

候选人一种一种一种
一种12233
00112

对于每列,A的计数始终大于B的计数,因此A始终严格领先于B。对于AABBA而言,随着选举的进行,投票的计数如下:

候选人一种一种一种
一种12223
00122

关于此命令,B在第四次投票后与A并列,因此A并不总是严格地领先于B。在10个可能的命令中,仅在AAABB和AABAB的情况下,A总是在B之前。因此,A始终严格领先的概率为2/10 = 1/5,这确实等于定理所预测的3-2 / 3 + 2。