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

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

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 $tex_9bf82472bd2decfceb6b8e2762101739 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$.

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 $tex_6e99eb1b55e376d97dcfea934131fb93 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

Picking 0 out of N is 1 aka $tex_f3c5f037b8271308fc7946b386c81262 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$
Picking N out of N is 1 aka $tex_58394739577c81a8da3d5005f4f72d66 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$
Picking M out of N when M is greater than N is 0 aka $tex_6968974bc5450970d9441d10a8d30b25 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$ when $tex_52f06fcff8c7609f0e7d5cce7e88bcdb Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$ 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:

$tex_8c3de51df4985a9a66a59ab13e1e5b8f Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

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:

$tex_f33a65a4bd1f46366a7f7ff7b8c9b2a3 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

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.

$tex_133b7f25ac11931919f2673f8666a346 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

$tex_b72dd5dc1cb5393653d793b262d64516 Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

Thus:

$tex_c3e2cbe5cf890e5192f49adf1c7b415e Teaching Kids Programming - How Many Games are Played in World Cup (Combinatorics and Permutations) algorithms Dynamic Programming math Memoization python teaching kids programming youtube video$

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)]```

GD Star Rating