For a round-robin of n teams find the number of different outcomes

[Potatochip911]

Homework Statement

In a round-robin tournament each team plays every other team once, find the number of different outcomes possible for $n$ teams.

e.g. for 4 teams the possible outcomes are:
|3-0 | 3-0 | 2-1 | 2-1
| 2-1 | 1-2 | 2-1 | 2-1
| 1-2 | 1-2 | 1-2 | 2-1
| 0-3 | 1-2 | 1-2 | 0-3

so there are 4 possible outcomes.

Homework Equations

Combinations: $\frac{n!}{r!(n-r)!}$

The Attempt at a Solution

I don't know much about how to solve this question so I will just list what I do know. $n(n-1)/2$ games will take place, this gives $2^{n(n-1)/2}$ possible outcomes for the games. The total number of wins must always be equal to $(n-1)(n-2)/2$ so if it's useful the question can be turned into how many unique ways can you create $(n-1)(n-2)/2$ from $n$ digits using the digit $(n-1)$ at most once since only one team could theoretically go flawless and digits ranging from $0\leq d < n$. Unfortunately I'm terrible at combinatorics so I really have no clue how to approach solving this.

For 2 teams:
1-0 |
0-1 |
For 3 teams:
2-0 | 1-1
1-1 | 1-1
0-2 | 1-1

If someone could point me in the right direction that would help a lot!

 

[haruspex]

the number of different outcomes

It depends what you consider to be different outcomes. Do we care about exactly which team beat which, or only how many games each won?
I assume there are no draws.

 

[Ray Vickson]

Homework Statement

In a round-robin tournament each team plays every other team once, find the number of different outcomes possible for $n$ teams.

e.g. for 4 teams the possible outcomes are:
|3-0 | 3-0 | 2-1 | 2-1
| 2-1 | 1-2 | 2-1 | 2-1
| 1-2 | 1-2 | 1-2 | 2-1
| 0-3 | 1-2 | 1-2 | 0-3

so there are 4 possible outcomes.

Homework Equations

Combinations: $\frac{n!}{r!(n-r)!}$

The Attempt at a Solution

I don't know much about how to solve this question so I will just list what I do know. $n(n-1)/2$ games will take place, this gives $2^{n(n-1)/2}$ possible outcomes for the games. The total number of wins must always be equal to $(n-1)(n-2)/2$ so if it's useful the question can be turned into how many unique ways can you create $(n-1)(n-2)/2$ from $n$ digits using the digit $(n-1)$ at most once since only one team could theoretically go flawless and digits ranging from $0\leq d < n$. Unfortunately I'm terrible at combinatorics so I really have no clue how to approach solving this.

For 2 teams:
1-0 |
0-1 |
For 3 teams:
2-0 | 1-1
1-1 | 1-1
0-2 | 1-1

If someone could point me in the right direction that would help a lot!

Please explain your notation: what does |3-0 | 3-0 | 2-1 | 2-1 mean in the first line of your first table?

 

[Orodruin]

Please explain your notation: what does |3-0 | 3-0 | 2-1 | 2-1 mean in the first line of your first table?

I believe they are intended to be grouped in columns rather than rows and each entry representing the number of wins and losses for a team. The first column would be the possibility with one team winning all three games (3-0), the second team winning two games (2-1), the third team winning one game (1-2), and the last team losing all games (0-3).

 

[Ray Vickson]

I believe they are intended to be grouped in columns rather than rows and each entry representing the number of wins and losses for a team. The first column would be the possibility with one team winning all three games (3-0), the second team winning two games (2-1), the third team winning one game (1-2), and the last team losing all games (0-3).

OK, so would the first column be listing the wins for Team A? Would the second column list the wins for Team B? If so, what could be meant by the fact that its three entries are |3-0|, |1-2|, |1-2|, |1-2| ?

 

[Orodruin]

OK, so would the first column be listing the wins for Team A?

No, the first row seems to be listing the wins for the team with the most wins, not necessarily a specific team. Every column is a different realisation.

Consider the outcome table (team names made up):
Physicists 3W-0L
Chemists 1W-2L
Biologists 1W-2L
Geologists 1W-2L
which is a possible outcome. This would be represented as the column
3-0
1-2
1-2
1-2
and is one of the listed outcomes - the second one (the OP seems to suggest that the team order does not matter, although in the case of those team names it obviously does as the 3-0 in the first entry is obvious and excludes two outcomes!)

 

