موضوع مقاله: قضیه رأی‌گیری برترند | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه رأی‌گیری برترند | مقدمه: فرض کنید در یک انتخابات کاندید ، رأی و کاندید ، رأی به دست می‌آورد؛ به طوری که ( یک عدد صحیح مثبت است). | ## بخش 1: قضیه رأی‌گیری برترند | تعداد (یا احتمال) حالاتی را به دست آورید که در تمام طول رأی‌گیری آرای ، دست کم تا بیشتر از آرای باشد. (احتمال آن برای حالت برابر با است.) تاریخچه در سال ۱۸۸۷ جوزف برترند که مسئلهٔ رأی‌گیری را بیان کرده‌بود برای حالت خاص راه حلی از طریق روابط بازگشتی ارائه داد و خواستار راه حل مستقیمی برای آن شد. در سال ۱۹۲۳ Aeppli اعلام کرد که اولین اثبات برای قضیهٔ رأی‌گیری به ازای دارد و به خوانندگان مشتاق مقالهٔ دکتری خود را پیشنهاد کرد. ۱۰ حالت برای ترتیب رأی‌ها وجود دارد: در جدول زیر تعداد آرای هر کاندید را در هر مرحله از رأی‌گیری برای حالت بررسی می‌کنیم: A A B A B رأی ۳ ۳ ۲ ۲ ۱ A ۲ ۱ ۱ ۰ ۰ B برای هر ستون تعداد آرای A بیشتر از B است. برای حالت در هر مرحله از رأی‌گیری داریم: A A B B A رأی ۳ ۲ ۲ ۲ ۱ A ۲ ۲ ۱ ۰ ۰ B در این حالت تعداد رأی‌های در مرحلهٔ چهارم به رسیده. از بین ۱۰حالت ممکن برای ترتیب آرا تنها در ۲حالت و همواره تعداد رای‌های بیشتر از است که برابر مقدار می‌باشد. اثبات با انعکاس برای حالت آندره برای به دست آوردن تعداد حالت‌های مطلوب مسئله، حالت‌های نامطلوب را از تعداد کل حالات کم کرد. | ## بخش 2: قضیه رأی‌گیری برترند | می‌خواهیم تناظر یک به یکی بین جایگشت‌های نامطلوبی که با شروع می‌شوند و تمام جایگشت‌هایی که با شروع می‌شوند برقرار کنیم. از آنجایی که تعداد رأی‌های بیشتر از است اگر رأی اول برای کاندید باشد بالاخره به گره می‌رسیم. برای هر رشته که با شروع شود و گره داشته باشد رأی‌ها را تا رسیدن به اولین گره معکوس می‌کنیم (یعنی هر را به تبدیل می‌کنیم و برعکس) و رشته‌ای که با شروع می‌شود می‌سازیم. به‌طور مشابه هر رشته‌ای که با شروع می‌شود را به رشته‌ای که با شروع می‌شود و گره دارد (نامطلوب است) تبدیل می‌کنیم. اگر ۲تبدیل‌یافته یکسان باشند معکوس تا گرهٔ اول آن‌ها که همان رشته‌هایی هستند که از آنها به دست آمده‌اند هم یکسان اند پس این تبدیل‌ها یک به یک است) در نتیجه تناظری یک به یک داریم. تعداد حالاتی که با شروع می‌شوند معادل جایگشت‌هایی است که می‌توان با تا و تا ساخت یعنی . در نتیجه تعداد حالات مطلوب از روابط زیر به‌دست می‌آید: و احتمال و قوع آن برابر خواهدبود. | ## بخش 3: قضیه رأی‌گیری برترند | تعمیم‌یافته: مجاز بودن تساوی آرا مسئلهٔ اصلی یافتن احتمال آن است که همواره تعداد رأی‌های کاندید اول اکیداً بیشتر از کاندید دوم باشد. حال فرض کنید می‌خواهیم احتمال آن را به دست بیاوریم که هیچگاه تعداد رأی‌های کاندید دوم از کاندید اول بیشتر نشود (یعنی وجود گره مجاز باشد). تعداد کل رشته‌هایی که با تا و تا برای حالات رأی‌گیری می‌توان ساخت برابر است با : . هر رشتهٔ رأی‌گیری را به صورت مسیر شبکه ای روی صفحهٔ دکارتی نمایش می‌دهیم به‌طوری که: مسیر را از نقطهٔ (۰٬۰) شروع می‌کنیم. تناظر یک به یکی بین رشته‌ها و مسیرهای بین نقاط و با محدودیت حرکت به راست و بالا وجود دارد. یک رشته نامطلوب است اگر زمانی کاندید دوم رأی بیشتری از کاندید اول کسب کند یعنی مسیر متناظر آن از خط عبور کرده و به خط اصابت کند.بند انگشتی|چپ|220px|مسیر نامطلوب (آبی) و بازتاب شده‌اش (قرمز) نقطهٔ شروع تا اولین تلاقی هر مسیر نامطلوب با خط را نسبت به خط مذکور قرینه می‌کنیم. به‌طور مشابه با اثبات مسئلهٔ اصلی مسیرهای نامطلوب از به تناظر یک به یکی با مسیرهای بین نقاط و با محدودیت حرکت به راست و بالا دارند. | ## جمع‌بندی | تعداد این مسیرها است پس تعداد مسیرهای مطلوب به صورت زیر به دست می‌آید: و احتمال وقوع آن برابر خواهدبود.