Combinatorics

ℹ️ Why It Matters

Combinatorics is the mathematics of counting, arranging, and structuring discrete objects. It underpins algorithm analysis, probability theory, cryptography, and complexity theory. From determining the number of possible passwords to analyzing the worst-case runtime of sorting algorithms, combinatorics provides the essential tools for quantifying discrete possibilities. Every time you wonder "how many ways can this happen?", you are doing combinatorics.

Counting Principles

ThProduct Rule (Multiplication Principle)

If a task consists of $k$ independent stages, where stage $i$ has $n_i$ possible outcomes, then the total number of outcomes for the entire task is:

n_1 \times n_2 \times \cdots \times n_k

Example: A license plate has 2 letters followed by 4 digits. There are $26 \times 26 \times 10 \times 10 \times 10 \times 10 = 6{,}760{,}000$ possible plates.

ThSum Rule (Addition Principle)

If a task can be performed in one of $n_1$ ways OR in one of $n_2$ ways, and the two sets of ways are disjoint (mutually exclusive), then the total number of ways is:

n_1 + n_2

More generally, if a task can be done in $n_1, n_2, \ldots, n_k$ mutually exclusive ways, the total is $n_1 + n_2 + \cdots + n_k$ .

Example: A student can choose from 5 math courses OR 3 CS courses OR 2 physics courses. Total options: $5 + 3 + 2 = 10$ .

⚠️ When to Apply Each Rule

Product Rule: Multiple stages that happen together (AND). "Do this AND then that."
Sum Rule: Multiple alternatives (OR). "Do this OR that."
If unsure, ask: "Do I need to complete all stages, or just one of several options?"

Permutations

Permutations (Ordered Arrangements)

P(n,k) = \frac{n!}{(n-k)!}

Here,

$n$ =Total number of distinct items
$k$ =Number of items to arrange
$P(n,k)$ =Number of ordered arrangements of k items from n

📝Example: Arranging Books

How many ways can you arrange 3 books chosen from a shelf of 8?

