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.