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.

Return to MathPages Main Menu