Discrete Structures and Counting

Combinatorics is the branch of mathematics dealing with combinations of objects belonging to finite sets. It is foundational for probability and computer science.

Permutations and Combinations

• A permutation is an arrangement of objects in a specific order. The number of permutations of $n$ objects taken $r$ at a time is: $P(n, r) = \frac{n!}{(n-r)!}$
• A combination is a selection of objects where order does not matter: $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

import math

def permutations(n, r):
  return math.factorial(n) // math.factorial(n - r)

def combinations(n, r):
  return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

print(f"Permutations of 5 pick 3: {permutations(5, 3)}") # 60
print(f"Combinations of 5 pick 3: {combinations(5, 3)}") # 10

The Pigeonhole Principle

The pigeonhole principle states that if $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item. While simple, it is a powerful tool for proving existence.

Generating Functions

A generating function is a way of encoding an infinite sequence of numbers $(a_n)$ by treating them as the coefficients of a formal power series: $G(x) = \sum_{n=0}^{\infty} a_n x^n$

def get_fibonacci_coefficient(n):
  """Sequence: 0, 1, 1, 2, 3, 5, ...
  Generating function: x / (1 - x - x^2)"""
  a, b = 0, 1
  for _ in range(n):
      a, b = b, a + b
  return a

print(f"10th Fibonacci number: {get_fibonacci_coefficient(10)}")

Principle of Inclusion-Exclusion

For two sets $A$ and $B$: $|A \cup B| = |A| + |B| - |A \cap B|$ This generalizes to any number of sets, compensating for over-counting elements in intersections.