Arrangements and Combinations · Combinations

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

If each of the \(n\) teams played once with every other team, then the total number of games was \(\frac{n(n-1)}{2}\). Let us consider two proofs.

Combinatorial. Each game is determined by two teams. There are \(n\) ways to choose the first team and \((n-1)\) ways to choose the second team. With this counting method, the game between teams \(i\) and \(j\) is counted twice: once as game \(ij\) and once as game \(ji\).
```
from itertools import combinations

for c in combinations('abcdefgh', 2):
    print(*c, sep='')
```
```
ab
ac
ad
ae
af
ag
ah
bc
bd
be
bf
bg
bh
cd
ce
cf
cg
ch
de
df
dg
dh
ef
eg
eh
fg
fh
gh
```

Recursive. Let \(T(n)\) be the number of games. Then team \(n\) played exactly \(n-1\) games, and all other teams must play among themselves. Thus, \(T(n)=n-1+T(n-1)\). This recurrence relation can be unfolded step by step: \[\begin{align*}T(n)&=(n-1)+T(n-1)=\\&=(n-1)+(n-2)+T(n-2)=\\&=(n-1)+(n-2)+(n-3)+T(n-3)=\\&=\dotsb=\\&=(n-1)+(n-2)+\dotsb+1\end{align*}\] According to the formula for the sum of an arithmetic progression, this equals \(\frac{n(n-1)}{2}\).
```
def number_of_games(n):
    return 0 if n <= 1 else (n - 1) + number_of_games(n - 1)


print(number_of_games(8))
```
```
28
```