[Ray Vickson]

No, the first row seems to be listing the wins for the team with the most wins, not necessarily a specific team. Every column is a different realisation.

Consider the outcome table (team names made up):
Physicists 3W-0L
Chemists 1W-2L
Biologists 1W-2L
Geologists 1W-2L
which is a possible outcome. This would be represented as the column
3-1
1-2
1-2
1-2
and is one of the listed outcomes - the second one (the OP seems to suggest that the team order does not matter, although in the case of those team names it obviously does!)

Thanks: that clarifies it. I wish the OP had gotten back here with the explanation.

 

[Potatochip911]

It depends what you consider to be different outcomes. Do we care about exactly which team beat which, or only how many games each won?
I assume there are no draws.

Yep there are no draws.

We only care about the overall result and not which team beat which.
E.g. Team A:(1-0) and Team B:(0-1) is the same as Team A:(0-1) and Team B:(1-0).

Thanks: that clarifies it. I wish the OP had gotten back here with the explanation.

Yes the way Orodruin explained it is correct. Hopefully my reply to Haruspex clarifies any confusion about order.

 

[haruspex]

This does seem to be a hard problem, perhaps on a par with finding the partition numbers.
Let the number of outcomes for n teams be N_n. I can show that the number in which either one team beats all the others or one team loses to all the others is 2N_n-1-N_n-2.
For n=5, that leaves just three other patterns: 3 3 2 1 1, 3 2 2 2 1, 2 2 2 2 2. N₅=2.4-2+3=9.
Likewise, for n=6, if all scores are from 1 to 4 then all 9 partitions of 15 into the 6 scores within that constraint appear to be valid. This gives 2.9-4+9=23.
At n=7 further constraints arise since, e.g., no subset of four teams can have a score line 2 1 1 1.

 

[Potatochip911]

This does seem to be a hard problem, perhaps on a par with finding the partition numbers.

Yikes.

Let the number of outcomes for n teams be N_n. I can show that the number in which either one team beats all the others or one team loses to all the others is 2N_n-1-N_n-2.
For n=5, that leaves just three other patterns: 3 3 2 1 1, 3 2 2 2 1, 2 2 2 2 2. N₅=2.4-2+3=9.
Likewise, for n=6, if all scores are from 1 to 4 then all 9 partitions of 15 into the 6 scores within that constraint appear to be valid. This gives 2.9-4+9=23.
At n=7 further constraints arise since, e.g., no subset of four teams can have a score line 2 1 1 1.

Just to make sure I'm understanding this correctly, we are solving for the cases in which one team beats all the others or one team loses to all the others in order to remove sums involving a 0 as one of the digits which then allows us to sum that with the partitions of n(n-1)/2 that have n scores in order to get the total number of outcomes? It appears as though the mathematical solution to this problem is quite over my head so I will try to come up with a somewhat brute-force algorithm tomorrow after I wake up.

 

[haruspex]

in order to remove sums involving a 0 as one of the digits

and those involving n-1.

which then allows us to sum that with the partitions of n(n-1)/2 that have n scores in order to get the total number of outcomes?

Those partitions in which all lie in the range 1 to n-2. But as I posted, that counts too many for n>6.

 

[Potatochip911]

and those involving n-1.

Whoops forgot about that.

Those partitions in which all lie in the range 1 to n-2. But as I posted, that counts too many for n>6.

For some reason I thought I would be able to avoid the constraints when coding an algorithm, clearly this is not the case. I took this code for the unique partitions of an integer and implemented some basic checks to see if the current partition could be a potential outcome however I am struggling to identify the last outcome in which one team beats all the others or one team loses to all the others for n = 5 (probably more problems arising with larger n). Here is my code so far.

Output for n = 5 :

Spoiler

10
9 1
8 2
8 1 1
7 3
7 2 1
7 1 1 1
6 4
6 3 1
6 2 2
6 2 1 1
6 1 1 1 1
5 5
5 4 1
5 3 2
5 3 1 1
5 2 2 1
5 2 1 1 1
4 4 2
4 4 1 1
4 3 3 <- Added outcome
4 3 2 1 <- Added outcome
4 2 2 2 <- Added outcome
3 3 3 1 <- Added outcome
3 3 2 2 <- Added outcome
3 3 2 1 1 <- Added outcome
3 2 2 2 1 <- Added outcome
2 2 2 2 2 <- Added outcome
Number of unique outcomes:8

