Counting Various Classes of Tournament Score Sequences

Paul K. Stockmeyer Department of Computer Science The College of William & Mary P. O. Box 8795 Williamsburg, VA 23187-8795 USA

                     stockmeyer@cs.wm.edu

Abstract Based on known methods for computing the number of distinct score sequences for n-vertex tournaments, we develop algorithms for computing the number of distinct score sequences for self-complementary tournaments, strong tournaments, and tournaments that are both self-complementary and strong.

1 Introduction

In graph theory, a tournament, sometimes called a round-robin tournament, is an oriented complete graph, i.e., a directed graph where for any two vertices v and w there is either a directed edge from v to w or from w to v but not both. For background information about tournaments, see the classic book by Moon [9] or the article by Harary and Moser [5].

If an edge of a tournament is directed from vertex v to vertex w we say that v dominates w. The score of a vertex v is the number of vertices that v dominates. The score sequence of an n-vertex tournament is the sequence (s_{1}, s_{2}, …, s_{n}) of vertex scores, written in nondecreasing order:

s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{n}.  (1)

For example, we observe that the score sequences for 5-vertex tournaments are (0, 1, 2, 3, 4), (0, 1, 3, 3, 3), (0, 2, 2, 2, 4), (0, 2, 2, 3, 3), (1, 1, 1, 3, 4), (1, 1, 2, 2, 4), (1, 1, 2, 3, 3), (1, 2, 2, 2, 3), and (2, 2, 2, 2, 2).

This paper develops methods for computing the number of score sequences for various classes of n-vertex tournaments. Section 2 reviews the history of computing the total number of n-vertex score sequences, introducing tools that will be used in later sections. Section 3 provides an algorithm for counting self-complementary score sequences, Section 4 contains two different methods for counting strong score sequences, while Section 5 gives two methods for counting score sequences that are both strong and self-complementary. Section 6 contains some asymptotic results and conjectures.

2 Counting score sequences

Sequence \underline{A000571} in the On-Line Encyclopedia of Integer Sequences (OEIS) [11] gives the number of different score sequences that are possible for an n-vertex tournament. Postulating the existence of a 0-vertex tournament with null score sequence, this sequence begins with n = 0 and reads 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, …. There is no known simple formula for this sequence but various methods have been devised for determining its terms.

The first major effort to catalog score sequences was carried out in 1920 by MacMahon [8], who expanded the product

∏_{1≤i<j≤n} (a_{i} + a_{j})

to generate the score sequence of each of the 2^{\binom{n}{2}} labeled tournaments on n vertices. For example, with n = 5, fourteen of the 1024 terms in this product are a_{1}^{2}a_{2}^{2}a_{3}^{1}a_{4}^{3}a_{5}^{2}, representing some of the labeled tournaments with score sequence (1, 2, 2, 2, 3). By combining these terms with the other terms with the same collection of exponents, MacMahon calculated that there were 14×20 = 280 labeled tournaments with this score sequence, the most of any of the nine possible score sequences. In a Herculean effort of hand calculation, MacMahon carried out this procedure up through n = 9, determining the number of labeled tournaments possessed by each of 490 possible score sequences that arose. The most common sequence turned out to be (2, 3, 3, 4, 4, 4, 5, 5, 6), occurring 5,329,376,640 times among the 2^{36} = 68, 719, 476, 736 labeled tournaments on nine vertices.

Presumably unaware of the work of MacMahon, David [4] made essentially the same hand calculations in 1959, but only for n ≤ 8. This was followed by Alway [1], who in 1962 used a computer to catalog all score sequences up to n = 10.

Of course it is not necessary to generate all the n-vertex tournament score sequences in order to count them. The following test for a sequence of non-negative integers to be the score sequence of a tournament is usually attributed to Landau [7].

Proposition 1. A sequence (s_{1}, s_{2}, …, s_{n}) of n ≥ 1 non-negative integers satisfying (1) is the score sequence of a tournament if and only if

