Round Robin Ties

A round-robin tournament involving N teams consists of N(N-1)/2 
matches such that each team plays each other team exactly once.
Let T(N) denote the number of distinct sets of outcomes of a
round-robin tournament of N teams in which each team wins exactly 
half of its games.

Obviously if N is even then each team plays an odd number of
other teams, so no team can win exactly half its games.  Thus
we can assume N is odd (although we can ask more general questions
that apply to both odd and even N).

One simple idea for characterizing the number of distinct round-
robin ties for N = 2n+1 teams is that it equals the coefficient of 
(x1 x2 .. xN)^n in the expansion of

    f(x1,x2,..,xN) =  PROD (xi + xj)
                      i<>j

Of course this expansion consists of 2^(N(N-1)/2) terms, so it's
not feasible to write out the entire expansion just to pick off the
coefficient of one particular term.  However, notice that we can 
explicitly define T(N) in terms of a certain partial derivative:

                    1         d^(nN) f(x1,..,xN)
         T(N)  = -------   ------------------------
                 (n!)^N    d^n x1  d^n x2 ...d^n xN

For example, with N=3 we have n=1 and

    f(x1,x2,x3) = (x1+x2)(x1+x3)(x2+x3)

                =  x1^2 x2  +  x1^2 x3  +  x2^2 x1  +  x2^2 x3

                     +  x3^2 x1  +  x3^2 x2  +  2 x1 x2 x3

Only the final term, 2 x1 x2 x3, contains all three of the variables, 
so if we take the partial derivative of f with respect to x1, then 
x2, and then x3, we have T(3) = 2.

The benefit of this approach is that we can evaluate the partials
of f without actually expanding the product, and we can perform this 
evaluation in a way that takes advantage of a great deal of symmetry, 
so that the number of non-zero terms is relatively small.

To see how this approach can be developed into useful formulas, first
consider again the trivial case N=3.  I'll use  x,y,z  in place of
x1,x2,x3 for typographical convenience.  We have the fundamental
function
            f(x,y,z) = (x+y)(x+z)(y+z)

and we want to evaluate the partial with respect to x, which can be
represented by
                          f(q,y,z) - f(-q,y,z)
              f_x(y,z) = ----------------------
                                  2q

in the limit as q goes to zero.  Now we want the partial of this
function with respect to y, which we can represent by the limit of

                          f_x(q,z) - f_x(-q,z)
              f_xy(z)  = ----------------------
                                  2q

as q goes to zero.  Lastly, we want the partial of this function with
respect to z, which is

                           f_xy(q) - f_xy(-q)
              f_xyz   =   --------------------
                                   2q

If we substitute all the way back to give an expression for f_xyz in
terms of the fundamental function f, we have

         
 (2q)^3  f_xyz  =  f(q,q,q) - f(q,q,-q) - f(q,-q,q) + f(q,-q,-q)

                  - f(-q,q,q) + f(-q,q,-q) + f(-q,-q,q) - f(-q,-q,-q)

There are a couple of important things to notice about this.  First, 
the coefficient of each f term depends on the arguments of that term.  
To be precise, the coefficient of the general term f(r,s,t) is the 
product M(r)M(s)M(t) where M(q)=1 and M(-q)=-1.  (We'll see how this 
generalizes below.)  Second, recalling that f(x,y,z)=(x+y)(x+z)(y+z), 
it's clear that if any two of the arguments of f sum to zero, then f 
must equal zero.  Thus we are left with simply

            f(q,q,q) - f(-q,-q,-q)      (2q)^3 - (-2q)^3
  f_xyz  =  ----------------------  =  ------------------  =  2
                   (2q)^3                    (2q)^3

Therefore, the coefficient of xyz in the expansion of f(x,y,z) is 
2/(1!)^3 = 2.

Now for a slightly less trivial example, consider the case N=5.  In
this case the fundamental function is the product of all sums of two
of the five variables v,w,x,y,z, and T(N) is the coefficient of 
(vwxyz)^2 in the expansion of f.  This means we need to evaluate the
SECOND partial derivatives with respect to each of these variables.  
So, in order to get the second derivatives we need to evaluate the 
function at three values, q, 0, and -q.  It turns out that the overall 
partial is a linear combination of the f functions with every possible 
set of five arguments from the set {q,0,-q}, and the coefficient of 
the general term f(r,s,t,h,g) is the product M(r)M(s)M(t)M(h)M(g) 
where
            M(q) = 1     M(0) = -2     M(-q) = 1

We'll see later that the "M" functions are always just the nth row of 
binomial coefficients with alternating signs.

