Round Robin Ties

Intreat me not to leave thee, or to return from following after thee, for whither thou goest, I will go, and where thou lodgest, I will lodge. Thy people shall be my people, and thy God my God. Where thou diest, will I die, and there will I be buried. The Lord do so to me, and more also, if ought but death part thee and me.

Ruth, 1:16

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 (x₁ x₂ ... x_N)ⁿ in the expansion of

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:

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

Only the final term, 2x₁x₂x₃, contains all three of the variables, so if we take the partial derivative of f with respect to x₁, then x₂, and then x₃, 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 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 x₁, x₂, x₃ for typographical convenience.  We have the fundamental function

and we want to evaluate the partial with respect to x (at x=0), which can be represented by

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

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

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

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.) Also, 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. Therefore we are left with simply

Therefore, the coefficient of xyz in the expansion of f(x,y,z) is 2/(1!)³ = 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)² 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, and M(−q) = 1. (As will become apparent, the "M" functions are always just the nth row of binomial coefficients with alternating signs.) It would be impractical to write out the entire expression, because there are 5³ = 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

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²)⁵. Also, notice that we've represented the f terms containing 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

This means the coefficients of (vwxyz)² in the expansion of f(v,w,x,y,z) is 768/(2!)⁵ = 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, and M(−3q) = −1. 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

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)³)⁷, we arrive at

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

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

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

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} 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 with respect to nine variables with an increment of q is (q⁴)⁹, we arrive at

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 we leave that for another time.

Return to MathPages Main Menu