Oplossing AchterOPgave 62-3

Bij $n - 1, n \ge 2$ ploegen en de regel dat verliezers zonder meer afvallen, volstaat een schema met $n−2$ partijen om tot een winnaar te komen. Er kan op $2n - 3$ manieren een $n^e$ ploeg worden toegevoegd aan een bestaand schema voor $n - 1$ ploegen:

  • De $n^e$ ploeg speelt tegen de winnaar van de $n - 1$ ploegen. Dit is $1$ mogelijkheid.
  • De $n^e$ ploeg speelt tegen één van beide ploegen uit één van de $n - 2$ partijen uit het schema voor $n - 1$ ploegen, en de winnaar daarvan speelt tegen de andere ploeg uit die ene partij. Hiervoor zijn er $2(n - 2)$ mogelijkheden.

Dus voor het aantal mogelijke schema’s $s(n)$ voor $n \ge 3$ ploegen geldt recursief:

$$s(n) = (2n - 3) \cdot s(n - 1), s(2) = 1.$$

Hieruit volgt dat $s(n)$ het product is van de eerste $n-1$ oneven getallen $1, 3, 5, 7, \dots , 2n - 3$:

$$s(n) =\prod_{k=2}^{n}\left(2k-3\right)=\prod_{k=1}^{n-1}\left(2k-1\right).$$

Voor $9$ partijen voor $10$ ploegen zijn er $s(10) = 1 \cdot 3 \cdot 5 \cdot \cdots \cdot 17 = 34\,459\,425$ verschillende schema’s.