关于n人对k个候选人投票时出现Condorcet悖论的方式数通用公式的问询

嘿，这个问题挺有深度的！先从你提到的已知情况说起，再聊聊k个候选人的通用公式现状：

首先，你说的OEIS序列A277935确实对应2n-1人投票给3个候选人时出现Condorcet悖论的方式数——这个特定场景下的计数已经被明确记录下来。但当扩展到k个候选人（k≥3）和任意n个投票者的一般情况时，事情就复杂多了：

• 先明确下Condorcet悖论的核心：当投票结果里不存在一个能在两两对决中击败所有其他候选人的“Condorcet胜者”时，悖论就出现了，最典型的就是三人候选时的循环偏好（比如A>B，B>C，C>A）。
• 对于k=3的情况，除了A277935针对奇数投票者的场景，其实也有适用于任意n个投票者的计数公式，但这类公式往往是基于排列组合的拆分，需要考虑所有可能的偏好分布和循环形成条件。
• 当k≥4时，目前没有简洁的闭合形式通用公式。原因很直观：候选人数增加后，可能出现的循环偏好结构呈指数级增长，既要考虑全循环，还要考虑部分子循环的组合，再结合投票者对这些偏好的选择，使得精确计数的复杂度飙升。
• 不过，学界也不是没有进展：
  • 可以利用对称群的性质，推导递归公式或者生成函数来计算这类数目，不过这类方法的计算成本会随着k和n的增大快速上升；
  • 另外，有不少研究给出了随机投票场景下出现Condorcet悖论的渐近概率，但这和精确的计数公式是两回事——概率是计数除以总投票方式数，但我们要的是计数本身。
• 补充一点：如果限定是奇数个投票者（避免两两对决出现平手的情况），情况会稍微清晰一些，但即使如此，当k≥4时，仍然没有简单的通用闭合公式，大多是针对特定k值的结果或者渐近表达式。

备注：内容来源于stack exchange，提问作者Poisson