Combinatorics Review

Introduction

Combinatorics is the mathematics of counting. While this might sound simple, counting becomes remarkably complex when dealing with large sets of objects with various constraints. In probability theory, combinatorics provides the tools to calculate the number of favorable outcomes and total outcomes needed for probability computations.

Why This Matters for ML: Combinatorics appears throughout machine learning - from calculating the number of possible model configurations in hyperparameter tuning, to understanding the complexity of search spaces, to computing probabilities in discrete distributions.

Fundamental Counting Principle

The Fundamental Counting Principle (also called the multiplication principle) states: If one event can occur in m ways and another independent event can occur in n ways, then both events can occur in m × n ways.

Example: Password Combinations

A password consists of 3 lowercase letters followed by 2 digits. How many possible passwords are there?

• 26 choices for each letter (a-z)
• 10 choices for each digit (0-9)
• Total: $26 \times 26 \times 26 \times 10 \times 10 = 1,757,600$

Permutations

A permutation is an arrangement of objects where order matters. The number of permutations of n distinct objects taken r at a time is:

Where $n! = n \times (n-1) \times \cdots \times 2 \times 1$ is the factorial function, with $0! = 1$ by definition.

Special Cases

Permutations with Identical Objects

When some objects are identical, we divide by the factorial of the count of each repeated element:

Combinations

A combination is a selection of objects where order does not matter. The number of combinations of n objects taken r at a time is:

The notation $\binom{n}{r}$ is read as "n choose r" and represents the binomial coefficient.

Key Properties

1. Symmetry: $\binom{n}{r} = \binom{n}{n-r}$
2. Pascal's Identity: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$
3. Boundary: $\binom{n}{0} = \binom{n}{n} = 1$
4. Sum: $\sum_{r=0}^{n} \binom{n}{r} = 2^n$

Example: Choosing 3 team members from 10 candidates:$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Stars and Bars

The stars and bars technique counts ways to distribute identical objects into distinct groups. If we have n identical objects to distribute into k distinct bins:

Example: Distributing Items

Distribute 10 identical candies among 4 children. We need k-1 = 3 dividers among n + k - 1 = 13 positions:

Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle counts elements in the union of sets by adding individual sets, then subtracting pairwise intersections, adding triple intersections, and so on:

For three sets:

General Formula

Python Implementation

Python provides built-in tools for combinatorial calculations:

1import math
2from itertools import permutations, combinations
3
4# Factorial
5print(f"5! = {math.factorial(5)}")  # 120
6
7# Permutations: P(n, r)
8def P(n, r):
9    return math.factorial(n) // math.factorial(n - r)
10
11print(f"P(5, 3) = {P(5, 3)}")  # 60
12
13# Combinations: C(n, r)
14def C(n, r):
15    return math.comb(n, r)  # Python 3.8+
16
17print(f"C(10, 3) = {C(10, 3)}")  # 120
18
19# Generate all permutations
20items = ['A', 'B', 'C']
21perms = list(permutations(items, 2))
22print(f"Permutations of 2 from {items}: {perms}")
23# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
24
25# Generate all combinations
26combs = list(combinations(items, 2))
27print(f"Combinations of 2 from {items}: {combs}")
28# [('A', 'B'), ('A', 'C'), ('B', 'C')]

Permutations with Repetition

1from collections import Counter
2import math
3
4def permutations_with_repetition(word):
5    """Count permutations of a word with repeated letters."""
6    counts = Counter(word)
7    n = len(word)
8    denominator = 1
9    for count in counts.values():
10        denominator *= math.factorial(count)
11    return math.factorial(n) // denominator
12
13# Example: MISSISSIPPI
14word = "MISSISSIPPI"
15result = permutations_with_repetition(word)
16print(f"Permutations of {word}: {result}")  # 34650
17
18# Verify letter counts
19print(f"Letter counts: {dict(Counter(word))}")
20# {'M': 1, 'I': 4, 'S': 4, 'P': 2}

Stars and Bars Implementation

1import math
2
3def distribute(n_items, n_bins):
4    """Count ways to distribute n identical items into k distinct bins."""
5    return math.comb(n_items + n_bins - 1, n_bins - 1)
6
7# 10 candies among 4 children
8print(f"Ways to distribute 10 candies to 4 children: {distribute(10, 4)}")  # 286
9
10# Generate one possible distribution
11def generate_distributions(n_items, n_bins, max_per_bin=None):
12    """Generate all possible distributions."""
13    if n_bins == 1:
14        if max_per_bin is None or n_items <= max_per_bin:
15            yield [n_items]
16        return
17
18    max_first = n_items if max_per_bin is None else min(n_items, max_per_bin)
19    for first in range(max_first + 1):
20        for rest in generate_distributions(n_items - first, n_bins - 1, max_per_bin):
21            yield [first] + rest
22
23# Example: 5 items into 3 bins
24distributions = list(generate_distributions(5, 3))
25print(f"5 items into 3 bins: {len(distributions)} ways")
26print(f"First 5 distributions: {distributions[:5]}")

Summary

This section covered the essential combinatorial tools for probability calculations:

• Permutations count arrangements where order matters
• Combinations count selections where order does not matter
• Stars and Bars counts distributions of identical items
• Inclusion-Exclusion handles counting with overlaps

In the next section, we'll review the calculus concepts essential for working with continuous probability distributions.