A recurrence for the Condorcet Paradox with Three Candidates where the only \ allowed permutations are 123,231,312 By Shalosh B. Ekhad Suppose that there are 2n-1 voters each completely ranking three candidates,\ let's call them 1,2,3. Also assume that there are ony 3 allowed choice\ s for each of these 2n-1 voters Namely: 123, 231,312 (2 n - 1) Of course there are , 3 , possible such vote-preferences Let a(n) be the number of vote-preferences that lead to Condorcet scenarios\ in this resticted case). Thanks to the beautiful bijection between comp\ ositions (into non-neg. integers) of n-2 and Condorect vote-count profil\ es and Using Wilf-Zeilberger proof theory it is easy to get the following secon\ d-order recurrence for a(n) 36 (2 n + 1) a(n) (17 n + 13) a(n + 1) ----------------- - -------------------- + a(n + 2) = 0 n + 1 n + 1 and in Maple formal 36*(2*n+1)/(n+1)*a(n)-(17*n+13)/(n+1)*a(n+1)+a(n+2) = 0 subject to the initial conditions a(1) = 0, a(2) = 6 Using this recurrence we can easily compute the first, 100, terms [0, 6, 90, 1050, 11130, 112266, 1099098, 10550826, 99899514, 936435786, 8711707290, 80572452714, 741766408890, 6803700252810, 62219207836890, 567597206875050, 5167463468534010, 46965976868507850, 426262280218695450, 3864157168469020650, 34994228358927126330, 316641268097190529290, 2863009258924604739930, 25870683864624929430570, 233647692300335011249530, 2109191684849706568821066, 19032645957721399864980378, 171685784298888770565017706, 1548251828313825999072400314, 13958479816004867460240945546, 125816796785329883761738005978, 1133850420734865814990318087338, 10216460377740605116348436550138, 92041165026725183112991964668362, 829103714536173987241910551785498, 7467715467556956331637059881971946, 67255053053338020506805806607644730, 605655457016123826411119885404207626, 5453741056851022136514823383917382234, 49106113579900726696196007375925419306, 442132330358214607259508582056613709434 , 3980592139981761067920289996513043364426, 35836405149445359803142720341407119641754, 322615223146571807187178379043559611265386, 2904229661204239946450402588616392092351674, 26143546604773567311578596521811319728562826, 235335280182798810952970200296997962049517274, 2118360717288152156349918469810405986768891306, 19067963421100158697853660676464929813478972154, 171633184720853147562178967432887532848512234186, 1544869052820815944769059195946036858692045867290, 13905171234104747368619909029714720384589119607274, 125157235349088310791958623991943255123236907278650, 1126499864966344711830257162046253901732011956857610, 10139170481750942471152415305431678656450932624638810, 91257859061494378025835809917952591250170970087808554, 821362949021784004531558861459179796321145587056889722, 7392601318313376044979898711611883548144034827941989194, 66536066993681887886372531868308022198412059838336378266, 598845663965292645712386880731024757142897848867904803434, 5389778059796735338976085738314826435986449168372637263290, 48509328254708407220313759265817571578025228873120343757706, 436594474494578766134569993223393527393201506439069728124890, 3929433764119487475780543905923520978213213927641997666660010, 35365566608067348515294618515683461455334478283195291776132090, 318295360537096167350992755179363994453863001689670447408497610, 2864700014497392416670916354099480932970627822810644911916081690, 25782631794073491696193085822449493335471142191043878698998002410, 232046319945813754249908549802034396885669185076806088078434437690, 2088437797221533589456794136844308823605849334326926191597561011210, 18796106321369811583274506615542430611152124405534239978431734758490, 169166276702977166684458372110927217416798794912876244302875453824810, 1522506975489171573949195193312760728642824907694704870007520599021690, 13702646086172115436743585639847191046787461662645697656688946740059210, 123324476726636983626179938234557402658022263695099009316326218946100890, 1109925550844378386482428108319761680045044703973857581474281519557555050, 9989371763178430510492806043063144776960638858839083556517437776304295610, 89904678141519683940881790461976059743448408848012941331102775173429773450, 809144744417351024631998323980000040069210662368602848645520076762771679450, 7282323695176756561371922482507991949148135064589747720670360727912989863850, 65541080170184557902834605997741460671108866452322690044775652845748864527610, 589871048597764407047904337361514866224319540798479946203352599731228416611530, 5308849989173774878326262938265350888216308943508019268779470521067721488317210 , 47779733808394947902897592653156028847564923026178460611142175671551654691443\ 690, 43001827152668656244319856134812970879733334548699900079005096885274303205\ 7770810, 3870169750349182040463766743539454480804380695947009479767934698012734\ 612382403850, 34831569959195638797626064749086490065772127672939232239977849133\ 082336738440787290, 31348446534067656871827708305906724529384144072675163809163\ 9427265208454290604023850, 2821362858469964955711650000055493665500534377554503\ 192282563362969003322152320950650, 25392286969442539576359755919453521957617401\ 296841391901510805440295704970653072747850, 22853075172654290243243461036364970\ 3631541231666874949673740564343544315302967031191450, 2056778110122726489820730\ 046373102677226737731997467447432277830034308405754974803334250, 18511013689315\ 094379298474557242564445099100301029098364605984532154903953932759692523450, 16\ 6599208329382208752125078149749035479475353544298440011663088808384833903482041\ 343047050, 14993935523464470786111706792696065820199635140753598211496114435116\ 87359832713145220735450, 134945473616527336346645992902362501708611675332631377\ 47712298728895557124328516501605396650, 121450969154546669215662063060904171043\ 674079389273063781780146302662549085386346646623008250, 10930590638192379130527\ 26369759029847213406892517957823195085454634160436552845438974644872650, 983753\ 4291863834628568199427060819646347859367879071371450361209768199499708336388944\ 553677850, 88537830256902455171677489128324005149298729261935393440056670979144\ 860040176938826562870588650] Just for fun here is, a(1000) 5826237505742172032199915397215535235096874958117294731481149036598180539297276\ 8171419349665649120545962547553331673410184929874727650942487842388179497801103\ 7710869389679665060143262793032890624790987142085068220979572188699945584187589\ 6022366679922721888155839316819482478606676789497767263250650757894369632300205\ 7298567573502640457475376628710731761072120608912400359925650370602491296142408\ 2184982157433842198704614278905911119971416047587168112103977329849273482152231\ 7099301338480384806143945676381308509124390533509356500765237851795745774912411\ 5677215567646810975077079178494589890214898311422060192682946518059921253341717\ 6708685275512834394065798875144339686934718730158046090349584267007929447770152\ 4625634455155675118392291861297732937479225812602673889137530025851409760857643\ 0218810367783025320580176364789420076277174489058248419878170835503581873782981\ 3177853030831118544901028269321682635892881353254094602870115992438964834041877\ 649706 Of course, by the law of large numbers a(n)/3^(2*n-1) tends to 1. Now suppose that the prob. of the ranking 123 is p123, the prob. of the rank\ ing 231 is p231 and the prob. of the ranking p312 is 1-p123-p231 . Let b\ (n) be the prob. of a Condorcet scenariowhen where there are 2n-1 voters\ . Using Wilf-Zeilberger proof theory it is easy to get the following fourth-or\ der recurrence for b(n) - 8 p123 p231 (p231 - 1) (p123 - 1) (p123 + p231) (p123 + p231 - 1) (2 n + 5) (2 n + 3) (2 n + 1) b(n)/((n + 3) (n + 2) (n + 1)) + 4 (2 n + 5) (2 n + 3) 4 2 3 3 2 4 4 (4 n p123 p231 + 8 n p123 p231 + 4 n p123 p231 - 4 n p123 p231 3 2 2 3 4 4 2 - 16 n p123 p231 - 16 n p123 p231 - 4 n p123 p231 + 2 p123 p231 3 3 2 4 4 3 + 4 p123 p231 + 2 p123 p231 - n p123 + 6 n p123 p231 2 2 3 4 4 + 13 n p123 p231 + 6 n p123 p231 - n p231 - 2 p123 p231 3 2 2 3 4 3 2 - 8 p123 p231 - 8 p123 p231 - 2 p123 p231 + 2 n p123 + n p123 p231 2 3 4 3 2 2 + n p123 p231 + 2 n p231 - p123 + 2 p123 p231 + 5 p123 p231 3 4 2 2 3 + 2 p123 p231 - p231 - n p123 - 3 n p123 p231 - n p231 + 2 p123 2 2 3 2 2 + 3 p123 p231 + 3 p123 p231 + 2 p231 - p123 - 3 p123 p231 - p231 ) 4 b(n + 1)/((n + 3) (n + 2) (n + 1)) + 4 (2 n + 5) (2 n p123 3 2 2 3 4 + 4 n p123 p231 + 6 n p123 p231 + 4 n p123 p231 + 2 n p231 3 2 2 3 4 - 4 n p123 - 10 n p123 p231 - 10 n p123 p231 - 4 n p231 + 3 p123 3 2 2 3 4 2 + 6 p123 p231 + 9 p123 p231 + 6 p123 p231 + 3 p231 + n p123 2 3 2 2 + 5 n p123 p231 + n p231 - 6 p123 - 15 p123 p231 - 15 p123 p231 3 2 2 - 6 p231 + n p123 + n p231 + p123 + 7 p123 p231 + p231 + 2 p123 2 + 2 p231) b(n + 2)/((n + 2) (n + 3)) + (8 n p123 + 8 n p123 p231 2 2 2 + 8 n p231 - 8 n p123 - 8 n p231 + 20 p123 + 20 p123 p231 + 20 p231 - n - 20 p123 - 20 p231 - 3) b(n + 3)/(n + 3) + b(n + 4) = 0 and in Maple format -8*p123*p231*(p231-1)*(p123-1)*(p123+p231)*(p123+p231-1)*(2*n+5)*(2*n+3)*(2*n+1 )/(n+3)/(n+2)/(n+1)*b(n)+4*(2*n+5)*(2*n+3)*(4*n*p123^4*p231^2+8*n*p123^3*p231^3 +4*n*p123^2*p231^4-4*n*p123^4*p231-16*n*p123^3*p231^2-16*n*p123^2*p231^3-4*n* p123*p231^4+2*p123^4*p231^2+4*p123^3*p231^3+2*p123^2*p231^4-n*p123^4+6*n*p123^3 *p231+13*n*p123^2*p231^2+6*n*p123*p231^3-n*p231^4-2*p123^4*p231-8*p123^3*p231^2 -8*p123^2*p231^3-2*p123*p231^4+2*n*p123^3+n*p123^2*p231+n*p123*p231^2+2*n*p231^ 3-p123^4+2*p123^3*p231+5*p123^2*p231^2+2*p123*p231^3-p231^4-n*p123^2-3*n*p123* p231-n*p231^2+2*p123^3+3*p123^2*p231+3*p123*p231^2+2*p231^3-p123^2-3*p123*p231- p231^2)/(n+3)/(n+2)/(n+1)*b(n+1)+4*(2*n+5)*(2*n*p123^4+4*n*p123^3*p231+6*n*p123 ^2*p231^2+4*n*p123*p231^3+2*n*p231^4-4*n*p123^3-10*n*p123^2*p231-10*n*p123*p231 ^2-4*n*p231^3+3*p123^4+6*p123^3*p231+9*p123^2*p231^2+6*p123*p231^3+3*p231^4+n* p123^2+5*n*p123*p231+n*p231^2-6*p123^3-15*p123^2*p231-15*p123*p231^2-6*p231^3+n *p123+n*p231+p123^2+7*p123*p231+p231^2+2*p123+2*p231)/(n+2)/(n+3)*b(n+2)+(8*n* p123^2+8*n*p123*p231+8*n*p231^2-8*n*p123-8*n*p231+20*p123^2+20*p123*p231+20* p231^2-n-20*p123-20*p231-3)/(n+3)*b(n+3)+b(n+4) = 0 Of course by the law of large numbers, as n goes to infinity, b(n) tends to\ 0 if p123+p231<1/2, tends to 1 if p123+p231>1/2, and to 1/2 if p123+p23\ 1=1/2 Let's try out an example with p123=1/5,p231=1/5, and p312=3/5 and 99 voters\ , i.e. n=50 The exact probabilty of a Condorcet scenario is, 1384005472773927632791341372544818249098560414306043112949779033846 --------------------------------------------------------------------, 63108872417680944432938285222622898373856514808721840381622314453125 and in decimals it is, 0.02193044210 Let's test is with simulations, with, 5000, tries We get that the estimated probability is, 0.021400000000000000000000000000000\ 00000000000000000000000000000000000000000000000000000000000000000000 Let's try out an example with p123=1/4,p231=1/4, and p312=1/2 and 99 voters\ , i.e. n=50 The exact probabilty of a Condorcet scenario is, 12554201268842881412944947335501570576505884144057732170557 -----------------------------------------------------------, 25108406941546723055343157692830665664409421777856138051584 and in decimals it is, 0.4999999123 Let's test is with simulations, with, 5000, tries We get that the estimated probability is, 0.508600000000000000000000000000000\ 0000000000000000000000000000000000000000000000000000000000000000000 Let's try out an example with p123=11/40,p231=11/40, and p312=9/40 and 99 v\ oters, i.e. n=50 The exact probabilty of a Condorcet scenario is, 8449940263761207709281639608\ 594337188324862544993054581380815854375056333733083785515165578716281352\ / 14661283516102472536813719901425726798811193690429282681 / 10043362776\ / 618689222137263077132266265763768711142455220633600000000000000000000000\ 000000000000000000000000000000000000000000000000000000000000000000000000\ 00, and in decimals it is, 0.8413457177 Let's test is with simulations, with, 5000, tries We get that the estimated probability is, 0.847400000000000000000000000000000\ 0000000000000000000000000000000000000000000000000000000000000000000