∑_{i=1}^{r} s_{i} ≥ \binom{r}{2} for 1 ≤ r < n, and  (2)

∑_{i=1}^{n} s_{i} = \binom{n}{2}.  (3)

This test was utilized by Bent [2] in a remarkable 1964 Master of Science dissertation, also published by Narayana and Bent [10]. We present Bent’s algorithm, which will be used in later sections.

Definition 2. For all positive n and all non-negative T and E, the array entry F_{n} [T, E] is the number of sequences of length n satisfying (1), (2), s_{n} = E, and

∑_{i=1}^{n} s_{i} = T.

(We can imagine that T stands for Total and E for End.) These F_{n} arrays can be computed using the following recursive formulas.

Proposition 3 (Bent). We have

F_{1} [T, E] = \begin{cases}1, & if T = E; \\ 0, & otherwise, \end{cases}

and for n ≥ 2 we have

F_{n} [T, E] = \begin{cases}∑_{k=0}^{E} F_{n−1} [T −E, k], & if T −E ≥ \binom{n−1}{2}; \\ 0, & otherwise. \end{cases}

Bent then used the values in the F_{n} arrays to count score sequences.

Theorem 4 (Bent). Let S(n) denote the number of distinct score sequences for n-vertex tournaments. Then for n ≥ 1 we have

S(n) = ∑_{E=⌈\frac{n−1}{2}⌉}^{n−1} F_{n} [\binom{n}{2}, E] .

Using Theorem 4 and the computer available to him, Bent computed S(n) for n ≤ 27. With an alternative method, which allowed him to compute S_{2n} from array F_{n} and to compute S_{2m+1} from arrays F_{m} and F_{m+1}, he was able to extend his result up to n = 36. The limiting factor was the speed of the computer he was using.

A recent paper by Claesson et al. [3] provides an alternative method for counting score sequences. Today the OEIS entry \underline{A000571} gives values of S(n) up to n = 1, 675. As a test of our programs for this paper, we verified these numbers for n ≤ 500.

3 Counting self-complementary score sequences

The complement of a tournament T_{n} is the tournament T_{n}^{c} obtained from T_{n} by reversing the direction of all of its edges. Thus a vertex with score s_{i} in T_{n} becomes a vertex of score n−1−s_{i} in T_{n}^{c}. A tournament is called self-complementary if it is isomorphic to its complement. In this case, for each vertex of score s_{i} there is a corresponding vertex of score n−1−s_{i}.

Definition 5. A score sequence of length n is called self-complementary if s_{n+1−i} = n−1−s_{i} for 1 ≤ i ≤ ⌊\frac{n}{2}⌋.

For example, the self-complementary score sequences of length n = 6 are (0, 1, 2, 3, 4, 5), (0, 2, 2, 3, 3, 5), (1, 1, 1, 4, 4, 4), (1, 1, 2, 3, 4, 4), (1, 2, 2, 3, 3, 4), and (2, 2, 2, 3, 3, 3). Clearly selfcomplementary tournaments have self-complementary score sequences. The converse, however, is not true. Of the four non-isomorphic tournaments with score sequence (1, 1, 2, 3, 4, 4), two are self-complementary and the other two are complements of each other.

Sequence \underline{A345470} in the OEIS, authored by Givner in 2021, lists the number of selfcomplementary score sequences for n-vertex tournaments. Givner wrote a program that generated all length n score sequences for n ≤ 34 and then counted those that were selfcomplementary. As with Bent’s program, computer time was the limiting factor in Givner’s calculations.

Without actually generating the self-complementary score sequences, we can count them using the F_{n} arrays of Bent from Section 2.

Theorem 6. Let SCS(n) denote the number of distinct self-complementary score sequences of length n. Then for all m ≥ 1 we have

SCS(2m) = ∑_{T =\binom{m}{2}}^{m(m−1)} ∑_{E=⌈\frac{T}{m}⌉}^{m−1} F_{m} [T, E] ,

and