I suppose I could bypass this problem by using your recurrence relation however I haven't been able to successfully derive it yet so I opted out of using it for now. Another thing I don't understand is how you got the constraint that for n=7 that the subset 2 2 2 1 is invalid, I understand why it's invalid since it leads to the outcome 5 5 4 2 2 2 1 which after drawing a picture I was unable to create a valid diagram for. However, I have no clue how you noticed this subset leads to problems.

 

[haruspex]

I don't understand is how you got the constraint that for n=7 that the subset 2 2 2 1 is invalid

Neither do I. I think I must have meant 2 1 1 1.

For an algorithm to generate solutions, I suggest building it up from just two teams. When you add the n+1^th team, there are 2ⁿ possibilities for that team. Eliminate duplicates and continue to n+2.

 

[haruspex]

Consider a sequence A=(a₁, a₂, ... , a_n), 0<=a₁<a₂<...<a_n.
Say A supports a tournament if the sequence represents a feasible outcome of an all-play-all tournament.
Theorem: A suports a tournament if and only if these two conditions are met:

1. $\Sigma_{i=1}^na_i=\frac 12n(n-1)$
2. For every r, $\Sigma_{i=1}^ra_i>=\frac 12r(r-1)$

That the conditions are necessary is trivial. It remains to prove they suffice.
Suppose A satisfies the conditions.
Result is trivially true for n=2.

Lemma
a_n<n
Proof, exercise.

Define B=(b₁, ... b_n-1) by
b_i=a_i for i <= a_n
b_i=a_i-1 otherwise.

Lemma
B satisfies the conditions.
Proof: exercise.

By induction, B supports a tournament.

Lemma
If a tournament between n-1 teams produces the outcome B, adding an n^th team which beats the first a_n and loses to the rest results in the outcome A.

Proof, exercise.

 

[Potatochip911]

Consider a sequence A=(a₁, a₂, ... , a_n), 0<=a₁<a₂<...<a_n.
Say A supports a tournament if the sequence represents a feasible outcome of an all-play-all tournament.
Theorem: A suports a tournament if and only if these two conditions are met:

1. $\Sigma_{i=1}^na_i=\frac 12n(n-1)$
2. For every r, $\Sigma_{i=1}^ra_i>=\frac 12r(r-1)$

That the conditions are necessary is trivial. It remains to prove they suffice.
Suppose A satisfies the conditions.
Result is trivially true for n=2.

Lemma
a_n<n
Proof, exercise.

Im a bit confused as to why we've defined $a_i < a_{i+1}$ instead of $a_i \leq a_{i+1}$ since this doesn't have to hold for tournaments in general.

Proof: Consider the series $A=a_1+a_2+\cdots +a_n$ with $0\leq a_1<a_2<\cdots < a_n$ then $\sum a_i=\frac12n(n-1)=0+1+\cdots+(n-1)$ then one cannot redistribute a 1 to $a_n$ from an $a_i, 0\leq i \leq n - 1$ without setting $a_1 \leq 0$ or removing the property of $a_i < a_{i+1}$ for $0\leq i \leq n - 1$.

I got a C+ in introductory analysis and never took more proof-related classes after that so this proof is probably pretty bad lol.

 

[haruspex]

Im a bit confused as to why we've defined a_i<a_i+1

Typo on my part. They should all have been <=.

 

[Potatochip911]

Typo on my part. They should all have been <=.

Ok that makes more sense

 

[haruspex]

Consider the series $A=a_1+a_2+\cdots +a_n$

I don't nderstand why you are summing them. I wrote that A is the sequence (a₁,...,a_n), these being the score totals (1 for a win, 0 for a loss) of the n teams, from lowest to highest.

 

[Potatochip911]

I don't nderstand why you are summing them. I wrote that A is the sequence (a₁,...,a_n), these being the score totals (1 for a win, 0 for a loss) of the n teams, from lowest to highest.

Yes I suppose that doesn't make sense after how you've defined it.

 

[haruspex]

Yes I suppose that doesn't make sense after how you've defined it.

Oh, sorry, I see you are checking off the first criterion. You confused me by calling the series A.

 

[Potatochip911]

Oh, sorry, I see you are checking off the first criterion. You confused me by calling the series A.

Oh, I believe I need to rewrite the proof anywayssince it relied on $a_i < a_{i+1}$

 

[haruspex]

... but I still do not understand the rest of what you wrote in post #15. It would help if you would state what you are trying to prove at each stage.