Combinatorics & Counting

Permutations, Combinations & Catalan

1:00

Master the six core tools of combinatorics — from the two counting rules through permutations, combinations, Pascal's triangle, stars and bars, and Catalan numbers.

By the end, you can

Identify whether a counting problem requires the rule of sum or the rule of product.
Decide when to use a permutation versus a combination, and apply the correct formula.
Use Pascal's rule to compute binomial coefficients without factorials.
Expand (a + b)ⁿ using the binomial theorem and identify the coefficient of any term.
Apply stars and bars to count non-negative integer solutions of a sum equation.
Compute Catalan numbers and name at least two families of structures they count.
Apply inclusion-exclusion to find the size of a union of overlapping sets.
State the pigeonhole principle and apply it to guarantee a collision.

Up next in String Algorithms, Advanced DP & Competitive Techniques