SCS(2m + 1) = ∑_{T =\binom{m}{2}}^{m^{2}} ∑_{E=⌈\frac{T}{m}⌉}^{m} F_{m} [T, E] .

Proof. From Definition 5 we know that a self-complementary score sequence of length 2m is determined by its first m terms. Therefore SCS(2m) is a certain sum of values in the array F_{m}. For the lower summation limit on E we note that E = s_{m} must be at least as large as the average of s_{1} through s_{m}, or \frac{T}{m}. For the upper limit on E we observe that s_{m} ≤ s_{m+1} and s_{m} + s_{m+1} = 2m − 1. This implies that E = s_{m} ≤ ⌊\frac{2m−1}{2}⌋ = m − 1. The lower summation limit on T comes from equation (2) while for the upper limit we note that T ≤ m · s_{m} ≤ m(m − 1).

For self-complementary score sequences of length 2m + 1 we have that s_{m+1} must be m, and the score sequence is again determined by its first m terms. The only difference between this case and the even case is that E = s_{m} can now be as large as s_{m+1} = m, and T can now be as large as m · s_{m} ≤ m^{2}.

We used Theorem 6 to compute SCS(n) for n from 2 to 500 as displayed in the OEIS entry \underline{A345470}, confirming the results of Givner for n from 2 to 34.

4 Counting strong score sequences

A tournament is called strong, or strongly connected, if every vertex of the tournament can reach every other vertex along a directed path. A tournament is reducible if its vertex set can be partitioned into two nonempty sets A and B with every vertex in B dominating every vertex in A. It is well known that a tournament is strong if and only if it is not reducible.

Harary and Moser [5, Theorem 9] showed that the property of being strong can be determined from a tournament’s score sequence.

Proposition 7. A tournament is strong if and only if its score sequence satisfies equations (1), (3) and

∑_{i=1}^{r} s_{i} > \binom{r}{2} for 1 ≤ r < n.  (4)

We call score sequences that satisfy equation (4) strong score sequences. For example, the seven strong score sequences for n = 6 are (1, 1, 2, 3, 4, 4), (1, 1, 3, 3, 3, 4), (1, 2, 2, 2, 4, 4), (1, 2, 2, 3, 3, 4), (1, 2, 3, 3, 3, 3), (2, 2, 2, 2, 3, 4), and (2, 2, 2, 3, 3, 3).

In this section we present two algorithms for counting strong score sequences. Our first method is a modified version of Bent’s algorithm of Section 2, using G_{n} arrays based on equation (4) instead of the F_{n} arrays based on equation (2).

Definition 8. For all positive n and all non-negative T and E, let G_{n} [T, E] be the number of sequences of length n satisfying (1), (4), s_{n} = E, and

∑_{i=1}^{n} s_{i} = T.

Proposition 9. We have

G_{1} [T, E] = \begin{cases}1, & if T = E; \\ 0, & otherwise, \end{cases}

and for n ≥ 2 we have

G_{n} [T, E] = \begin{cases}∑_{k=⌈\frac{T −E}{n−1}⌉}^{E} G_{n−1} [T −E, k], & if T −E > \binom{n−1}{2}; \\ 0, & otherwise. \end{cases}

Proof. The case n = 1 is clear: a sequence of length one gets counted if and only if its last (and only) element E is equal to the sum T of all its elements. For n ≥ 2, consider a sequence S = (s_{1}, …, s_{n}) counted by G_{n}(T, E). We have ∑_{i=1}^{r} s_{i} > \binom{r}{2} for r < n, ∑_{i=1}^{n} s_{i} = T, and s_{n} = E. If we delete the last term s_{n} we have a sequence Ŝ = (s_{1}, …, s_{n−1}) with ∑_{i=1}^{n−1} s_{i} = T −E and s_{n−1} equal to some integer k with \frac{T −E}{n−1} ≤ k ≤ E. The limits arise because s_{n−1} must be at least as large as of the average of the first n−1 terms of the sequence and no larger than s_{n}. Thus for every sequence S counted by array element G_{n} [T, E], the corresponding sequence Ŝ is counted by one of the indicated G_{n−1} [T −E, k] array elements. However, not all strings counted by these array elements satisfy the requirement that ∑_{i=1}^{n−1} s_{i} > \binom{n−1}{2}; our sum only includes those terms for which this requirement is satisfied.

