From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Lit review on regular tournaments (was: Probability question)
Date: 18 Aug 1997 18:16:19 GMT
A recent post by a Scrabble player prompted a number of followups
concerning regular (i.e., completely-tied) tournaments. I've done some
reading and found a number of interesting results in this direction,
which I thought I'd share.
In particular, the answer I posted to the original question was
incorrect (too high by about 20%); the correct value has been posted.
The original post asked,
>
>From: paul@ultra (Paul Giaccone)
>Subject: Probability question
>Date: 13 Aug 1997 17:09:25 GMT
>
>9 people take part in a round robin, each playing one game against
>the other 8. If the probability of a win for any player is 0.5, what is
>the probability that everyone wins exactly 4 games?
Mathematically, the real question here is just to count those tournaments
in which every player has an equal number of wins and losses. As Goethe
observed, mathematicians would say it differently:
>From: nobody@REPLAY.COM (Anonymous)
>Subject: All EULERIAN ORIENTATIONS of a complete graph?
>Date: Sat, 16 Aug 1997 16:58:42 +0200 (MET DST)
>
>Recently in sci.math, a question was posed that reduces to finding the
>number of Eulerian orientations of the graph K_9 [...]. As far as
>I know, the problem of enumerating all the Eulerian orientations of an
>undirected Eulerian graph remains unsolved, in general. Is a solution
>known for the special case of *complete* Eulerian graphs?
The answer to the question probably intended is "no". There is no "formula"
giving the number of regular tournaments with N players, unless you
accept answers like "The coefficient of blah blah in blah blah blah". An
asymptotic expression is obtained in [1]: the number of regular tournaments is
RT(N) = (2^(N+1)/Pi/N)^(N-1)/2 * Sqrt(N/E) * (1 + O(N^(-1/2+eps)))
assuming of course that N is odd.
(In the language of the original post, the probability of a complete tie
among N players decreases faster than exponentially.)
One could ask for an estimate of the complexity of computing these numbers;
some information is in [4], which implies that such problems are hard.
For small values of N, the value of RT[N] has been computed; in
particular, there is another paper [2] by McKay, which has the data we
seek. Apparently the first printed calculation appeared in [3] (which
I have not seen, and which only goes as far as 9 players).
McKay's paper [2] is quite short. He uses the obvious (to a combinatorialist!)
approach I mentioned in my previous post:
>
>From: rusin@vesuvius.math.niu.edu (Dave Rusin)
>Date: 16 Aug 1997 09:41:11 GMT
>
>[The number we seek may be viewed]
>as a coefficient in the expansion of Prod( (X_i + X_j), 1 <= i < j <= 9 ),
>but while I can find clever expressions for this product (even when
>pushing to 11 or 13 players) I can't pick out the appropriate coefficient
>so easily,
I had attempted to isolate the relevant coefficient as a linear combination
of the values of P at various values of (x1, ..., xn), but I failed to
find the clever linear combination McKay used (which uses evaluations at
complex points, in principle, although he worked mod-p instead and applied
the Chinese Remainder Theorem).
Here are the numbers of regular tournaments among N players, from [2]:
N RT(N)
1 1
3 2
5 24
7 2 640
9 3 230 080 ( <- the number sought by the original poster)
11 48 251 508 480
13 9.3 x 10^15 (McKay reports actual values which I am too
15 2.4 x 10^22 lazy to reprint completely)
17 8.6 x 10^29
19 4.3 x 10^38
21 3.0 x 10^48
The first few of these values agree with those "guessed" today:
>
>Date: Mon, 18 Aug 1997 00:41:28 -0600
>From: ksbrown@seanet.com
>
>My guess is that there are 3230080 ways in which 9 players could all
>break even (out of 2^36 distinct equi-probable outcomes). Similarly
>I think the number of ways that 7 players could tie in a round robbin
>is 2640 (out of 2^21), and the number for ways 5 players could tie
>is 24 (out of 1024), and the number of ways 3 players could tie is 2
>(out of 8).
You may note that the value for N=9 is somewhat smaller than the
3,870,720 I reported in a previous post. My program neglected the extra
symmetry involved when the "types" of tournaments among those who beat
one player and those beaten by that player were the same; thus I
overcounted those tournaments. Fortunately, someone did the sensible thing
and ran a simulation, which as s/he reports
>
>Date: Sat, 16 Aug 1997 16:32:29 +0200 (MET DST)
>From: nobody@REPLAY.COM (Anonymous)
>
>This comes to 0.0000563264, which is pretty close, but not quite the
>results I obtain from simulations (consistently below 0.000050).
>
supports the somewhat lower count. (The correct probability is about
.00004700385034, less than one chance in twenty thousand.) I see
this same (?) person has clarified the empirical results:
>
>Date: Mon, 18 Aug 1997 04:05:41 +0200 (MET DST)
>
>The answer that I get from the simulation program I posted is
>0.00004652, from a sampling of 100000000 tournaments, and using a
>256-byte state array for random(). All of the half-dozen simulations
>I've carried out have given results in the 0.000045-0.000050 range.
which agrees with the theoretical value.
Going in a slightly different direction, a more combinatorial approach
might allow not only an enumeration but perhaps a classification of
all-tied tournaments. This sort of idea was suggested by Tilly:
>
>From: Benjamin.J.Tilly@dartmouth.edu (Benjamin J. Tilly)
>Date: 17 Aug 1997 03:46:16 GMT
>
>My idea was to start with the normalized score vector that you want,
>namely 444444444, and work backwards to see what score vectors you
>could get if you delete one person at a time. Then I was planning to
>work forwards to calculate the probability with n people in the
>tournament of getting each normalized score vector in question, until
>we finish with 444444444.
The advantage to this approach is that it can clarify the distinct
combinatorial structures possible in such a tournament, and indeed is
applicable to counting tournaments with any pre-assigned "score vector".
The disadvantage is the combinatorial explosion typical in this area
(studies of partitions, Young tableaux, and other similar topics). The
underlying problem is that there are quite a lot of possible outcomes
to a tournament. As far as I can tell, these are the counts:
N outcomes summands
1 1 1
3 2 2
5 9 7
7 59 34
9 490 219
11 4639 1696
13 48107 maybe 15000?
Here the last column shows the number of terms in the most compact formula
I could devise which would keep track of all possible outcomes: the
polynomial P, whose coefficients are the numbers we seek, is a symmetric
function of N variables, and so may be expressed as a polynomial in the
elementary symmetric functions a_1, ..., a_N. For example, when N=3,
P=a1*a2-a3, and when N=5, P =
a3^2*a4 -a1*a2*a3*a4 +a1^2*a4^2 +a1*a2^2*a5 -a2*a3*a5 -2*a1*a4*a5 +a5^2
These expressions are found rather simply by Maple, after noting that
P^2 * 2^N * a_N happens to be the resolvent of f(x) and f(-x), where
f(x) = Prod(x-x_i) = x^N - a1*x^(N-1) + ... +- a_N. It does not appear
to be an easy task to "pick out the coefficient of (x1 x2 ... xN)^(N-1)/2 "
here, although McKay's techniques may make that possible; nonetheless,
it's clear that even in this compressed form, P has too many terms
to manage effectively for N > 11 or so. Tilly wasn't recommending this,
but computing the numbers of all possible tournament outcomes is
clearly infeasible for any but the smallest N.
The combinatorial, rather than enumerative, approach might let us look
at distinct tournament structures. Let me explain by counting the
tournaments among 7 players. There are really just three distinct
kinds of tournaments here.
First imagine seating the 7 players at a round table. If every player
beats the three players to his or her left, we have a regular tournament.
If everyone were to get up and move one chair to the left, and then
again beat the players to his or her left, there would be no change in
the tournament results. On the other hand, if one player stayed seated
and the others moved around, then the beat-three-on-the-left algorithm
would produce a different set of tournament results. Thus we count
6!=720 distinct tournaments which are actually isomorphic (i.e., the
same after a relabelling of the vertices).
Now imagine the players seated again at the table, but this time each
play beats the players 1, 2, or _4_ seats to the left. I claim this is
really a new tournament. Indeed, if you look at the three players any one
player beats, you'll see that in this tournament, those three players
are tied (each beats one of the others and loses to the remaining one).
In the tournament of the previous paragraph, this was never the case
(the player to my immediate left beat both of the other players I beat).
This distinction makes it clear the two tournament types are not isomorphic.
Observe that we can again make more tournaments isomorphic to this one
by shuffling all the players but one, but something different occurs:
If we number the players mod 7, and then have player #i move to the chair
previously held by player #(2*i), then we have not changed the tournament
results! (this is because 2*{1,2,4} = {1,2,4} mod 7!). In other words,
this tournament has an additional symmetry of order 3, and so all the
reshufflings contribute only 6!/3 = 240 tournaments.
Finally, we arrange a third regular tournament by doing the following.
Seat three players at a small round table, and three others at a
similar table directly above them. Each player beats the player to their
left, and the players on the top table beat the one player directly
below them. Also, all the players on the top table beat the unseated
player, who in turn beats the players at the bottom table. The
unseated player is the only one whose sets of superior and inferior
players play in cyclic sets of three. This makes it clear that this
tournament is distinct from the other two, and also makes it clear
that no relabelling can preserve the tournament results if it relabels
the unseated player. That is, the symmetry group of this tournament is
not transitive; we say the tournament is not _homogeneous_ (see
e.g. [7]). Actually, the only symmetry is to rotate the two tables
simultaneously, giving 7!/3 = 1680 tournaments of this type.
It's not hard to show these are the only three isomorphism types of
regular tournaments on 7 players, giving 2640 total tournaments.
(My tournament-counting program missed the symmetries of this last sort,
giving too high a count for 9-player tournaments.)
As you might imagine, there's quite a lot of literature about isomorphism
types of tournaments, including some with a heavy group-theoretic bent [5].
Reference [6] discusses the types of regular tournaments among 9 players,
and considers the isomorphism problem for higher numbers of players.
There is also a fair amount of literature studying paths within the
directed graphs underlying regular tournaments; its relevance is not
altogether clear to me. See e.g. [8].
I'm not aware of a thorough discussion of regular tournaments in book
form, but it's a pretty topic, and might warrant such a treatment.
dave
References:
[1] McKay, Brendan D. The asymptotic numbers of regular tournaments,
Eulerian digraphs and Eulerian oriented graphs. Combinatorica 10
(1990), no. 4, 367--377.
[2] McKay, Brendan D. Applications of a technique for
labelled enumeration. Proceedings of the fourteenth Southeastern
conference on combinatorics, graph theory and computing (Boca Raton,
Fla., 1983). Congr. Numer. 40 (1983), 207--221.
[3] Liskovec, "Number of Eulerian digraphs and regular tournaments",
Vesci Akad Nauk BSSR, Ser Fiz-Mat. Nauk, (1971) #1 22-27
[4] Mihail, M.; Winkler, P. On the number of Eulerian
orientations of a graph. Algorithmica 16 (1996), no. 4-5, 402--414.
[5] Ito, Noboru, Doubly regular tournaments of Szekeres
type. J. Austral. Math. Soc. Ser. A 32 (1982), no. 3, 399--404.
[6] Astie-Vidal, A.; Dugat, V.; Tuza, Z. Construction of nonisomorphic
regular tournaments. Combinatorics '90 (Gaeta, 1990), 11--23,
Ann. Discrete Math., 52, North-Holland, Amsterdam, 1992.
[7] Tabid, Claudette, Pluralite des tournois homogenes de meme
ordre. Ann. Sci. Math. Quebec 8 (1984), no. 1, 81--95.
[8] Bollobas, Bela; Huggkvist, Roland, Powers of Hamilton cycles in
tournaments. J. Combin. Theory Ser. B 50 (1990), no. 2, 309--318.
==============================================================================
From: fredh@ix.netcom.com (Fred W. Helenius)
Newsgroups: sci.math
Subject: Re: Probability question
Date: Tue, 19 Aug 1997 00:11:31 GMT
[deletia]
It appears that Kevin Brown has it right. Sequence A7079 in Sloane's
On-Line Encyclopedia of Integer Sequences
is described as "Labeled regular tournaments with 2n+1 nodes", and
has the terms
1,2,24,2640,3230080,48251508480,9307700611292160,
24061983498249428379648,855847205541481495117975879680.
A reference is given to Congressus Numerantium, 40 (1983), p.215.
--
Fred W. Helenius
==============================================================================
From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math
Subject: Round-Robin Ties
Date: Sun, 21 Sep 1997 22:18:01 GMT
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) if 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 repsect 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*6SUM 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.
__________________________________________________________________
| MathPages /*\ http://www.seanet.com/~ksbrown/ |
| / \ |
|__"When I am here [at Milan], I do not fast on the Sabbath; when__|
I am at Rome, I do fast on the Sabbath." St. Ambrose 4th c.