Now, it would be impractical to write out the entire expression, 
because there are 5^3 = 125 terms.  However, we again notice that if 
any two of the arguments of f sum to zero, then f itself is zero, so 
it's clear that we need not consider any terms with more than one "0" 
argument, nor any that contain both q and -q.  Thus, we need only 
consider the terms that contain all +q arguments (possibly with 
exactly one 0), or all -q arguments (possibly with exactly one 0). 
Thus we have

 (q^2)^5  f_vwxyz =   (1)^5 f(q,q,q,q,q)  +  (1)^5 f(-q,-q,-q,-q,-q)

                            + (5) (1)^4 (-2)^1 f(0,q,q,q,q)

                            + (5) (1)^4 (-2)^1 f(0,-q,-q,-q,-q)

Notice that the "denominator" for these derivatives was just q (instead
of 2q as in the case N=3), so the overall denominator of second partials
with respect to all five variables is (q^2)^5.  Also, notice that I've
represented the f terms contains four q's and one 0 by just a single
term with a multiplier of 5, because there are 5 possible slots for the
zero to be placed, and similarly for the terms with four -q's and one 0.

So, the overall (second) partial with respect to the five variables is 
simply

           (2q)^10  + (2q)^10 - 10 (2q)^6 (q)^4 - 10 (-2q)^6 (-q)^4
 f_vwxyz = ---------------------------------------------------------
                                    (q^2)^5

               =  768

This means the coefficients of (vwxyz)^2 in the expansion of 
f(v,w,x,y,z)  is  768/(2!)^5 = 24,  so we have T(5) = 24.


Now let's go on to the case N=7.  Here we need to take the third 
partials with respect to each of seven variables, and we do this by 
evaluating the fundamental function f at values of {+3q, +q, -q, -3q}.  
Again we arrive at a linear combination of f terms with every possible 
set of arguments from the set {3q,q,-q,-3q}, and the coefficients are 
given as products of the M values

     M(3q) = 1    M(q) = -3    M(-q) = 3    M(-3q) = -1

We also see that we can neglect any terms whose arguments include both 
3q and -3q, or both q and -q.  Thus we need only consider the terms 
whose arguments consist entirely of {3q,q} or {3q,-q} or {-3q,q} or 
{-3q,-q}.  Let's consider the general case of the terms whose arguments 
consist of {r,s} where r+s is not zero.  This means we could have all 
seven of the arguments equal to r, or six r's and one s, or five r's 
and two s's, and so on.  Thus the sum of all such terms is

   7              i     7-i     i(i-1)/2     (7-i)(6-i)/2      i(7-i)
 SUM   C(7,i) M(r)  M(s)    (2r)         (2s)             (r+s)
  i=0

So we can evaluate this sum for {r,s} equal to each of the pairs {3q,q},
{3q,-q}, {-3q,q} and {-3q,-q} to give the complete "numerator" of the
(third) partial derivative with respect to each of the seven parameters.
However, this will result in "double-bookkeeping" of the terms that
consist of just a single argument, such as {3q}.  Basically, the terms
of the summation with i=0 and i=7 each occur in two of the summations,
so we have to deduct one copy of each of those terms.  

Then, noting that the "denominator" of the overall third partial of 
seven variables with increment 2q is ((2q)^3)^7, we arrive at

     f_{3rd partial wrt seven variables} = (3!)^7 (2640)

and so T(7) = 2640.


To conclude with a non-trivial example, let's consider the case N=9.
In this case we need to take the 4th partial of f with respect to nine
variables, and we do this by evaluating f with various combinations of
the arguments {2q,q,0,-q,-2q}, for which the "coefficient factors" are

 M(2q) = 1   M(q) = -4    M(0) = 6    M(-q) = -4     M(-2q) = 1

Again we see that the only non-zero values of f will occur for terms
whose arguments are from the set {2q,q,[0]}, {2q,-q,[0]}, {-2q,q,[0]},
or {-2q,-q,[0]}, where [0] signifies that there can be at most one
argument equal to 0.  By the same reasoning as before, the sum of the
f terms containing no "0" argument is given by

    9              i     9-i     i(i-1)/2     (9-i)(8-i)/2      i(9-i)
  SUM   C(9,i) M(r)  M(s)    (2r)         (2s)             (r+s)
   i=0

and the sum of the f terms containing exactly one 0 is given by

      8            i    8-i    i(i-1)/2    (8-i)(7-i)/2     i(8-i) i 8-i
9*6 SUM C(8,i) M(r) M(s)   (2r)        (2s)            (r+s)      r s
     i=0

Note that we've multiplied the second summation by 9 because there are
nine possible slots for the single 0 to be placed, and we've multiplied
it by 6 to account for the single 0 argument with M(0)=6.   Also, note 
that if we evaluate these two summations for each of the sets {r,s} = 
{2q,q} or etc, we will double bookkeep the leading and trailing terms 
of each summation, so we need to deduct one copy of each of these 
terms.

Having done that, and noting the "denominator of the overall 4th 
partial wrt nine variables with an increment of q is (q^4)^9, we arrive 
at
     f_{4rd partial wrt nine variables} = (4!)^9 (3230080)

so we have T(9) = 3230080.


Another way of computing T(N) is based on "n-fold derangements" of the 
permutations of N variables, but I'll leave that for another time.