Ultimate Combinatorics Formulas Cheat Sheet: Master Counting Techniques & Problem-Solving

Introduction: The World of Combinatorics

Combinatorics is the branch of mathematics concerned with counting, arrangement, and combination of objects. It provides powerful tools for analyzing discrete structures and solving counting problems across mathematics, computer science, statistics, and various scientific disciplines. This cheat sheet compiles essential combinatorics formulas, techniques, and problem-solving approaches to help you tackle complex counting problems efficiently.

Core Principles of Combinatorics

• Multiplication Principle: If task A can be done in m ways and task B can be done in n ways, then tasks A and B can be done in m × n ways
• Addition Principle: If task A can be done in m ways and task B can be done in n ways, then either task A or B can be done in m + n ways
• Complementary Counting: Sometimes it’s easier to count what you don’t want and subtract from the total
• Bijection Principle: If there exists a one-to-one correspondence between two sets, they have the same number of elements
• Recursion: Many combinatorial problems can be solved by breaking them down into smaller instances of the same problem

Essential Combinatorial Formulas

Basic Counting Formulas

• Factorial: n! = n × (n-1) × (n-2) × … × 2 × 1

  • 0! = 1 (by definition)
  • Used for counting permutations of distinct objects

• Permutations (ordered arrangements):

  • With repetition: n^r (selecting r elements from n options with repetition allowed)
  • Without repetition: P(n,r) = n!/(n-r)! (selecting and ordering r elements from n distinct elements)

• Combinations (unordered selections):

  • Without repetition: C(n,r) = n!/(r!(n-r)!) = (n r) (binomial coefficient)
  • With repetition: C(n+r-1,r) = (n+r-1)!/(r!(n-1)!) (selecting r elements from n types with repetition)

• Multinomial Coefficient: Permutations of n objects where there are n₁ objects of type 1, n₂ objects of type 2, etc.

  • (n; n₁,n₂,…,nₖ) = n!/(n₁!×n₂!×…×nₖ!)

Advanced Counting Formulas

• Stirling Numbers of the First Kind: s(n,k) = number of permutations of n elements with exactly k cycles

  • Recurrence relation: s(n+1,k) = n×s(n,k) + s(n,k-1)

• Stirling Numbers of the Second Kind: S(n,k) = number of ways to partition n objects into k non-empty subsets

  • S(n,k) = k×S(n-1,k) + S(n-1,k-1)
  • S(n,1) = S(n,n) = 1

• Bell Numbers: B₍ₙ₎ = total number of partitions of a set with n elements

  • B₍ₙ₎ = ∑ₖ₌₁ⁿ S(n,k)
  • B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15

• Catalan Numbers: C₍ₙ₎ = number of valid arrangements of n pairs of parentheses

  • C₍ₙ₎ = (1/(n+1))(2n n) = (2n)!/(n!(n+1)!)
  • C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14

Binomial Theorem and Related Formulas

• Binomial Theorem: (x + y)ⁿ = ∑ₖ₌₀ⁿ (n k)xⁿ⁻ᵏyᵏ

• Binomial Coefficient Properties:

  • (n r) = (n n-r)
  • (n 0) = (n n) = 1
  • (n r) = (n-1 r-1) + (n-1 r) (Pascal’s Identity)
  • ∑ᵏ₌₀ⁿ (n k) = 2ⁿ

• Multinomial Theorem: (x₁ + x₂ + … + xₘ)ⁿ = ∑ (n; k₁,k₂,…,kₘ)x₁ᵏ¹x₂ᵏ²…xₘᵏᵐ

  • Sum over all k₁ + k₂ + … + kₘ = n, where each kᵢ ≥ 0

Recurrence Relations and Generating Functions

• Linear Recurrence Relations: Sequences defined by terms that came before

  • Fibonacci: F₍ₙ₎ = F₍ₙ₋₁₎ + F₍ₙ₋₂₎, with F₀ = 0, F₁ = 1

• Ordinary Generating Function: G(x) = ∑ₙ₌₀∞ aₙxⁿ

  • For Fibonacci: G(x) = x/(1-x-x²)

• Exponential Generating Function: G(x) = ∑ₙ₌₀∞ aₙxⁿ/n!

Step-by-Step Problem-Solving Approaches

1. Permutation Problems

1. Identify whether order matters

   • If order matters, you’re dealing with permutations

2. Determine if repetition is allowed

   • Repetition allowed: use n^r
   • No repetition: use P(n,r) = n!/(n-r)!

3. Check for identical objects

   • If some objects are identical, use multinomial coefficients

4. Example: Arranging 5 distinct books on a shelf

   • P(5,5) = 5! = 120 possible arrangements

2. Combination Problems

1. Identify whether order doesn’t matter

   • If order doesn’t matter, you’re dealing with combinations

2. Determine if repetition is allowed

   • No repetition: use C(n,r) = n!/(r!(n-r)!)
   • Repetition allowed: use C(n+r-1,r)

