combinatorics

name	combinatorics
description	Counting principles, permutations, combinations, generating functions, partition theory, and combinatorial algorithms for enumeration and optimization.
category	mathematics
tags	["mathematics","combinatorics","permutations","combinations","generating-functions","partitions","enumeration"]
difficulty	intermediate
author	neuralblitz

Combinatorics

What I do

I provide comprehensive expertise in combinatorics, the mathematics of counting, arrangement, and selection. I enable you to solve counting problems using permutations, combinations, and generating functions, analyze partition structures, and apply combinatorial algorithms for enumeration. My knowledge spans from fundamental counting principles to advanced topics like Polya enumeration and combinatorial optimization essential for algorithm analysis, probability, cryptography, and operations research.

When to use me

Use combinatorics when you need to: count arrangements and selections in probability problems, optimize resource allocation with constraints, analyze algorithm complexity through counting, design experiments and surveys, solve problems involving dice, cards, and games, enumerate structures in graph theory, implement combinatorial generation algorithms, or apply inclusion-exclusion principle for complex counting.

Core Concepts

• Fundamental Counting Principle: If one task has m ways and another has n ways, together they have m×n ways.
• Permutations: Arrangements of objects where order matters, with P(n,k) = n!/(n-k)! variations.
• Combinations: Selections of objects where order doesn't matter, with C(n,k) = n!/(k!(n-k)!) possibilities.
• Multinomial Coefficients: Counting ways to divide objects into groups of specified sizes.
• Stars and Bars: Method for counting solutions to equations with non-negative integer variables.
• Generating Functions: Formal power series encoding combinatorial sequences and solving recurrence relations.
• Partition Theory: Ways of writing integers as sums of positive integers without regard to order.
• Inclusion-Exclusion Principle: Counting technique for unions of sets with overlapping elements.
• Pigeonhole Principle: If n items are placed in m containers with n > m, at least one container has multiple items.
• Recurrence Relations: Equations expressing sequence terms in terms of previous terms.

Code Examples

Basic Counting

import math
from itertools import combinations, permutations, product

def permutations_count(n, k):
    """Number of permutations of n items taken k at a time."""
    return math.perm(n, k) if hasattr(math, 'perm') else math.factorial(n) // math.factorial(n - k)

def combinations_count(n, k):
    """Number of combinations of n items taken k at a time."""
    return math.comb(n, k)

def multinomial_coefficient(n, *ks):
    """Number of ways to divide n items into groups of sizes k1, k2, ..."""
    total = math.factorial(n)
    for k in ks:
        total //= math.factorial(k)
    return total

# Basic examples
print(f"P(5, 3) = {permutations_count(5, 3)} (arrangements of 3 from 5)")
print(f"C(5, 3) = {combinations_count(5, 3)} (selections of 3 from 5)")

# Multinomial: arrange "MISSISSIPPI"
letters = {'M': 1, 'I': 4, 'S': 4, 'P': 2}
total_letters = sum(letters.values())
multinomial = multinomial_coefficient(total_letters, *letters.values())
print()


 ():
    
     n <= :
         
     math.factorial(n - )

()


 ():
    
     fixed:
         colors ** n
    
     math  gcd
    total = (colors ** gcd(n, k)  k  (, n + ))
     total // ( * n)

()


 ():
    
     math.factorial(n) // math.prod(math.factorial(c)  c  counts)

()

Combinations with Constraints

import math

def combinations_with_restrictions(n, k, restrictions):
    """
    Count combinations with restrictions.
    restrictions: list of (element, condition) where condition is function.
    """
    valid = [i for i in range(1, n + 1) if all(r(i) for r in restrictions)]
    return math.comb(len(valid), k) if len(valid) >= k else 0

def combinations_with_bounds(n, k, lower, upper):
    """Count combinations where each element has bounds."""
    def helper(start, remaining, current_sum):
        if remaining == 0:
            return 1 if lower <= current_sum <= upper else 0
        if current_sum + remaining > upper:
            return 0
        
        total = 0
        for i in range(start, n + 1):
            total += helper(i + 1, remaining - 1, current_sum + i)
        return total
    
    return helper(0, k, 0)


 ():
    
     functools  lru_cache
    

     ():
         k == :
               min_sum <= current_sum <= max_sum  
         i > n  current_sum + k * i > max_sum:
             
        
         dp(i + , k, current_sum) + dp(i + , k - , current_sum + i)
    
     dp(, k, )

()


 ():
    
    valid_count = math.comb(n, k)
     bad_set  forbidden:
         (bad_set) == k:
            valid_count -= 
     valid_count


 ():
    
     itertools  permutations
    
    total_outcomes = math.perm(n_horses, n_places)
    win_outcomes = math.perm(n_horses - , n_places - )
    
     {
        : win_outcomes / total_outcomes,
        : math.comb(n_horses - , n_places - ) / math.comb(n_horses, n_places)
    }


 ():
    
    prob_no_match = 
     i  (n_people):
        prob_no_match *= ( - i) / 
      - prob_no_match

 n  [, , , , ]:
    prob = birthday_problem(n)
    ()

Stars and Bars

import math

def stars_and_bars(n, k):
    """Number of solutions to x1 + ... + xk = n with xi >= 0."""
    return math.comb(n + k - 1, k - 1)

def stars_and_bars_lower_bound(n, k, lower):
    """Number of solutions with xi >= lower."""
    yi = [x - lower for x in [0] * k]  # Transform: yi >= 0
    return stars_and_bars(n - k * lower, k)

