C/C++의 Bertrandís ballot theorem에 대한 응용

<시간/>

Bertrand의 원본 논문에서 그는 재귀 관계를 구현하는 유리한 시퀀스의 수에 대한 일반 공식에 의존하는 증명을 설명합니다.

예시

5명의 유권자가 있고 그 중 3명은 후보자 A에, 2명은 후보자 B에 대해 투표합니다(따라서 p =3 및 q =2). 투표 순서에 대해 10가지 가능성이 있습니다. −

꺄악
AABAB
아바브
꺄악
아바
아바바
바바
아바
바바
꺄악

AABAB 순서의 경우, 선거가 진행됨에 따른 투표 집계는 다음과 같습니다. -

후보자	아	아	나	아	나
A	1	2	2	3	3
나	0	0	1	1	2

각 열에 대해 A에 대한 집계는 항상 B에 대한 집계보다 크므로 A는 항상 B보다 엄격하게 앞서 있습니다. AABBA 순서의 경우 선거가 진행됨에 따라 투표 집계는 다음과 같습니다. -

후보자	아	아	나	나	아
A	1	2	2	2	3
나	0	0	1	2	2

이 순서와 관련하여 B는 네 번째 투표 후에 A와 동점이므로 A가 항상 B보다 엄격하게 앞서는 것은 아닙니다. 가능한 10가지 주문 중 A는 AAABB 및 AABAB의 경우에만 항상 B보다 앞서 있습니다. 따라서 A가 항상 엄격하게 앞서 있을 확률은 2/10=1/5이고 이는 정리가 예측하는 대로 실제로 3-2 / 3+2와 같습니다.