Teaching Kids Programming – How Many Games are Played in World Cup (Combinatorics and Permutations)

Teaching Kids Programming: Videos on Data Structures and Algorithms

How Many Matches are played during Worldcup?

There are 32 teams, allocated to 8 Groups of Four. In The Group Stages, there are 6 matches each which is .

Half of 32 = 16 qualifies (top 2 in the groups) to knock-out stages. Each knock-out elinimates one team, so 15 matches = 15 teams elinimated. Plus, there is one more match between third and fourth place.

Therefore: 8×6+15+1 = 64 matches.

Next worldcup has 48 teams – and thus total matches played 12×6+23+1=96. 12=groups,6=matches played in group stages. 23=knock-out, 1=3 vs 4.

Combinatorics

Choosing M out of N times (the order does not matter) can be noted as

Picking 0 out of N is 1 aka
Picking N out of N is 1 aka
Picking M out of N when M is greater than N is 0 aka when where we want to pick M items out of N:

For the first item, we can pick or skip.

When pick, we have M-1 items to pick from N-1 items.
When skip, we have M items to pick from N-1 items.

Thus:

We can implement this via Recursion with Memoization aka Top Down Dynamic Programming:

1
2
3
4
5
6
7
8

from collections import *
@cache # or @lru_cache(maxsize=None)
def C(N, M):
    if M == N or M == 0:
        return 1
    if M > N:
        return 0
    return C(N-1, M) + C(N-1, M-1)

from collections import *
@cache # or @lru_cache(maxsize=None)
def C(N, M):
    if M == N or M == 0:
        return 1
    if M > N:
        return 0
    return C(N-1, M) + C(N-1, M-1)

This is basically solving the Pascal triangle where each number is the sum of two numbers on the shoulder, the border numbers are all ones. We can also solve this via Iterative/Loop – where we use arrays (space can be optimised to one dimension) to store the previous Combination Numbers.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

The Combination Number can also be computed via the following equation:

In Python, we can compute the combination number using the comb function (N, M) in the math library/package:

1
2
3

from math import comb
 
print(comb(4, 2)) # prints 6

from math import comb

print(comb(4, 2)) # prints 6

We can use the combinations from the itertools to obtain the combinations aka the function has the signature: combinations(iterator, number to pick)

1
2
3
4

from itertools import combinations
 
print(list(combinations((1,2,3), 2)))
# [(1, 2), (1, 3), (2, 3)]

from itertools import combinations

print(list(combinations((1,2,3), 2)))
# [(1, 2), (1, 3), (2, 3)]

Permutations

For permutations, the order of the items matters, for example, (1, 2) is different than (2, 1). We can take permutations as P(N, M) which is equal to C(N, M) and do full permutations on M items aka P(M, M)

Full permutations of N items is N factorial. The first item we have N choices, the second item we have N-1 choices and so on, the last item we have 1 choices.

Thus:

In Python, we can compute the permutations number using the perm function (N, M) in the math library/package:

1
2
3

from math import perm
 
print(perm(4, 2)) # prints 12

from math import perm

print(perm(4, 2)) # prints 12

We can use the permutations from the itertools to obtain the permutations aka the function has the signature: permutations(iterator, number to pick)

1
2
3
4

from itertools import permutations
 
print(list(permutations((1,2,3), 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

from itertools import permutations

print(list(permutations((1,2,3), 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

–EOF (The Ultimate Computing & Technology Blog) —