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