combinatorics

What I do

• Calculate permutations and combinations
• Apply binomial coefficients and Pascal's triangle
• Solve recurrence relations
• Count using inclusion-exclusion principle
• Generate combinatorial identities
• Apply generating functions

When to use me

When counting possibilities, analyzing algorithms, or solving probability problems.

Key Concepts

• Permutations: P(n,r) = n!/(n-r)! for ordered arrangements
• Combinations: C(n,r) = n!/(r!(n-r)!) for unordered selections
• Binomial Theorem: (x+y)^n = Σ C(n,k)x^{n-k}y^k
• Pigeonhole Principle: If n items into m boxes and n > m, some box has ≥2
• Recurrence Relations: a_n = f(a_{n-1}, a_{n-2}, ...) with initial conditions
• Generating Functions: G(x) = Σ a_n x^n encodes sequences