Combinatorics

Master advanced combinatorial techniques for complex counting problems

Overview

Combinatorics is a core mathematical branch in competitive programming, involving counting, permutations, and combinations. This chapter explores advanced techniques like inclusion-exclusion principle, Catalan numbers, and generating functions to solve complex combinatorial problems in world-class competitions.

Core Content

1. Inclusion-Exclusion Principle

The inclusion-exclusion principle is a powerful tool for complex counting problems, calculating the size of unions through alternating addition and subtraction.

Basic Principle

// Inclusion-Exclusion: Calculate size of union of multiple sets
// |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Count numbers divisible by certain numbers (1 to n)
long long inclusionExclusion(long long n, vector<int>& divisors) {
    int m = divisors.size();
    long long result = 0;
    
    // Enumerate all subsets
    for (int mask = 1; mask < (1 << m); mask++) {
        long long lcm = 1;
        int bits = 0;
        
        // Calculate LCM of current subset
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                lcm = lcm / __gcd(lcm, (long long)divisors[i]) * divisors[i];
                bits++;
                if (lcm > n) break; // Optimization: break if LCM too large
            }
        }
        
        // Add or subtract based on subset size
        if (bits % 2 == 1) {
            result += n / lcm;
        } else {
            result -= n / lcm;
        }
    }
    
    return result;
}

int main() {
    long long n = 100;
    vector<int> divisors = {2, 3, 5};
    
    // Count numbers from 1 to 100 divisible by 2, 3, or 5
    cout << inclusionExclusion(n, divisors) << endl;
    
    return 0;
}

Advanced Application: Derangements

// Derangements: Calculate number of complete derangements of n elements
#include <iostream>
#include <vector>
using namespace std;

// Calculate derangements using inclusion-exclusion
long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    // D(n) = n! * Σ(k=0 to n) (-1)^k / k!
    long long factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial *= i;
    }
    
    double sum = 0;
    long long fact = 1;
    for (int k = 0; k <= n; k++) {
        if (k > 0) fact *= k;
        sum += (k % 2 == 0 ? 1.0 : -1.0) / fact;
    }
    
    return (long long)(factorial * sum + 0.5);
}

// Calculate derangements using recurrence (more efficient)
long long derangementsDP(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // D(n) = (n-1) * (D(n-1) + D(n-2))
        dp[i] = (long long)(i - 1) * (dp[i - 1] + dp[i - 2]);
    }
    
    return dp[n];
}

int main() {
    for (int n = 0; n <= 10; n++) {
        cout << "D(" << n << ") = " << derangementsDP(n) << endl;
    }
    return 0;
}

2. Catalan Numbers

Catalan numbers have wide applications in combinatorics, from parentheses matching to binary tree counting, key for solving recursive structure problems. 

// Multiple methods to calculate Catalan numbers
#include <iostream>
#include <vector>
using namespace std;

// Method 1: Recurrence C(n) = Σ(i=0 to n-1) C(i) * C(n-1-i)
long long catalanDP(int n) {
    vector<long long> catalan(n + 1, 0);
    catalan[0] = catalan[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - 1 - j];
        }
    }
    
    return catalan[n];
}

// Method 2: Combinatorial formula C(n) = C(2n, n) / (n + 1)
long long catalanCombination(int n) {
    // Calculate combination C(2n, n)
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result = result * (2 * n - i) / (i + 1);
    }
    return result / (n + 1);
}

// Application 1: Number of valid parentheses sequences
int validParentheses(int n) {
    return catalanDP(n);
}

// Application 2: Number of binary search trees
int numBST(int n) {
    return catalanDP(n);
}

// Application 3: Number of mountain arrays
int mountainArrays(int n) {
    if (n % 2 == 0) return 0; // Even length cannot form mountain
    return catalanDP(n / 2);
}

// Application 4: Triangulations of convex polygon
int triangulations(int n) {
    if (n < 3) return 0;
    return catalanDP(n - 2);
}

int main() {
    int n = 10;
    cout << "Catalan numbers:" << endl;
    for (int i = 0; i <= n; i++) {
        cout << "C(" << i << ") = " << catalanDP(i) << endl;
    }
    
    cout << "\nApplications:" << endl;
    cout << "Valid parentheses with 5 pairs: " << validParentheses(5) << endl;
    cout << "BSTs with 5 nodes: " << numBST(5) << endl;
    cout << "Triangulations of hexagon: " << triangulations(6) << endl;
    
    return 0;
}

3. Advanced Combinatorial Techniques

Generating Functions

Generating functions are powerful tools in combinatorics, transforming combinatorial problems into algebraic ones. 

// Generating Functions: Integer Partitions
#include <iostream>
#include <vector>
using namespace std;

