Problem Ballot (Kertas Suara)

Mumpung sedang happening perihal pilpres, pilkada, dll. Dalam kombinatorika, ada kelas kombinatorial yang disebut "barisan ballot". Ballot (kertas suara) adalah kertas yang dicoblos/dicontreng oleh pemilih untuk menentukan pilihannya.

Contoh ballot (kartu suara). (lessonpix.com)

Problem ballot adalah sebagai berikut: Dalam suatu pemilihan dengan 2 kandidat (A dan B), kandidat A memperoleh p suara dan kandidat B memperoleh q suara, dengan $p>q$. Berapakah peluang perolehan suara untuk A selalu lebih besar dari perolehan suara untuk B selama proses penghitungan?
Berikut ilustrasinya agar lebih jelas. Misalkan ada 5 pemilih, dengan hasil A mendapat 3 suara dan B 2 suara. Salah satu kemungkinan urutan penghitungan suaranya yang valid dalam problem ballot tersebut adalah AABAB. Mengapa demikian? Untuk AABAB, proses penghitungannya adalah A, AA, AAB, AABA, dan AABAB. Selama proses penghitungan, jumlah suara untuk A selalu $>$ jumlah suara untuk B. Di sisi lain,  ABBAA adalah urutan penghitungan yang tidak valid. Poses penghitungan untuk ABBAA adalah A, AB, ABB, ABBA, dan ABBAA. Perhatikan bahwa saat penghitungan ballot kedua (AB), jumlah suara untuk B telah menyamai jumlah suara untuk A, sehingga melanggar syarat yang ditetapkan dalam problem ballot.

Sekarang, kita cari solusi dari problem ballot di atas, yaitu di mana p=3 dan q=2. Semua kemungkinan urutan penghitungannya (tanpa memandang valid/tidak valid) adalah: AAABB, AABAB, ABAAB, BAAAB, AABBA, ABABA, BAABA, ABBAA, BABAA, BBAAA. Nah, dari kesepuluh kemungkinan itu, yang valid hanya 2, yaitu AAABB dan AABAB, Oleh karena itu dalam kasus ini, peluang perolehan suara untuk A selalu lebih besar atau sama dengan perolehan suara untuk B selama proses penghitungan adalah $\frac{2}{10}=0,2$.

Secara umum peluang yang ditanyakan dalam problem ballot ini diberikan oleh $\frac{p-q}{p+q}$.