3. Example: Selecting 3 flavors from 8 ice cream options

   • C(8,3) = 8!/(3!×5!) = 56 possible selections

3. Distribution/Partition Problems

1. Identify objects and containers

   • Determine if objects are distinct or identical
   • Determine if containers are distinct or identical

2. Determine constraints

   • Are empty containers allowed?
   • Are there minimum/maximum objects per container?

3. Select appropriate formula

   • Distinct objects, distinct containers: multinomial coefficient
   • Identical objects, distinct containers: C(n+k-1,k-1)
   • Distinct objects, identical containers: Stirling numbers (second kind)
   • Identical objects, identical containers: partition numbers

4. Example: Distributing 10 identical candies to 4 children

   • C(10+4-1,4-1) = C(13,3) = 286 ways

4. Recursion and Dynamic Programming Approach

1. Identify base cases

   • Solve smallest instances directly

2. Establish recurrence relation

   • Express solution in terms of smaller subproblems

3. Use memoization or tabulation

   • Store solutions to avoid redundant calculations

4. Example: Counting ways to climb n stairs taking 1 or 2 steps at a time

   • Base cases: f(1) = 1, f(2) = 2
   • Recurrence: f(n) = f(n-1) + f(n-2) for n > 2

Comparison Tables for Related Concepts

Permutations vs. Combinations

Distribution Problem Types

Special Number Sequences in Combinatorics

Common Challenges and Solutions

Challenge: Overcounting or Undercounting

• Solution: Use PIE (Principle of Inclusion-Exclusion) for overlapping cases
• Solution: Check boundary conditions and edge cases carefully
• Solution: Double-check whether objects are distinct or identical

Challenge: Handling Constraints

• Solution: Use complementary counting when constraints are complex
• Solution: Break down into cases based on key variables
• Solution: Translate constraints into equations (e.g., x₁ + x₂ + … + xₙ = k)

Challenge: Recurrence Relations Seem Too Complex

• Solution: Look for pattern simplifications
• Solution: Try generating functions
• Solution: Use known sequences and their properties

Challenge: Difficulty with Double Counting

• Solution: Count from different perspectives and verify equality
• Solution: Use bijection arguments to establish correspondence
• Solution: Apply combinatorial identities to simplify expressions

Challenge: Combinatorial Proof Complexity

• Solution: Use smaller examples to verify pattern
• Solution: Try algebraic and combinatorial approaches separately
• Solution: Break problem into clearer subproblems

Best Practices and Practical Tips

• Start with small examples to understand patterns and verify formulas
• Check answers using different counting methods when possible
• Simplify expressions using combinatorial identities
• Draw tree diagrams to visualize complex counting problems
• Use symmetry to reduce computational complexity
• Apply the PIE systematically for problems involving restrictions
• Break complex problems into stages or cases
• Use recursion when direct formulas are not obvious
• Build a toolkit of standard problems and their solutions
• Develop intuition by solving many practice problems

Advanced Techniques

The Principle of Inclusion-Exclusion (PIE)

• For sets A₁, A₂, …, Aₙ:
• |A₁ ∪ A₂ ∪ … ∪ Aₙ| = ∑ᵢ |Aᵢ| – ∑ᵢ<ⱼ |Aᵢ ∩ Aⱼ| + ∑ᵢ<ⱼ<ₖ |Aᵢ ∩ Aⱼ ∩ Aₖ| – … + (-1)ⁿ⁺¹|A₁ ∩ A₂ ∩ … ∩ Aₙ|

Burnside’s Lemma/Pólya Enumeration

• For counting distinct arrangements under group action
• |X/G| = (1/|G|) ∑ₐₑG |Xᵃ|, where Xᵃ are elements fixed by action a

Generating Functions

• Ordinary: G(x) = ∑ₙ₌₀∞ aₙxⁿ
• Exponential: G(x) = ∑ₙ₌₀∞ aₙxⁿ/n!
• Useful for solving recurrence relations and counting with constraints

Resources for Further Learning

Books

• Concrete Mathematics by Graham, Knuth, and Patashnik
• A Course in Combinatorics by van Lint and Wilson
• Enumerative Combinatorics by Richard Stanley
• Combinatorial Problems and Exercises by László Lovász

Online Resources

• OEIS (The On-Line Encyclopedia of Integer Sequences)
• MIT OpenCourseWare: Mathematics for Computer Science
• Art of Problem Solving: Combinatorics resources
• Brilliant.org: Combinatorics courses and problems

Problem Collections

• IMO (International Mathematical Olympiad) problems
• Putnam Competition problems
• Project Euler combinatorial problems
• Combinatorial puzzles by Martin Gardner

Software Tools

• Mathematica: Combinatorial functions
• SageMath: Open-source mathematics software
• Python with SymPy for symbolic mathematics
• OEIS database search tools

Remember that combinatorics often requires creative thinking beyond formula application. When tackling a new problem, try multiple approaches, look for patterns in small cases, and leverage known results from similar problems. With practice, you’ll develop stronger combinatorial intuition and problem-solving skills.