The Exact Number of Ways that the Condorcet Paradox Can Happen By Shalosh B. Ekhad Theorem:, Suppose that you have n voters and three candidates and each voter is asked to totally-order the three candidates and then the votes given to each of the six rankings is counted resulting in a certain composition of n into six parts. Of course the total number of such compositions is binomial(n + 5, 6) Let , f(n), be the number of such compositions that give rise to the famous Condorcet paradox i.e. a majority of the voters prefer candidate 1 to candidate 2, candidate 2 to candidate 3, candidate 3 to candidate 1, or vice-versa Then we have the generating function infinity ----- 2 3 \ n (t - t + 1) t ) f(n) t = ----------------- / 6 5 ----- (t - 1) (t + 1) n = 0 In Maple input notation the right side is: (t^2-t+1)*t^3/(t-1)^6/(t+1)^5 More informatively, the weighted generating function whose coeff. of t^n gives all the score vectors is: 3 3 / (t x[p123] x[p231] x[p312] + 1) t x[p312] x[p123] x[p231] / ( / 2 2 2 (t x[p123] x[p321] - 1) (t x[p213] x[p312] - 1) (t x[p312] x[p123] - 1) 2 2 2 (t x[p132] x[p231] - 1) (t x[p123] x[p231] - 1) (t x[p231] x[p312] - 1)) and in Maple input notation (t^3*x[p123]*x[p231]*x[p312]+1)*t^3*x[p312]*x[p123]*x[p231]/(t^2*x[p123]*x[p321 ]-1)/(t^2*x[p213]*x[p312]-1)/(t^2*x[p312]*x[p123]-1)/(t^2*x[p132]*x[p231]-1)/(t ^2*x[p123]*x[p231]-1)/(t^2*x[p231]*x[p312]-1) In fact, we have the following explicit expression 4 3 2 (2 n + 3) (n + 6 n + 16 n + 21 n - 35) f(n) = ----------------------------------------- 7680 4 3 2 n + (-1/512 n - 3/256 n - 3/256 n + 9/512 n + 7/512) (-1) Alternatively: n (n - 1) (n - 2) (n + 2) (n + 1) f(2 n) = --------------------------------- 120 n (n + 4) (n + 3) (n + 2) (n + 1) f(2 n + 1) = --------------------------------- 120 In Maple input notation the right side is: 1/7680*(2*n+3)*(n^4+6*n^3+16*n^2+21*n-35)+(-1/512*n^4-3/256*n^3-3/256*n^2+9/512 *n+7/512)*(-1)^n For the sake of Sloane, the first 40 terms are: [0, 0, 0, 1, 0, 6, 1, 21, 6, 56, 21, 126, 56, 252, 126, 462, 252, 792, 462, 1287, 792, 2002, 1287, 3003, 2002, 4368, 3003, 6188, 4368, 8568, 6188, 11628, 8568, 15504, 11628, 20349, 15504, 26334, 20349, 33649, 26334] ------------------------------------------------------- This took, 64.307, seconds.