Our first method for counting strong score sequences now follows.

Theorem 10. Let SS(n) denote the number of distinct strong score sequences for n-vertex tournaments. Then for n ≥ 1 we have

SS(n) = ∑_{E=⌈\frac{n−1}{2}⌉}^{n−2} G_{n} [\binom{n}{2}, E] .

Proof. By definition, G_{n} [\binom{n}{2}, E] counts strong score sequences of length n with largest score being E. This score is bounded below by the average score, and bounded above by n − 2 for strong tournaments.

Our second method for counting strong score sequences is to count reducible score sequences and subtract that number from the number of all score sequences. Every reducible tournament can be characterized by a non-empty vertex set A which induces a strong subtournament, and a nonempty set B of the remaining vertices, with every vertex in B dominating every vertex in A. The score sequence of such a tournament consists of an initial strong score sequence of length |A|, followed by an arbitrary valid score sequence of length |B| with each score increased by |A|. Some typical reducible score sequences of length 6 are (0, 2, 3, 3, 3, 4) with |A| = 1, (1, 1, 1, 3, 4, 5) with |A| = 3, (1, 1, 2, 2, 4, 5) with |A| = 4, and (1, 2, 2, 2, 3, 5) with |A| = 5. This characterization of reducible score sequences provides us with the following bootstrapping method for counting strong score sequences, using only the series S(n) that counts all score sequences.

Theorem 11. Terms in the sequence SS(n) with n ≥ 1 can be computed recursively from the sequence S(n) using the formula

SS(n) = S(n) − ∑_{i=1}^{n−1} SS(i)S(n − i).

Claesson et al. [3] observed that this method also works when using their method for computing S(n).

We computed SS(n) for n from 1 to 500 by both of these methods with identical results, as displayed in the OEIS entry \underline{A351822}.

5 Counting strong self-complementary score sequences

In this section we sketch two methods for computing the number of score sequences for nvertex tournaments that are both strong and self-complementary. The first is based on our method of counting self-complementary score sequences, but using the G_{n} arrays rather than the F_{n} arrays.

Theorem 12. Let SSCS(n) denote the number of distinct score sequences of length n that are both strong and self-complementary. Then for all m ≥ 1 we have

SSCS(2m) = ∑_{T =\binom{m}{2}+1}^{m(m−1)} ∑_{E=⌈\frac{T}{m}⌉}^{m−1} G_{m} [T, E]

and

SSCS(2m + 1) = ∑_{T =\binom{m}{2}+1}^{m^{2}} ∑_{E=⌈\frac{T}{m}⌉}^{m} G_{m} [T, E] .

Our second method for counting strong self-complementary score sequences is similar to our second method for counting strong score sequences: subtract the number of selfcomplementary reducible score sequences from the number of self-complementary score sequences. Now a self-complementary reducible score sequence of length n begins with a strong score sequence of length i with 1 ≤ i ≤ ⌊\frac{n}{2}⌋ and ends with the complement of this initial subsequence. In between we must have a self-complementary sequence of length n − 2i, with each term increased by i. For example, the three self-complementary reducible score sequences of length n = 6 are (0, 1, 2, 3, 4, 5) and (0, 2, 2, 3, 3, 5) with i = 1, and (1, 1, 1, 4, 4, 4) with i = 3. Then the sequence that counts strong self-complementary score sequences can be computed from the sequences for strong sequences and self-complementary sequences.

Theorem 13. For all n ≥ 1 we have

SSCS(n) = SCS(n) − ∑_{i=1}^{⌊ \frac{n}{2} ⌋} SS(i) SCS(n − 2i).

