## 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)

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.
```