def stars_and_bars_bounds(n, k, lower, upper):
    """Number of solutions with lower <= xi <= upper."""
    from functools import lru_cache
    
    @lru_cache(None)
    def dp(i, remaining, current_sum):
        if i == k:
            return 1 if lower * k <= current_sum <= upper * k else 0
        
        total = 0
        for val in range(lower, upper + 1):
            total += dp(i + 1, remaining - 1, current_sum + val)
        return total
    
    return dp(0, k, 0)

# Examples
print(f"Solutions to x+y+z=10 (xi>=0): ")
()
()


 ():
    
     stars_and_bars(n - k, k)

()


 ():
    
     ():
         remaining == :
             (current)
            
         part  ((max_part, remaining), , -):
            current.append(part)
              helper(remaining - part, part, current)
            current.pop()
    
      helper(n, n, [])


 ():
    
     itertools  combinations
    
    total = stars_and_bars(n, k)
    
     i  (, k + ):
         combo  combinations((k), i):
            reduced_n = n - (bounds[j] +   j  combo)
             reduced_n >= :
                sign = -  i %  ==   
                total += sign * stars_and_bars(reduced_n, k)
    
     (, total)

Generating Functions

from collections import defaultdict

class GeneratingFunction:
    def __init__(self, coefficients=None):
        self.coeffs = defaultdict(int)
        if coefficients:
            for i, c in enumerate(coefficients):
                self.coeffs[i] = c
    
    def __add__(self, other):
        result = GeneratingFunction()
        for i in set(list(self.coeffs.keys()) + list(other.coeffs.keys())):
            result.coeffs[i] = self.coeffs[i] + other.coeffs[i]
        return result
    
    def __mul__(self, other):
        result = GeneratingFunction()
        for i, a in self.coeffs.items():
            for j, b in other.coeffs.items():
                result.coeffs[i + j] += a * b
        return result
    
    def __pow__(self, power):
        result = GeneratingFunction([1])
        for _ in range(power):
            result = result * self
        return result
    
    def ():
         .coeffs.get(n, )
    
     ():
         [.coefficient(i)  i  (terms)]


 ():
    
    
    a = GeneratingFunction([, ])  
    b = GeneratingFunction([, -, -])  
    
    
    result = GeneratingFunction([])
    current = GeneratingFunction([])
    
     _  (n):
        result = result + a * current
        current = current * b
    
     result.coefficient(n)


 ():
    phi = ( + **) / 
     ((phi**n - (-phi)**(-n)) / (**))


 ():
    
    
    result = GeneratingFunction([])
    
     k  (, n + ):
        term = GeneratingFunction([] * k + [])  
        result = result * term
    
     result.coefficient(n)


 ():
    
     itertools  product
    
    
    gf = GeneratingFunction([])
    
     coin  coins:
        coin_gf = GeneratingFunction([])
         k  (coin, target + , coin):
            coin_gf.coeffs[k // coin] = 
        gf = gf * coin_gf
    
     gf.coefficient(target)

coins = [, , , ]
()
()
()


 ():
    
     math  factorial
      / factorial(k) * (x**k)**n  

Partition Theory

import math

def partition_number(n):
    """Compute partition number p(n) using recurrence."""
    from functools import lru_cache
    
    @lru_cache(None)
    def p(n, max_part=None):
        if n == 0:
            return 1
        if max_part is None:
            max_part = n
        
        total = 0
        for k in range(min(max_part, n), 0, -1):
            total += p(n - k, k)
        return total
    
    return p(n)

def partition_with_parts(n, parts):
    """Count partitions using only specified parts."""
    from functools import lru_cache
    
    @lru_cache(None)
    def p(remaining, max_part_idx):
        if remaining == 0:
            return 1
        if max_part_idx < 0 or remaining < 0:
            return 
        
        total = 
         i  ((max_part_idx, remaining // parts[max_part_idx]), -, -):
            total += p(remaining - i * parts[max_part_idx], max_part_idx - )
         total
    
     p((parts) - , (parts) - )


 ():
    
     functools  lru_cache
    

     ():
         n == :
             
         n < :
             
        
        total = 
        k = 
         :
            g1 = k * ( * k - ) // 
            g2 = k * ( * k + ) // 
            
             g1 > n  g2 > n:
                
            
            sign = -  k %  ==   
            total += sign * p(n - g1)
             g2 <= n:
                total += sign * p(n - g2)
            
            k += 
        
         total
    
     p(n)


 n  [, , ]:
    ()
    ()


 ():
    
      part:
         []
    
    max_part = (part)
     [(  p  part  p >= i)  i  (, max_part + )]

part = [, , , ]
conj = conjugate_partition(part)
()


 ():
    
     functools  lru_cache
    

     ():
         remaining == :
             
         remaining <   max_part == :
             
         p(remaining, max_part - ) + p(remaining - max_part, max_part - )
    
     p(n, n)

 ():
    
     functools  lru_cache
    

     ():
         remaining == :
             
         remaining <   max_odd < :
             
        
        total = 
         odd  ((max_odd, remaining), , -):
            total += p(remaining - odd, odd)
         total
    
     p(n, n)


 n  [, , ]:
    ()

Best Practices

• Verify combinatorial counting by computing small cases manually to ensure formulas are correct.
• Distinguish between permutations (order matters) and combinations (order doesn't matter) in problem formulation.
• Use generating functions as systematic tools for complex counting problems with multiple constraints.
• Apply stars and bars only when variables are indistinguishable and order doesn't matter.
• Remember that stars and bars requires non-negative integer solutions; transform for lower bounds.
• When counting becomes complex, break into cases and use inclusion-exclusion for overlaps.
• For partition problems, recognize when to use generating functions versus recurrence relations.
• Consider symmetry to reduce computation: conjugate partitions, rotational symmetry in necklaces.
• Use dynamic programming for counting problems with overlapping subproblems to avoid exponential time.
• When probability is involved, combine combinatorial counting with probability axioms rather than counting directly.