P(8,3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336

ℹ️ Full Permutations

When $k = n$ , we get $P(n,n) = n!$ , the total number of ways to arrange all $n$ items. For example, $P(5,5) = 5! = 120$ .

Combinations

Combinations (Unordered Selections)

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Here,

$n$ =Total number of distinct items
$k$ =Number of items to choose
$\binom{n}{k}$ =Number of ways to choose k items from n (order does not matter)

📝Example: Choosing a Committee

A committee of 4 people is to be chosen from a group of 12.

\binom{12}{4} = \frac{12!}{4!8!} = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = 495

⚠️ Permutation vs. Combination

Use permutations when order matters (e.g., assigning ranks: 1st, 2nd, 3rd). Use combinations when order does not matter (e.g., selecting a group of members).

The relationship between them: $P(n,k) = \binom{n}{k} \times k!$

Permutations with Repetition

n^k

Here,

$n$ =Number of distinct items to choose from
$k$ =Number of positions to fill (repetition allowed)

📝Example: Binary Strings

How many 8-bit binary strings are possible? Each bit can be 0 or 1 (repetition allowed).

2^8 = 256

📝Example: Password with Repetition

A 4-character password using 26 lowercase letters (repetition allowed):

26^4 = 456{,}976

Combinations with Repetition

Combinations with Repetition (Stars and Bars)

\binom{n+k-1}{k} = \binom{n+k-1}{n-1}

Here,

$n$ =Number of distinct types of items
$k$ =Number of items to select (repetition allowed)

📝Example: Distributing Candies

You have 3 types of candy and want to choose 5 pieces (repetition allowed).

\binom{3+5-1}{5} = \binom{7}{5} = \binom{7}{2} = 21

ℹ️ Stars and Bars Visualization

To distribute $k$ identical items into $n$ distinct bins, we use $n-1$ bars to separate bins and $k$ stars to represent items. The total arrangements of $k$ stars and $n-1$ bars is $\binom{n+k-1}{k}$ .

Binomial Theorem

ThBinomial Theorem

For any real numbers $x$ and $y$ and non-negative integer $n$ :

(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

The binomial coefficient $\binom{n}{k}$ gives the coefficient of the $x^{n-k}y^k$ term.

Binomial Expansion

(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k

Here,

$\binom{n}{k}$ =Binomial coefficient (appears as the coefficient of each term)
$x, y$ =Terms being raised to the power n

📝Example: Expanding (x + y)^3

(x+y)^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3}y^3

= 1 \cdot x^3 + 3 \cdot x^2y + 3 \cdot xy^2 + 1 \cdot y^3 = x^3 + 3x^2y + 3xy^2 + y^3

📝Example: Binomial Coefficients Sum

What is $\sum_{k=0}^{n} \binom{n}{k}$ ?

Setting $x = 1, y = 1$ in the Binomial Theorem:

(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} = 2^n

Pascal's Triangle

DfPascal's Triangle

Pascal's Triangle is a triangular array where each entry is the sum of the two entries directly above it. Row $n$ (starting from $n=0$ ) contains the binomial coefficients $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ .

First 8 rows of Pascal's Triangle:

Architecture Diagram

Row 0:              1
Row 1:            1   1
Row 2:          1   2   1
Row 3:        1   3   3   1
Row 4:      1   4   6   4   1
Row 5:    1   5  10  10   5   1
Row 6:  1   6  15  20  15   6   1
Row 7: 1  7  21  35  35  21   7   1

ThPascal's Identity

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Each entry is the sum of the two entries above it.

ℹ️ Properties of Pascal's Triangle

Symmetry: $\binom{n}{k} = \binom{n}{n-k}$
Sum of row $n$ : $2^n$
Hockey stick identity: $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$
Fibonacci numbers appear along shallow diagonals.

Inclusion-Exclusion Principle

Inclusion-Exclusion (Two Sets)

|A \cup B| = |A| + |B| - |A \cap B|

Here,

$|A|$ =Size of set A
$|B|$ =Size of set B
$|A \cap B|$ =Size of the intersection of A and B

Inclusion-Exclusion (Three Sets)

|A \\cup B \\cup C| = |A| + |B| + |C| - |A \\cap B| - |A \\cap C| - |B \\cap C| + |A \\cap B \\cap C|

Here,

$|A \cup B \cup C|$ =Size of the union of three sets

General Inclusion-Exclusion

\\left|\\bigcup_{i=1}^{n} A_i\\right| = \\sum_{k=1}^{n} (-1)^{k+1} \\sum_{|I|=k} \\left|\\bigcap_{i \\in I} A_i\\right|

Here,

$A_i$ =Sets to be combined
$I$ =Index subset of {1, 2, ..., n}

📝Example: Survey Problem

In a survey of 100 people: 60 like tea, 50 like coffee, 40 like both. How many like at least one?

|T \cup C| = |T| + |C| - |T \cap C| = 60 + 50 - 40 = 70

ℹ️ When to Use Inclusion-Exclusion

Use inclusion-exclusion when counting the union of overlapping sets. It corrects for double-counting elements that belong to multiple sets.

Pigeonhole Principle

ThPigeonhole Principle (Basic)

If $n$ items are placed into $m$ containers and $n > m$ , then at least one container contains more than one item.

ThPigeonhole Principle (Generalized)

If $n$ items are placed into $m$ containers, then at least one container contains at least $\lceil n/m \rceil$ items.

📝Example: Birthday Problem

In a group of 367 people, at least two people must share a birthday (since there are only 366 possible birthdays including Feb 29).

📝Example: Socks in a Drawer

A drawer contains 10 black socks and 10 blue socks. How many must you pull out (in the dark) to guarantee a matching pair?

Using the pigeonhole principle with 2 colors: you need to pull out $\mathbf{3}$ socks. The first two might not match, but the third must match one of the first two.

ℹ️ Pigeonhole in Competitions

The pigeonhole principle is a favorite in math competitions and coding interviews because it provides elegant non-constructive proofs�proving something exists without finding it explicitly.

Python Implementation

from math import comb, perm, factorial
from itertools import combinations, permutations
from functools import reduce
import operator

# Basic calculations
print(f"10! = {factorial(10)}")                    # 3628800
print(f"P(10,3) = {perm(10, 3)}")                  # 720
print(f"C(10,3) = {comb(10, 3)}")                  # 120

# Pascal's Triangle
def pascal_triangle(n):
    triangle = [[1]]
    for i in range(1, n + 1):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i-1][j-1] + triangle[i-1][j])
        row.append(1)
        triangle.append(row)
    return triangle

