Combinatorics — Counting, Permutations, Combinations

Why it matters

Combinatorics appears in many problems. Understanding shapes counting arguments.

The architecture

Permutations: n!/(n-k)! for k from n.

Combinations: n!/(k!(n-k)!).

How it works end to end

Precompute factorials + inverse factorials mod p for O(1) queries.

Catalan: C(2n,n)/(n+1). Counts balanced parens, BSTs, triangulations.

Inclusion-Exclusion: alternating sum over subsets.

Stars and bars: distribute n into k bins.