Combinatorics and Enumerative Analysis

Combinatorics is the study of discrete structures. It determines the existence, count, and optimization of arrangements according to specific rules.

Fundamental Principles

• Addition Principle: If events are mutually exclusive, sum the ways.
• Multiplication Principle: If events occur in sequence, multiply the ways.

Permutations and Combinations

Permutations ($P(n, k)$): Choosing and ordering $k$ elements from $n$. $P(n, k) = \frac{n!}{(n-k)!}$

Combinations ($\binom{n}{k}$): Choosing $k$ elements without regard to order. $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

import math

def nCr(n, r):
  return math.comb(n, r)

def nPr(n, r):
  return math.perm(n, r)

print(f"Combinations (10 choose 3): {nCr(10, 3)}")
print(f"Permutations (10 permute 3): {nPr(10, 3)}")

Pascal’s Triangle and Binomial Expansion

The identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ allows for recursive construction.

def pascal_triangle(rows):
  triangle = [[1]]
  for i in range(1, rows):
      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(6):
  print(str(row).center(30))

Advanced Principles

• Pigeonhole Principle: If $n > m$ items are put in $m$ boxes, one box has $>1$ item.
• Inclusion-Exclusion: Corrects for overcounting in unions ($|A \cup B| = |A| + |B| - |A \cap B|$).

Stars and Bars: Multisets

Choosing $k$ items from $n$ types with repetition: $\binom{n+k-1}{k}$.

from itertools import combinations_with_replacement

# Choosing 2 items from {A, B, C} with repetition
types = ['A', 'B', 'C']
k = 2
combos = list(combinations_with_replacement(types, k))
print(f"Multisets of size {k} from {types}:")
print(combos)
print(f"Formula count: {nCr(len(types) + k - 1, k)}")