for row in pascal_triangle(7):
    print(" " * (7 - len(row)) + " ".join(map(str, row)))

# Inclusion-Exclusion for two sets
def inclusion_exclusion_two(A, B, A_inter_B):
    return A + B - A_inter_B

# Example: people who like tea or coffee
tea, coffee, both = 60, 50, 40
print(f"At least one: {inclusion_exclusion_two(tea, coffee, both)}")  # 70

# Pigeonhole principle
def min_pigeonhole(items, containers):
    import math
    return math.ceil(items / containers)

print(f"Min in one container (17 items, 5 boxes): {min_pigeonhole(17, 5)}")  # 4

# Combinations with repetition
def comb_repetition(n, k):
    return comb(n + k - 1, k)

print(f"C(3,5) with repetition: {comb_repetition(3, 5)}")  # 21

# Generating all combinations
items = ['A', 'B', 'C', 'D']
print("Combinations of 2 from ABCD:")
for c in combinations(items, 2):
    print(f"  {c}")

Applications in AI/ML

ℹ️ Combinatorics in AI and Machine Learning

Combinatorial reasoning is fundamental to many AI and ML concepts:

Hyperparameter Search

The number of hyperparameter configurations grows combinatorially. If a model has 4 hyperparameters with 5, 10, 3, and 7 possible values respectively, a grid search requires $5 \times 10 \times 3 \times 7 = 1{,}050$ evaluations.

Feature Selection

Selecting the best $k$ features from $n$ candidates is a combinatorial problem with $\binom{n}{k}$ possibilities. For $n=100$ features and $k=10$ , this is approximately $1.7 \times 10^{13}$ combinations�too many to brute-force.

Permutation Tests

Permutation tests in statistics compare observed statistics against distributions generated by randomly permuting labels. The total number of permutations is $n!$ , making exact tests infeasible for large $n$ .

Neural Architecture Search

NAS explores architectures as combinations of layers, connections, and operations. The search space grows exponentially with depth and breadth.

Attention Mechanisms

Self-attention in Transformers considers all $\binom{n}{2}$ pairs of positions, leading to $O(n^2)$ complexity. Understanding this combinatorial structure drives efficient attention variants.

Common Mistakes

Mistake	Correct Approach	Example
Using permutations when order doesn't matter	Use combinations for unordered selections	Choosing a committee: use $\binom{n}{k}$ , not $P(n,k)$
Forgetting to divide by $k!$	Combinations divide out the ordering: $\frac{P(n,k)}{k!}$	$\binom{10}{3} = \frac{P(10,3)}{3!} = \frac{720}{6} = 120$
Adding when you should multiply	Use product rule for sequential stages	3 shirts AND 2 pants = $3 \times 2 = 6$ outfits
Multiplying when you should add	Use sum rule for alternative choices	3 shirts OR 2 pants = $3 + 2 = 5$ choices
Ignoring overlapping sets	Apply inclusion-exclusion	$\|A \cup B\| = \|A\| + \|B\| - \|A \cap B\|$
Confusing repetition formulas	$n^k$ is ordered repetition; $\binom{n+k-1}{k}$ is unordered	Passwords: $n^k$ ; candy selection: stars and bars

Interview Questions

How many ways can you arrange the letters in "MISSISSIPPI"?

Answer: $\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = 34{,}650$
If you flip a coin 10 times, how many outcomes have exactly 7 heads?

Answer: $\binom{10}{7} = 120$
You have 5 different books. How many ways can you arrange them on a shelf such that two specific books are always adjacent?

Answer: Treat the two books as one unit. $4! \times 2! = 48$
What is the coefficient of $x^3y^2$ in $(x + y)^5$ ?

Answer: $\binom{5}{3} = 10$
How many 5-digit numbers use only the digits {1, 2, 3} and each digit appears at least once?

Answer: $3^5 - 3 \cdot 2^5 + 3 \cdot 1^5 = 243 - 96 + 3 = 150$ (inclusion-exclusion)
Given 12 people, how many ways to form a committee of 5 with a designated chair?

