Combinatorics

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Introduction to Combinatorics

Combinatorics is the study of counting, arrangement, and combination of objects. It provides tools for solving problems involving discrete structures and is fundamental to probability theory, computer science, and optimization.

2. Basic Counting Principles

2.1 Addition Principle

If there are $m$ ways to do one thing and $n$ ways to do another, and these two things cannot be done simultaneously, then there are $m + n$ ways to do either.

2.2 Multiplication Principle

If there are $m$ ways to do one thing and $n$ ways to do another, then there are $m \times n$ ways to do both.

2.3 Inclusion-Exclusion Principle

For two sets $A$ and $B$:

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

For three sets:

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

3. Permutations

3.1 Permutations without Repetition

The number of ways to arrange $r$ objects from $n$ distinct objects is:

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

When $r = n$, we have $P(n, n) = n!$ (all arrangements of $n$ objects).

3.2 Permutations with Repetition

If we have $n$ objects where $n_1$ are of type 1, $n_2$ are of type 2, ..., $n_k$ are of type $k$:

\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}

3.3 Circular Permutations

The number of ways to arrange $n$ distinct objects in a circle is $(n-1)!$.

4. Combinations

4.1 Combinations without Repetition

The number of ways to choose $r$ objects from $n$ distinct objects (order doesn't matter):

C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

4.2 Properties of Binomial Coefficients

$\binom{n}{r} = \binom{n}{n-r}$ (Symmetry)
$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ (Pascal's Identity)
$\sum_{r=0}^{n} \binom{n}{r} = 2^n$ (Sum of row in Pascal's triangle)
$\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$ for $n > 0$

4.3 Combinations with Repetition

The number of ways to choose $r$ objects from $n$ types (with repetition allowed):

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

5. Generating Functions

5.1 Ordinary Generating Functions

For a sequence $\{a_n\}$, the generating function is:

G(x) = \sum_{n=0}^{\infty} a_n x^n

5.2 Common Generating Functions

$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ (geometric series)
$\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$
$(1+x)^n = \sum_{r=0}^{n} \binom{n}{r} x^r$ (binomial theorem)
$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$

5.3 Exponential Generating Functions

For labeled objects, we use:

G(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}

6. Recurrence Relations

6.1 Linear Homogeneous Recurrence Relations

For $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$

The characteristic equation is:

r^k - c_1 r^{k-1} - c_2 r^{k-2} - \ldots - c_k = 0

6.2 Fibonacci Numbers

$F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0, F_1 = 1$

Closed form (Binet's formula):

F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}

where $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$

7. Catalan Numbers

The $n$-th Catalan number is:

C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}

Recurrence relation: $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$

Applications: Number of valid parentheses expressions, binary trees, triangulations of polygons.

8. Stirling Numbers

8.1 Stirling Numbers of the First Kind

$S(n, k)$ counts the number of permutations of $n$ elements with $k$ cycles.

$$S(n, k) = S(n-1, k-1) + (n-1)S(n-1, k)$$

8.2 Stirling Numbers of the Second Kind

$\{n \atop k\}$ counts the number of ways to partition $n$ objects into $k$ non-empty subsets.

\left\{n \atop k\right\} = \left\{n-1 \atop k-1\right\} + k\left\{n-1 \atop k\right\}

9. Derangements

A derangement is a permutation where no element is in its original position.

Number of derangements of $n$ objects:

D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} \approx \frac{n!}{e}

Recurrence: $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \geq 2$

10. Pigeonhole Principle

10.1 Basic Form

If $n$ objects are placed into $m$ containers with $n > m$, then at least one container contains more than one object.

10.2 Generalized Form

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

11. Burnside's Lemma

For counting objects under group actions:

|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|

where $X^g$ is the set of elements fixed by group element $g$.

12. Ramsey Theory

Ramsey numbers $R(r, s)$ represent the minimum number of vertices needed so that any 2-coloring of edges contains either a red clique of size $r$ or a blue clique of size $s$.

Famous result: $R(3, 3) = 6$

13. Code Examples

# Python implementations of combinatorial functions
import math
from functools import lru_cache

def factorial(n):
    """Calculate n! efficiently"""
    if n < 0:
        raise ValueError("Factorial undefined for negative numbers")
    return math.factorial(n)

def permutations(n, r):
    """Calculate P(n, r) = n!/(n-r)!"""
    if r > n or r < 0:
        return 0
    return factorial(n) // factorial(n - r)

def combinations(n, r):
    """Calculate C(n, r) = n!/(r!(n-r)!)"""
    if r > n or r < 0:
        return 0
    if r > n - r:  # Take advantage of symmetry
        r = n - r
    
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    return result

def combinations_with_repetition(n, r):
    """Calculate combinations with repetition: C(n+r-1, r)"""
    return combinations(n + r - 1, r)

@lru_cache(maxsize=None)
def fibonacci(n):
    """Calculate nth Fibonacci number"""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def fibonacci_closed_form(n):
    """Calculate nth Fibonacci number using Binet's formula"""
    phi = (1 + math.sqrt(5)) / 2
    psi = (1 - math.sqrt(5)) / 2
    return round((phi**n - psi**n) / math.sqrt(5))

@lru_cache(maxsize=None)
def catalan(n):
    """Calculate nth Catalan number"""
    if n <= 1:
        return 1
    
    # Using the recurrence relation
    result = 0
    for i in range(n):
        result += catalan(i) * catalan(n - 1 - i)
    return result

def catalan_formula(n):
    """Calculate nth Catalan number using direct formula"""
    return combinations(2 * n, n) // (n + 1)

def derangements(n):
    """Calculate number of derangements of n objects"""
    if n == 0:
        return 1
    if n == 1:
        return 0
    
    # Using the recurrence relation
    prev_prev = 1  # D(0)
    prev = 0       # D(1)
    
    for i in range(2, n + 1):
        current = (i - 1) * (prev + prev_prev)
        prev_prev, prev = prev, current
    
    return prev

def stirling_second(n, k):
    """Calculate Stirling number of the second kind"""
    if n == 0 and k == 0:
        return 1
    if n == 0 or k == 0:
        return 0
    if k > n:
        return 0
    
    # Dynamic programming approach
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, k + 1)):
            dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]
    
    return dp[n][k]

