My notes about combinatorics (binomial coefficent, permutations and cominations).

Kaggle: https://www.kaggle.com/code/michelesalvucci/combinatorics-with-python.

Binomial coefficient

The number of ways to choose \(r\) objects from \(n\) objects without regard to order.

\[ \binom{n}{r}=\frac{n!}{r!(n-r)!}\]

Championship example: 20 teams challange each other 2 by 2.

import scipy.special
import numpy as np
import itertools
from pprint import pprint
import math

binomial_coeff = int(scipy.special.binom(20, 2))

# Multiply by 2 because of the round trip
test_championship_matches = 19*10*2

print(binomial_coeff * 2, test_championship_matches)
assert binomial_coeff * 2 == test_championship_matches

# Direct calculation of binomial coefficient
def custom_binom(n:int, k:int) -> int:
    return int(math.factorial(n) / (math.factorial(k) * math.factorial(n-k)))

print(custom_binom(20, 2))
print(int(math.factorial(20) / (math.factorial(2) * math.factorial(20-2))))

# All the matches through itertools.permutations
teams = [
    'Juve', 'Milan', 'Inter', 'Roma', 'Lazio',
    'Fiorentina', 'Sampdoria', 'Genoa', 'Torino', 'Atalanta',
    'Sassuolo', 'Udinese', 'Cagliari', 'Bologna', 'Parma',
    'Salernitana', 'Chievo', 'Lecce', 'Palermo', 'Napoli'
]
matches = list(itertools.permutations(teams, 2))
print(matches[:10], "...")
print(len(matches))

380 380
190
190
[('Juve', 'Milan'), ('Juve', 'Inter'), ('Juve', 'Roma'), ('Juve', 'Lazio'), ('Juve', 'Fiorentina'), ('Juve', 'Sampdoria'), ('Juve', 'Genoa'), ('Juve', 'Torino'), ('Juve', 'Atalanta'), ('Juve', 'Sassuolo')] ...
380

Permutations

Simple permutation

An arrangement of objects in a specific order.

Example: Arranging A, B, and C as ABC or BAC are different permutations.

arr = np.array(['h', 'e', 'l', 'o'], dtype='S')

# How many simple permutations?
print(math.factorial(arr.shape[0]))

# How many circular permutations?
print(math.factorial(arr.shape[0] - 1))

# Permutations through itertools
print(len(list(itertools.permutations(['h', 'e', 'l', 'o']))))

24
6
24

Permutations with repetition

Arrangements where some objects are repeated, and the repeated objects are considered identical.

\[ \frac{n!}{n_1!n_2!\cdots n_k!}\]

Example: the number of arrangements of AAB is

\[ \frac{3!}{2!}=3\]

So the arrangements are AAB, ABA, BAA.

example_word = 'halloween'
example_word_lst = list(example_word)

arr = np.array(example_word_lst, dtype='S')
num = math.factorial(arr.shape[0])
unique, counts = np.unique(arr, return_counts=True)
print("Counts", counts)

# Calculate factorial for each count to find out denominator
ufunc = np.vectorize(lambda count: math.factorial(count))
counts = ufunc(counts)
print("Counts factorials", counts)

denom = np.multiply.reduce(counts)
result = int(num/denom)
print("Result:", result)

Counts [1 2 1 2 1 1 1]
Counts factorials [1 2 1 2 1 1 1]
Result: 90720

Combinations

# Combination of class 3 of a 4-len array
example_word = 'aiuo'
example_word_lst = list(example_word)
combs = list(itertools.combinations(example_word_lst, 3))
print(combs)

assert len(combs) == 4

# Combination of class 3 of a 2-len array
example_word = 'st'
example_word_lst = list(example_word)
combs = list(itertools.combinations_with_replacement(example_word_lst, 3))
print(combs)

assert len(combs) == 4

[('a', 'i', 'u'), ('a', 'i', 'o'), ('a', 'u', 'o'), ('i', 'u', 'o')]
[('s', 's', 's'), ('s', 's', 't'), ('s', 't', 't'), ('t', 't', 't')]

Example of a simple problem with permutations

8 friends meet weekly for a dinner, changing every time their seat at the table. Supposing that seats are numbered, after how many years they will run out of every possible disposition?

The starting set is formed by \(n=8\) elements and each seat at the table is a group of \(k=8\) elements.

Order is fundamental, indeed each seat at the table differs from the others right for the order the friends take places.

\(k=n\) and the elements are distinct (no repetitions), therefore each table seat is a simple permutation of 8.

math.factorial(8)

40320

There are 40.320 possible ways of disposing seats at the table.

To calculate how many years they will take to run out of every possible disposition it's enough to divide the number of possible dispositions by the number of weeks in a year, that are about \(52\).

round(math.factorial(8) / 52, 2)

775.38

They will take about 775 years.