Answer: Choose 5 from 12, then choose chair from 5: $\binom{12}{5} \times 5 = 792 \times 5 = 3{,}960$

Practice Problems

📝Practice 1: Password Strength

How many 8-character passwords can be formed using 26 lowercase letters, 10 digits, and 10 special characters if repetition is allowed?

💡Solution 1

Total characters: $26 + 10 + 10 = 46$ . With repetition: $46^8 = 200{,}476{,}122{,}368{,}576$ .

📝Practice 2: Distributing Gifts

In how many ways can 12 identical gifts be distributed among 4 children?

💡Solution 2

Stars and bars: $\binom{4+12-1}{12} = \binom{15}{12} = \binom{15}{3} = 455$ .

📝Practice 3: Derangements

A derangement is a permutation where no element appears in its original position. How many derangements of $\{1, 2, 3, 4\}$ exist?

💡Solution 3

Using inclusion-exclusion: $D_4 = 4!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) = 24\left(\frac{3}{8}\right) = 9$ .

📝Practice 4: Counting Paths

On a 5�5 grid, how many shortest paths exist from the bottom-left to the top-right corner (only moving right or up)?

💡Solution 4

You must make exactly 5 right moves and 5 up moves (10 total). The number of paths is $\binom{10}{5} = 252$ .

Quick Reference

Formula	Name	When to Use
$n!$	Factorial	Arranging all $n$ items
$P(n,k) = \frac{n!}{(n-k)!}$	Permutations	Choosing and arranging $k$ from $n$
$\binom{n}{k} = \frac{n!}{k!(n-k)!}$	Combinations	Choosing $k$ from $n$ (unordered)
$n^k$	Permutations with Repetition	Filling $k$ slots from $n$ options
$\binom{n+k-1}{k}$	Combinations with Repetition	Choosing $k$ from $n$ with replacement
$\\|A \cup B\\| = \\|A\\| + \\|B\\| - \\|A \cap B\\|$	Inclusion-Exclusion	Overlapping sets
$\lceil n/m \rceil$	Pigeonhole (generalized)	Minimum items in one container
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$	Pascal's Identity	Recursive binomial computation

Cross-References

Probability Theory: Combinatorics provides the sample space counting for classical probability calculations.
Discrete Probability Distributions — The binomial distribution uses $\binom{n}{k} p^k (1-p)^{n-k}$ .
Graph Theory: Counting edges, paths, cycles, and spanning trees all rely on combinatorial methods.
Algorithm Analysis: The number of subsets $2^n$ , permutations $n!$ , and combinations $\binom{n}{k}$ appear in time complexity analysis.
Information Theory — Combinatorial entropy bounds relate to the number of possible messages.
Cryptography: Key space size is $|\text{key space}|$ , computed via combinatorial counting.

Summary

📋Key Takeaways

Product and Sum Rules: The product rule $|A \times B| = |A| \cdot |B|$ counts ordered pairs from sequential stages, while the sum rule $|A \cup B| = |A| + |B|$ counts disjoint alternatives. These are the two pillars of all counting.
Permutations vs. Combinations: Permutations $P(n,k) = \frac{n!}{(n-k)!}$ count ordered arrangements, while combinations $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ count unordered selections. Order matters for permutations, not for combinations.
Repetition Variants: With repetition, ordered selections give $n^k$ possibilities, while unordered selections give $\binom{n+k-1}{k}$ via stars and bars.
Binomial Theorem: $(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$ connects combinations to algebra. The coefficients $\binom{n}{k}$ appear in Pascal's triangle.
Pascal's Identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ enables efficient recursive computation of binomial coefficients.
Inclusion-Exclusion: Corrects for double-counting in overlapping sets. For two sets: $|A \cup B| = |A| + |B| - |A \cap B|$ .
Pigeonhole Principle: If $n > m$ , at least one of $m$ containers holds more than one item. Generalized: at least one holds $\lceil n/m \rceil$ items.
Factorials Grow Fast: $n!$ grows extremely rapidly � $10! = 3{,}628{,}800$ . This is why approximation methods like Stirling's formula are useful.
AI/ML Applications: Combinatorial explosion drives the need for heuristics in hyperparameter search, feature selection, and neural architecture search.