قضیه رای گیری برترند

قضیه رأی گیری برترند. فرض کنید در یک انتخابات کاندید A {\displaystyle A} ، a {\displaystyle a} رأی و کاندید B {\displaystyle B} ، b {\displaystyle b} رأی به دست می آورد؛ به طوری که a ≥ k b {\displaystyle a\geq kb} ( k {\displaystyle k} یک عدد صحیح مثبت است). تعداد (یا احتمال) حالاتی را به دست آورید که در تمام طول رأی گیری آرای A {\displaystyle A} ، دست کم k {\displaystyle k} تا بیشتر از آرای B {\displaystyle B} باشد.پاسخ a − k b a + b ( a + b a ) {\displaystyle {\frac {a-kb}{a+b}}{\binom {a+b}{a}}} است. (احتمال آن a − b a + b {\displaystyle {\frac {a-b}{a+b}}} می باشد)
A A A B B {\displaystyle AAABB}
A A B A B {\displaystyle AABAB}
A B A A B {\displaystyle ABAAB}
B A A A B {\displaystyle BAAAB}
A A B B A {\displaystyle AABBA}
A B A B A {\displaystyle ABABA}
B A A B A {\displaystyle BAABA}
A B B A A {\displaystyle ABBAA}
B A B A A {\displaystyle BABAA}
B B A A A {\displaystyle BBAAA}
در سال ۱۸۸۷ جوزف برترند که مسئلهٔ رأی گیری را بیان کرده بود برای حالت خاص k = 1 {\displaystyle k=1}   راه حلی از طریق روابط بازگشتی ارائه داد و خواستار راه حل مستقیمی برای آن شد. بلافاصله بعد از آن که برترند پرسش خود را مطرح کرد E ́mile Barbier راه حلی برای هر k {\displaystyle k}   اختیاری مطرح کرد اما هیچ اثباتی برای آن نداشت. اندکی بعد Désiré André اثبات ترکیبیاتی کوتاهی برای حالت k = 1 {\displaystyle k=1}   مسئلهٔ برترند داد. در سال ۱۹۲۳ Aeppli اعلام کرد که اولین اثبات برای قضیهٔ رأی گیری به ازای k ≥ 1 {\displaystyle k\geq 1}   دارد و به خوانندگان مشتاق مقالهٔ دکتری خود را پیشنهاد کرد.
فرض کنید k = 1 {\displaystyle k=1}   است. ۵ رأی دهنده داریم که ۳نفر به A {\displaystyle A}   و ۲نفر به B {\displaystyle B}   رأی خواهند داد. ( 1 × 2 ≤ 3 {\displaystyle 1\times 2\leq 3}  ) می خواهیم در طول رأی گیری همواره تعداد رای های A {\displaystyle A}   بیشتر از B {\displaystyle B}   باشد. ۱۰ حالت برای ترتیب رأی ها وجود دارد:
در جدول زیر تعداد آرای هر کاندید را در هر مرحله از رأی گیری برای حالت B A B A A {\displaystyle BABAA}   بررسی می کنیم: