Concepts8
Legendre's Formula
Legendre's formula gives the exponent of a prime p in n! by summing how many multiples of p, p^2, p^3, ... are ≤ n.
Linearity of Expectation Applications
Linearity of expectation says the expected value of a sum equals the sum of expected values, even if the variables are dependent.
Pólya Enumeration
Pólya Enumeration Theorem generalizes Burnside’s Lemma by turning counting under symmetry into a polynomial substitution problem.
Probability Fundamentals
Probability quantifies uncertainty by assigning numbers between 0 and 1 to events in a sample space.
Stirling Numbers of First Kind
Stirling numbers of the first kind count permutations by their number of cycles and connect power polynomials to rising/falling factorials.
Catalan Numbers
Catalan numbers count many 'non-crossing' and 'well-formed' structures like balanced parentheses, binary trees, Dyck paths, and triangulations of a convex polygon.
Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.
Stars and Bars
Stars and Bars counts the ways to distribute n identical items into k distinct bins using combinations.