Combinatorics

Combinatorics

Counting Principles

Permutations

Combinations

Permutations with Repetition

Combinations with Repetition

Binomial Theorem

Pascal's Triangle

First 8 rows of Pascal's Triangle:

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

Inclusion-Exclusion Principle

Pigeonhole Principle

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

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 evaluations.

Feature Selection

Selecting the best features from candidates is a combinatorial problem with possibilities. For features and , this is approximately 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 , making exact tests infeasible for large .

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 pairs of positions, leading to complexity. Understanding this combinatorial structure drives efficient attention variants.

Common Mistakes

Interview Questions

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

   Answer:

2. If you flip a coin 10 times, how many outcomes have exactly 7 heads?

   Answer:

3. 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. What is the coefficient of in ?

   Answer:

5. How many 5-digit numbers use only the digits {1, 2, 3} and each digit appears at least once?

   Answer: (inclusion-exclusion)

6. 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:

Practice Problems

Quick Reference

Cross-References

• Probability Theory: Combinatorics provides the sample space counting for classical probability calculations.
• Discrete Probability Distributions — The binomial distribution uses .
• Graph Theory: Counting edges, paths, cycles, and spanning trees all rely on combinatorial methods.
• Algorithm Analysis: The number of subsets , permutations , and combinations appear in time complexity analysis.
• Information Theory — Combinatorial entropy bounds relate to the number of possible messages.
• Cryptography: Key space size is , computed via combinatorial counting.

Summary