Concepts318
Category
Game Theory - Calculation Techniques
Sprague–Grundy theory converts any impartial, normal-play game into an equivalent Nim heap using a Grundy number.
Variance and Covariance
Variance measures how spread out a random variable is around its mean, while covariance measures how two variables move together.
Generating Functions - EGF
Exponential generating functions (EGFs) encode a sequence (a_n) as A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}, which naturally models labeled combinatorial objects.
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.
Expected Value
Expected value is the long-run average outcome of a random variable if you could repeat the experiment many times.
Pólya Enumeration
Pólya Enumeration Theorem generalizes Burnside’s Lemma by turning counting under symmetry into a polynomial substitution problem.
Bayes' Theorem
Bayes' Theorem tells you how to update the probability of a hypothesis after seeing new evidence.
Probability Fundamentals
Probability quantifies uncertainty by assigning numbers between 0 and 1 to events in a sample space.
Burnside's Lemma
Burnside's Lemma says the number of distinct objects up to a symmetry group equals the average number of objects fixed by each symmetry.
Partition Function
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
Generating Functions - OGF
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.
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.