def bell_number(n):
    """Calculate nth Bell number (sum of Stirling numbers of second kind)"""
    return sum(stirling_second(n, k) for k in range(n + 1))

def generate_partitions(n):
    """Generate all integer partitions of n"""
    def backtrack(remaining, max_value, current_partition):
        if remaining == 0:
            partitions.append(current_partition[:])
            return
        
        for i in range(min(remaining, max_value), 0, -1):
            current_partition.append(i)
            backtrack(remaining - i, i, current_partition)
            current_partition.pop()
    
    partitions = []
    backtrack(n, n, [])
    return partitions

def multinomial_coefficient(*args):
    """Calculate multinomial coefficient for given frequencies"""
    n = sum(args)
    result = factorial(n)
    for k in args:
        result //= factorial(k)
    return result

# Example usage and testing
if __name__ == "__main__":
    print("Combinatorial Functions Examples:")
    print(f"10! = {factorial(10)}")
    print(f"P(10, 3) = {permutations(10, 3)}")
    print(f"C(10, 3) = {combinations(10, 3)}")
    print(f"C(5, 3) with repetition = {combinations_with_repetition(5, 3)}")
    
    print(f"\nFibonacci sequence (first 10):")
    for i in range(10):
        print(f"F({i}) = {fibonacci(i)}")
    
    print(f"\nCatalan numbers (first 6):")
    for i in range(6):
        print(f"C({i}) = {catalan(i)}")
    
    print(f"\nDerangements:")
    for i in range(6):
        print(f"D({i}) = {derangements(i)}")
    
    print(f"\nStirling numbers of second kind S(5, k):")
    for k in range(6):
        print(f"S(5, {k}) = {stirling_second(5, k)}")
    
    print(f"\nBell numbers (first 6):")
    for i in range(6):
        print(f"B({i}) = {bell_number(i)}")
    
    print(f"\nPartitions of 4: {generate_partitions(4)}")
    print(f"Multinomial(6; 2,2,2) = {multinomial_coefficient(2, 2, 2)}")

14. Applications

14.1 Probability Theory

Combinatorics provides the foundation for calculating probabilities in discrete sample spaces.

14.2 Computer Science

Algorithm analysis (counting operations)
Data structures (trees, graphs)
Cryptography (key generation, permutation ciphers)

14.3 Optimization

Many optimization problems involve counting feasible solutions or arrangements.

15. References

Stanley, R. P. (2011). Enumerative Combinatorics.
van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics.
Tucker, A. (2012). Applied Combinatorics.