games in a round-robin tournament

How many games are played in a round-robin tournament held with n tennis players where each of the players will play against every other player exactly once.

The answer is $\frac{n(n-1)}{2}$. What is wrong with thinking about it this way...

We can line up people in some order $n!$and then say the first two are a pair, the next two are a pair...etc. This over counts by a factor of $\frac{n}{2}! \cdot 2^\frac{n}{2}$ since the order of the pairs doesn't matter, and the order within the pairs doesn't matter.

$$\frac{n!}{\frac{n}{2}! \cdot 2^\frac{n}{2}}$$

The question asks about the number of games over all the rounds, while your proposed answer gives the number of ways to split the players into pairs for one round. They are different questions with different answers. Your answer is fine for the question you are addressing.

• Ah, so my proposed would describe the number of possible arrangement of pairs\schedules for one round? – larrysummersstatistics Nov 29 '14 at 1:38
• That is correct. – Ross Millikan Nov 29 '14 at 15:11

This is actually a graph theory problem. Construct a simple graph with each player as a vertex. Each vertex has degree $n-1$, as each player goes up against every other player. So there are $n-1$ other players. So by the handshake lemma, $n$ vertices times $(n-1)$ edges per vertex gives us $n(n-1)$. We have double counted edges though, so we divide out by $2$. That is, if we count the edge $\{p_{1}, p_{2}\}$ on player $p_{1}$, we have also counted it on $p_{2}$.

Combinatorially, we have $n$ players and we look at the number of ways we can pair folks up. So we have $\binom{n}{2}$. So this counts $\{ \{p_{i}, p_{j}\} : i, j \in V, i \neq j \}$.

Notice here that ordering doesn't matter. We don't care when two players compete against each other, just that they do. So this isn't a permutation problem. Hence, why your count is wrong.

Edit: We are counting the two element subsets of the players. Notice each such subset is a game. So we choose the first player. There are $n$ such ways to do this. Then there are $n-1$ ways to choose the second player. By rule of product, we multiply to get n(n-1). Since $\{a, b\} = \{b, a\}$, so we have double counted and divide out by two. Notice that $n(n-1)$ assumes ordering, so $(a,b) \neq (b, a)$.

Does this make more sense?

• I don't have any knowledge of graph theory.. is there a way to explain way my thinking is wrong without graph theory? In my mind they are counting the same thing.. how many unique 'pairs' can we form from n but obviously they have very different results. – larrysummersstatistics Nov 28 '14 at 22:30
• I've updated. Let me know if this is clearer. – ml0105 Nov 28 '14 at 23:50
• This is not a reply to the original answer, since in his calculation order is not relevant either. – arovai Nov 29 '14 at 0:30