We observe that for n = 2m and i = m the last term in the above summation is SS(m) SCS(0). For this to be correct we must have SCS(0) = 1, i.e., we must assume the existence of a self-complementary tournament on zero vertices.

We computed SSCS(n) for n from 1 to 500 by both of these methods with identical results, as displayed in the OEIS entry \underline{A351869}.

6 Asymptotic Results and Conjectures

Moon [9] reports that Erdős and Moser, in an unpublished work, showed that there exist constants c_{1} and c_{2} such that

\frac{c_{1} · 4^{n}}{n^{9/2}} < S(n) < \frac{c_{2} · 4^{n}}{n^{3/2}} .

Winston and Kleitman [12] improved these bounds, showing that

\frac{c_{1} · 4^{n}}{n^{5/2}} < S(n) < \frac{c_{2} · 4^{n}}{n^{2}}

and conjecturing that

S(n) = Θ (\frac{4^{n}}{n^{5/2}} ) .

This conjecture was confirmed by Kim and Pittel [6]. Vaclav Kotesovec asserts in the OEIS entry \underline{A000571} that

S(n) ∼ \frac{c · 4^{n}}{n^{5/2}} ,

with c = 0.392478 …, but with no apparent proof.

For strong score sequences, Kotesovec asserts in \underline{A351822} that

SS(n) ∼ \frac{c · 4^{n}}{n^{5/2}} ,

with c = 0.202756 …. It would be nice to at least have a proof of the order of magnitude of SS(n). Assuming that the assertions of Kotesovec are correct, we have that slightly more than half of all tournament score sequences are strong.

As for self-complementary score sequences, we conjecture that both

SCS(n) = Θ (\frac{2^{n}}{n^{3/4}} ) and SSCS(n) = Θ (\frac{2^{n}}{n^{3/4}} ) .

We have no theoretical evidence for these formulas, but they are consistent with the data available. Results suggest that over seventy percent of all self-complementary score sequences are strong.

References

[1] G. G. Alway, The distribution of the number of circular triads in paired comparisons, Biometrika 49 (1962), 265–269.

[2] Dale H. Bent, Score problems of round-robin tournaments, Master’s thesis, Univ. Alberta, 1964.

[3] A. Claesson, M. Dukes, A. F. Franklín, and S. Ö. Stefánsson, Counting tournament score sequences, preprint, 2023. Available at https://arxiv.org/abs/2209.03925.

[4] H. A. David, Tournaments and paired comparisons, Biometrika 46 (1959), 139–149.

[5] Frank Harary and Leo Moser, The theory of round robin tournaments, Amer. Math. Monthly 73 (1966), 231–246.

[6] Jeong Han Kim and Boris Pittel, Confirming the Kleitman-Winston conjecture on the largest coefficient in a q-Catalan number, J. Combin. Theory Ser. A 92 (2000), 197–206.

[7] H. G. Landau, On dominance relations, and the structure of animal societies. III. The condition for a score structure, Bull. Math. Biophys. 15 (1953), 143–148.

[8] P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Math. 49 (1920), 1–36. Reprinted in Percy Alexander MacMahon Collected Papers, Volume I, George E. Andrews, ed., MIT Press, 1978.

[9] John W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, 1968.

[10] T. V. Narayana and D. H. Bent, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull. 7 (1964), 133–136.

[11] OEIS Foundation, Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org, 2023.

[12] Kenneth J. Winston and Daniel J. Kleitman, On the asymptotic number of tournament score sequences, J. Combin. Theory Ser. A 35 (1983), 208–230.

2020 Mathematics Subject Classification: Primary 05C30; Secondary 05A17, 05C20.

Keywords: tournament, score sequence, strong, self-complementary.

(Concerned with sequences \underline{A000571}, \underline{A345470}, \underline{A351822}, and \underline{A351869}.)

Received July 20 2022; revised versions received July 21 2022; May 28 2023; May 29 2023. Published in Journal of Integer Sequences, May 29 2023.

Return to Journal of Integer Sequences home page.