# Homework Help: For a round-robin of n teams find the number of different outcomes

1. Sep 12, 2017

### Potatochip911

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
Combinations: $\frac{n!}{r!(n-r)!}$

3. 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!

2. Sep 13, 2017

### haruspex

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.

3. Sep 13, 2017

### Ray Vickson

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

4. Sep 13, 2017

### Orodruin

Staff Emeritus
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).

5. Sep 13, 2017

### Ray Vickson

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| ?

6. Sep 13, 2017

### Orodruin

Staff Emeritus
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!)

Last edited: Sep 13, 2017
7. Sep 13, 2017

### Ray Vickson

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

8. Sep 13, 2017

### Potatochip911

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).

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

9. Sep 13, 2017

### 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 Nn. I can show that the number in which either one team beats all the others or one team loses to all the others is 2Nn-1-Nn-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. N5=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.

10. Sep 14, 2017

### Potatochip911

Yikes.
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.

11. Sep 14, 2017

### haruspex

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

12. Sep 14, 2017

### Potatochip911

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 :
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.

13. Sep 15, 2017

### haruspex

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+1th team, there are 2n possibilities for that team. Eliminate duplicates and continue to n+2.

14. Sep 18, 2017

### haruspex

Consider a sequence A=(a1, a2, ... , an), 0<=a1<a2<...<an.
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
an<n
Proof, exercise.

Define B=(b1, ... bn-1) by
bi=ai for i <= an
bi=ai-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 nth team which beats the first an and loses to the rest results in the outcome A.

Proof, exercise.

15. Sep 19, 2017

### Potatochip911

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.

16. Sep 19, 2017

### haruspex

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

17. Sep 19, 2017

### Potatochip911

Ok that makes more sense

18. Sep 19, 2017

### haruspex

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

19. Sep 19, 2017

### Potatochip911

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

20. Sep 19, 2017

### haruspex

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