// Calculate number of partitions of integer n (order does not matter)
int partitions(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    // Process each possible part
    for (int part = 1; part <= n; part++) {
        for (int sum = part; sum <= n; sum++) {
            dp[sum] += dp[sum - part];
        }
    }
    
    return dp[n];
}

// Calculate distinct partitions of n (all parts different)
int distinctPartitions(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int part = 1; part <= n; part++) {
        for (int sum = n; sum >= part; sum--) {
            dp[sum] += dp[sum - part];
        }
    }
    
    return dp[n];
}

// Pentagonal Number Theorem: Fast partition calculation
vector<int> fastPartitions(int n) {
    vector<int> p(n + 1, 0);
    p[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int k = 1; ; k++) {
            // Pentagonal numbers: k(3k-1)/2
            int pent1 = k * (3 * k - 1) / 2;
            int pent2 = k * (3 * k + 1) / 2;
            
            if (pent1 > i) break;
            
            // Apply recurrence relation
            if (k % 2 == 1) {
                p[i] += p[i - pent1];
                if (pent2 <= i) p[i] += p[i - pent2];
            } else {
                p[i] -= p[i - pent1];
                if (pent2 <= i) p[i] -= p[i - pent2];
            }
        }
    }
    
    return p;
}

int main() {
    int n = 20;
    
    cout << "Integer partitions:" << endl;
    for (int i = 1; i <= 10; i++) {
        cout << "P(" << i << ") = " << partitions(i) << endl;
    }
    
    cout << "\nDistinct partitions:" << endl;
    for (int i = 1; i <= 10; i++) {
        cout << "Q(" << i << ") = " << distinctPartitions(i) << endl;
    }
    
    // Verify pentagonal number theorem
    vector<int> fast = fastPartitions(n);
    cout << "\nFast algorithm verification: P(" << n << ") = " << fast[n] << endl;
    cout << "Standard algorithm: P(" << n << ") = " << partitions(n) << endl;
    
    return 0;
}

Burnside's Lemma

// Burnside's Lemma: Count distinct colorings under group action
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Calculate GCD
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Count distinct necklace colorings (rotations and reflections)
long long necklaceColorings(int n, int k) {
    if (n == 0) return 1;
    
    long long result = 0;
    
    // Rotational symmetry: for each possible rotation angle
    for (int i = 0; i < n; i++) {
        int cycles = gcd(n, i);
        result += (long long)pow(k, cycles);
    }
    
    // Reflection symmetry
    if (n % 2 == 1) {
        // Odd: n reflection axes, each fixes 1 bead
        result += n * (long long)pow(k, (n + 1) / 2);
    } else {
        // Even: n/2 axes through vertices + n/2 axes through edge midpoints
        result += (n / 2) * (long long)pow(k, n / 2 + 1);
        result += (n / 2) * (long long)pow(k, n / 2);
    }
    
    // Apply Burnside's lemma: average number of fixed points
    return result / (2 * n);
}

// Count distinct square colorings (4 vertices, k colors)
long long squareColorings(int k) {
    // 8 symmetry operations: identity, 3 rotations, 4 reflections
    long long result = 0;
    
    // Identity: all colorings are fixed
    result += (long long)pow(k, 4);
    
    // 90° and 270° rotations: all 4 vertices same color
    result += 2 * k;
    
    // 180° rotation: diagonal vertices same color
    result += (long long)k * k;
    
    // 4 reflections: adjacent vertices paired
    result += 4 * (long long)k * k;
    
    return result / 8;
}

int main() {
    cout << "Necklace coloring problems:" << endl;
    for (int n = 3; n <= 8; n++) {
        for (int k = 2; k <= 4; k++) {
            cout << "n=" << n << ", k=" << k << ": " 
                 << necklaceColorings(n, k) << " distinct colorings" << endl;
        }
    }
    
    cout << "\nSquare colorings:" << endl;
    for (int k = 2; k <= 5; k++) {
        cout << k << " colors: " 
             << squareColorings(k) << " distinct colorings" << endl;
    }
    
    return 0;
}

Problem-Solving Tips

🎯 Problem Recognition

Learn to recognize different combinatorial problems: use inclusion-exclusion for counting, consider Catalan numbers for recursive structures, apply Burnside's lemma for symmetry problems.

⚡ Computational Optimization

Watch for overflow in large number calculations, use modular arithmetic and fast exponentiation. Precomputing combinations and factorials significantly improves efficiency.

🔄 Recurrence Relations

Many combinatorial problems have elegant recurrence relations. Finding state transition equations is often more efficient than direct calculation.

🧮 Mathematical Insights

Deeply understand combinatorial identities and generating functions - they are powerful tools for solving complex combinatorial problems.

📚 Chapter Index