Search & glossary

Every rule and concept in Counting & Probability, with its definition and a link to the lesson that teaches it. Search by term, by idea, or by lesson title.

Glossary (176)

$D_n$ Is the Nearest Integer to $n!/e$: The Maclaurin series $e^{-1}=\sum_{k\ge 0}\tfrac{(-1)^k}{k!}$ truncated at $k=n$ is exactly $D_n/n!$ .; Inclusion–Exclusion, Derangements & Pigeonhole › Derangement Asymptotics: The Nearest–Integer Rule
Absorption & Lattice Paths: \[ k $\binom{n}{k}$ =n $\binom{n-1}{k-1}$ ; paths (0,0)→(m,n) (R/U steps)= $\binom{m+n}{m}$ .; Course Review › Binomial Theorem & Identities
Addition & Multiplication Principles: Multiplication (AND).; Course Review › Fundamental Counting
Arrangements when some items repeat: The number of distinct arrangements of $n$ objects, where there are $n_1$ identical objects of type 1, $n_2$ of type 2, …, $n_r$ of type $r$ (with $n_1 + \cdots + n_r = n$ ), is the multinomial coefficient \[ $\frac{n!}{n_1!\,n_2!\cdots n_r!}$ .; Fundamental Counting: Permutations & Combinations › Permutations with Identical Objects
Averaging in stages: The conditional expectation $E[X\mid Y]$ is the average of $X$ once the value of $Y$ is known; it is itself a random variable (a function of $Y$ ).; Expected Value, Linearity & Advanced Probability › Conditional Expectation & the Tower Property
Bayes as a multiplier on odds: Write Bayes' theorem for two competing hypotheses $H$ and its complement $H^c$ and divide the two versions.; Conditional Probability, Independence & Bayes › The Odds Form of Bayes & Sequential Updating
Bayes' Theorem: \[ P(B A)= $\frac{P(A\mid B)\,P(B)}{P(A)}$ = $\frac{P(A\mid B)P(B)}{\sum_i P(A\mid B_i)P(B_i)}$ .; Course Review › Conditional Probability & Bayes
Belief as something you update: Bayesian updating treats probability as a state of belief refined by evidence.; Conditional Probability, Independence & Bayes › Going Deeper: Bayesian Updating, Conditioning, and Ambiguity
Bell Numbers $B_0$ – $B_6$: \[; Course Review › Advanced Expectation & Markov Chains
Bijections: If a set is hard to count, find a one-to-one correspondence with a set you can count; equal sizes.; Course Review › Counting Strategies
Binomial coefficients with any upper index: Define, for any real (or complex) $\alpha$ and integer $k\ge 0$ , \[ $\binom{\alpha}{k}$ = $\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}$ .; Binomial Theorem, Pascal & Combinatorial Identities › The Generalized Binomial Series
Binomial Theorem: \[ (x+y)^n=∑_k=0^n $\binom{n}{k}$ x^n-ky^k.; Course Review › Binomial Theorem & Identities
Bounded Variables (inclusion–exclusion): For upper bounds like $x_i \le c_i$ , subtract the “overflow” cases with inclusion–exclusion (give a violating variable $c_i+1$ units, then recount).; Course Review › Distributions: Stars & Bars
Break an event across a partition of causes: Let $B_1,B_2,\dots,B_n$ partition the sample space (disjoint, together all outcomes, each $P(B_i)>0$ ).; Conditional Probability, Independence & Bayes › The Law of Total Probability
Burnside's Lemma (counting up to symmetry): The number of distinct configurations under a symmetry group $G$ equals the average number of colorings fixed by each group element: \[ #orbits= $\frac{1}{|G|}$ ∑_g∈ G|Fix(g)|.; Course Review › Advanced Reference
Casework: Split into disjoint, exhaustive cases; count each; add.; Course Review › Counting Strategies
Catalan Interpretations & Closed Form: \[ C_n= $\frac{1}{n+1}$ $\binom{2n}{n}$ = $\binom{2n}{n}$ - $\binom{2n}{n-1}$ .; Course Review › Advanced Reference
Catalan Numbers: \[ C_n= $\frac{1}{n+1}$ $\binom{2n}{n}$ = $\binom{2n}{n}$ - $\binom{2n}{n+1}$ , C_n+1=∑_i=0^nC_i C_n-i.; Course Review › Recursion, Catalan & Generating Functions
Catalan numbers $C_0$ – $C_8$ and Derangements $D_0$ – $D_6$: \[; Course Review › Reference Tables
Chaining conditional probabilities: Solving $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$ for the intersection gives the multiplication rule: \[ P(A∩ B) = P(B) P(A B).; Conditional Probability, Independence & Bayes › The Multiplication Rule & Probability Trees
Choosing what to case on: Two cases are not equal in quality.; Counting Strategies: Casework, Complementary & Overcounting › Systematic Casework and Generating Functions
Circular Permutations: Arrangements around a circle count only relative position (fix one seat to remove $n$ rotations): \[ (n-1)!; if reflections also identical (bracelet): $\frac{(n-1)!}{2}$ (n≥ 3).; Course Review › Fundamental Counting
Combinations (order doesn't matter): Choose $k$ of $n$ distinct objects, ignoring order: \[ $\binom{n}{k}$ = $\frac{n!}{k!\,(n-k)!}$ = $\frac{P(n,k)}{k!}$ , $\binom{n}{k}$ = $\binom{n}{n-k}$ .; Course Review › Fundamental Counting
Complementary Counting: Count the opposite and subtract from the total: $|E| = |S| - |E^c|$ .; Course Review › Counting Strategies
Condition on the first move to set up equations: First-step analysis solves “how long / how likely” questions on a chain by conditioning on the very first transition and using the memoryless property: after one step the problem looks like the same problem from the new state.; Conditional Probability, Independence & Bayes › First-Step Analysis & Conditional Expectation (Unit 9 Preview)
Conditional Probability: \[ P(A B)= $\frac{P(A\cap B)}{P(B)}$ , P(B)>0.; Course Review › Conditional Probability & Bayes
Conditioning on the first step: When a process repeats until something happens, set up an equation for the expected value by conditioning on the first step.; Expected Value, Linearity & Advanced Probability › Expected Value via States & Recursion
Constructive Counting: Build a valid object step by step, multiplying the choices available at each step (keep the count per step constant, or split into cases).; Course Review › Counting Strategies
Correcting for symmetry: a Burnside flavor: When simple division fails because some arrangements are fixed by a symmetry, use the Burnside idea: the number of distinct arrangements equals the average number of arrangements left unchanged by each symmetry: \[ #(distinct) = $\frac{1}{|G|}$ ∑_g…; Counting Strategies: Casework, Complementary & Overcounting › Going Deeper: Combining Strategies
Correcting Overcounting (divide by symmetry): Count an easy ordered/labeled way, then divide by the symmetries you introduced: rotations ( $\div n$ ), reflections ( $\div 2$ ), interchangeable groups ( $\div k!$ ).; Course Review › Counting Strategies
Count a hard set by matching it to an easy one: If there is a bijection (a one-to-one, onto pairing) between a finite set $A$ and a finite set $B$ , then $|A| = |B|$ .; Fundamental Counting: Permutations & Combinations › The Bijection Principle
Count the opposite instead: The complement $E^c$ is the event “ $E$ does not happen.” Since $E$ and $E^c$ partition $S$ , \[ P(E) + P(E^c) = 1 P(E) = 1 - P(E^c).; Probability Fundamentals & Geometric Probability › Complementary Probability
Counting a Union Without Double–Counting: When two sets overlap, adding their sizes counts the overlap twice, so subtract it once: $ $\boxed{\,|A\cup B| = |A| + |B| - |A\cap B|\,}$ $For three sets, add the singles, subtract the pairs, add back the triple:$ $|A∪ B∪ C| = |A|+|B|+|C| - |A∩ B| …; Inclusion–Exclusion, Derangements & Pigeonhole › Two– and Three–Set Inclusion–Exclusion
Counting Elements in Exactly (or At Least) $m$ Sets: Let $S_j = \sum_{|T|=j}\bigl|\bigcap_{i\in T}A_i\bigr|$ be the $j$ -th symmetric sum of intersection sizes ( $S_0=|U|$ ).; Inclusion–Exclusion, Derangements & Pigeonhole › Exactly $m$ Sets: The Bonferroni Refinement
Counting integer solutions of an equation: The number of nonnegative integer solutions $(x_1,\dots,x_k)$ to \[ x_1+x_2+…+x_k=n, x_i≥ 0 \] is $\displaystyle\binom{n+k-1}{k-1}$ .; Distributions: Stars & Bars and Integer Solutions › Nonnegative vs. Positive Integer Solutions
Counting monotonic lattice paths: The number of lattice paths from the origin $(0,0)$ to $(m,n)$ using only unit steps right ( $R$ ) and up ( $U$ ) is \[ $\binom{m+n}{m}$ = $\binom{m+n}{n}$ .; Binomial Theorem, Pascal & Combinatorial Identities › Lattice Path Counting
Counting the complement of a union: The strongest complementary arguments subtract a union of bad events, and unions are handled by inclusion–exclusion: \[ | A_1∪…∪ A_n | = N - ∑_i |A_i| + ∑_i<j|A_i∩ A_j| - … + (-1)^n |A_1∩…∩ A_n|.; Counting Strategies: Casework, Complementary & Overcounting › Complementary Counting Meets Inclusion–Exclusion
Counting tools power the ratio: For selection problems, $|S|$ and $|E|$ are themselves permutation or combination counts.; Probability Fundamentals & Geometric Probability › Probability with Permutations & Combinations
Counting with states: When the next choice depends on the current situation, define one sequence per state and let them recurse together.; Recursion, Catalan Numbers & Generating Functions › State-Based Counting Recursions
Counting-Based Probability: Compute favorable and total outcomes with the same counting rules (order-consistent on both).; Course Review › Probability Fundamentals
Cue $\rightarrow$ Technique decision guide: Course Review › Problem-Solving Playbook
Definition: \[ E[X]=∑_x x P(X=x).; Course Review › Expected Value
Derangement Nearest-Integer Formula: Since $D_n=n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ converges to $n!/e$ fast, \[ D_n= $\frac{n!}{e}$ +12 (n≥ 1).; Course Review › Advanced Reference
Derangements (no fixed points): \[ D_n=n!∑_k=0^n $\frac{(-1)^k}{k!}$ =(n-1)(D_n-1+D_n-2), D_n≈ $\frac{n!}{e}$ .; Course Review › Inclusion–Exclusion, Derangements & Pigeonhole
Direct, cases, or complement?: Three ways to count, in order of preference: directly (multiply choices), by cases (split cleanly, add), or by complement (count what you don't want, subtract).; Core Ideas in Plain Terms › Problem-Solving Playbook
Distributing balls into boxes — the master chart: Almost every elementary counting problem is “put $n$ balls into $m$ boxes.” The answer depends on two switches — are the balls distinguishable?; Fundamental Counting: Permutations & Combinations › Orientation: The Twelvefold Way
Distributions as coefficients: Each box contributes a factor recording what it can hold; multiplying the factors and reading off the coefficient of $x^{n}$ counts the distributions summing to $n$ .; Distributions: Stars & Bars and Integer Solutions › The Generating-Function View of Stars and Bars
Does one event change the other?: Events $A$ and $B$ are independent if knowing one occurred does not change the probability of the other.; Probability Fundamentals & Geometric Probability › Independent vs. Dependent Events (Basic)
Does order matter?: If rearranging counts as different (a race finish, a seating), use permutations: ${}_nP_k = \tfrac{n!}{(n-k)!}$ .; Core Ideas in Plain Terms › Arrangements vs. Selections
Drawing a partition; the conjugate: A partition $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_m\ge 1$ of $n$ is drawn as a Ferrers diagram: left-justified rows of dots, row $i$ having $\lambda_i$ dots.; Distributions: Stars & Bars and Integer Solutions › Integer Partitions and Ferrers Diagrams
EGFs for labeled structures: When objects are built on labeled elements (people, positions $1..n$ that are distinguishable), the right bookkeeping tool is the exponential generating function \[ A(x)=∑_n≥0a_n $\frac{x^n}{n!}$ .; Recursion, Catalan Numbers & Generating Functions › Exponential Generating Functions
Encoding a distribution in a single function: For a nonnegative integer-valued $X$ , its probability generating function (PGF) packs all the probabilities into one power series: \[ G_X(s)=E[s^X]=∑_k≥ 0P(X=k) s^k .; Expected Value, Linearity & Advanced Probability › Probability Generating Functions & the Tail-Sum Formula
Equally Likely Outcomes: \[ P(E)= $\frac{|E|}{|S|}$ , 0≤ P(E)≤ 1, P(E^c)=1-P(E).; Course Review › Probability Fundamentals
Equally likely outcomes make probability into counting: The formula $P(E)=|E|/|S|$ is not a definition of probability in general — it is a theorem about the special case of equally likely outcomes.; Probability Fundamentals & Geometric Probability › Going Deeper: Why Probability Is Counting, and the Meeting Problem
Every function is an assignment; count the assignments: Let $|X| = n$ (the domain) and $|Y| = m$ (the codomain).; Fundamental Counting: Permutations & Combinations › Counting Functions Between Finite Sets
Expectation adds — always: For any random variables $X$ and $Y$ defined on the same experiment, \[ E[X+Y]=E[X]+E[Y], \] and more generally $E\!\left[\sum_i X_i\right]=\sum_i E[X_i]$ .; Expected Value, Linearity & Advanced Probability › Linearity of Expectation
Expectation Toolkit: Beyond linearity and indicators ( $E[\sum X_i]=\sum P(\text{event }i)$ ), for a nonnegative integer $X$ use the tail sum: \[ E[X]=∑_k≥ 1P(X≥ k), Var(X)=E[X^2]-E[X]^2.; Course Review › Advanced Expectation & Markov Chains
Expectation via States / Recursion: Let $E$ be the expected value from a state; condition on the next step and solve the resulting equation(s).; Course Review › Expected Value
Expected value is the long-run average: The expected value formula is $E = \sum \big(\text{outcome} \times \text{probability}\big)$ : multiply each outcome by its probability and add.; Core Ideas in Plain Terms › Going Deeper: Complements and Expected Value
Expected wait for a first success: Repeat independent trials, each succeeding with probability $p>0$ .; Expected Value, Linearity & Advanced Probability › Waiting Times & the Geometric Distribution
Extracting an arithmetic slice of a row: Let $\omega=e^{2\pi i/m}$ be a primitive $m$ th root of unity.; Binomial Theorem, Pascal & Combinatorial Identities › The Roots of Unity Filter
Factorials $0!$ through $10!$: \[; Course Review › Reference Tables
Favorable over total: For equally likely outcomes, the probability of an event is given by the classical probability formula $P(A) = \dfrac{\text{favorable outcomes}}{\text{total outcomes}}$ .; Core Ideas in Plain Terms › Probability
Fibonacci from tilings: The Fibonacci numbers satisfy \[ f_n=f_n-1+f_n-2, f_1=f_2=1, \] giving $1,1,2,3,5,8,13,21,34,55,\dots$ Many tiling problems reduce to this.; Recursion, Catalan Numbers & Generating Functions › Fibonacci & Tiling / Domino Problems
First-Step Analysis & Gambler's Ruin: Define hitting probabilities/times per state and condition on the first step.; Course Review › Advanced Expectation & Markov Chains
Generalized Binomial Series: For any real (or complex) $\alpha$ with $|x|<1$ , and the negative-power expansion: \[ (1+x)^α=∑_k≥ 0 $\binom{\alpha}{k}$ x^k, 1(1-x)^k=∑_n≥ 0 $\binom{n+k-1}{k-1}$ x^n.; Course Review › Advanced Reference
Generating Functions: Encode a sequence $a_n$ as coefficients of $\sum a_n x^n$ ; products of series combine choices.; Course Review › Recursion, Catalan & Generating Functions
Generating functions as bookkeeping: A generating function replaces casework with algebra: the number of ways to choose objects with a target total is a coefficient in a product of polynomials/series.; Counting Strategies: Casework, Complementary & Overcounting › Systematic Casework and Generating Functions
Geometric Probability: When outcomes fill a continuous region, probability is a ratio of measures (length, area, volume): \[ P=measure of favorable regionmeasure of sample region.; Course Review › Probability Fundamentals
Hockey Stick: \[ ∑_i=r^n $\binom{i}{r}$ = $\binom{n+1}{r+1}$ .; Course Review › Binomial Theorem & Identities
Hockey Stick Identity: \[ ∑_i=r^n $\binom{i}{r}$ = $\binom{n+1}{r+1}$ .; Binomial Theorem, Pascal & Combinatorial Identities › The Hockey Stick Identity
Inclusion–Exclusion (PIE): \[ |_i A_i|=∑|A_i|-∑|A_i∩ A_j|+∑|A_i∩ A_j∩ A_k|-… \] Ex.; Course Review › Inclusion–Exclusion, Derangements & Pigeonhole
Inclusion–Exclusion and Euler's Totient: Euler's totient $\varphi(n)$ counts integers in $\{1,\dots,n\}$ coprime to $n$ .; Inclusion–Exclusion, Derangements & Pigeonhole › Going Deeper: Connections & Advanced Tools
Independence: Events are independent iff \[ P(A∩ B)=P(A) P(B).; Course Review › Probability Fundamentals
Indicator Variables: Let $X_i=1$ if event $i$ occurs, else $0$ ; then $E[X_i]=P(\text{event }i)$ and $E[\#\text{events}]=\sum P(\text{event }i)$ .; Course Review › Expected Value
Key Weighted & Squared Sum Identities: \[ ∑_k=0^n k $\binom{n}{k}$ =n 2^n-1, ∑_k=0^n $\binom{n}{k}$ ^2= $\binom{2n}{n}$ , \] and Vandermonde $\displaystyle\sum_{k}\binom{m}{k}\binom{n}{p-k}=\binom{m+n}{p}$ (the squared sum is its $m=n=p$ case).; Course Review › Advanced Reference
Law of Total Probability: For a partition $B_1,\dots,B_n$ of the sample space: \[ P(A)=∑_i P(A B_i) P(B_i).; Course Review › Conditional Probability & Bayes
Layering techniques: Contest problems rarely use one idea in isolation.; Counting Strategies: Casework, Complementary & Overcounting › Going Deeper: Combining Strategies
Layering the tools: Contest problems rarely use one idea in isolation.; Distributions: Stars & Bars and Integer Solutions › Going Deeper: Techniques That Combine
Let symmetry do the counting: When outcomes are interchangeable, symmetry pins down probabilities and expectations with almost no computation.; Expected Value, Linearity & Advanced Probability › Symmetry Arguments
Let the problem's symmetry do the counting: Often the cleanest probability argument computes nothing: instead you observe that several outcomes must, by symmetry, be equally likely, and read the answer off directly.; Probability Fundamentals & Geometric Probability › Symmetry & Bijection Arguments
Linearity of Expectation: Always true, even for dependent variables: \[ E[X_1+…+X_n]=E[X_1]+…+E[X_n].; Course Review › Expected Value
Measuring spread with $\mathrm{Var}(X)$: The variance of $X$ measures how far $X$ typically strays from its mean $\mu=E[X]$ : \[ Var(X)=E[(X-μ)^2]=E[X^2]-(E[X])^2 .; Expected Value, Linearity & Advanced Probability › Variance & the Second Moment
Memoryless step-by-step randomness: A Markov chain moves among states $1,\dots,m$ so that the next state depends only on the current one, not the past history: \[ P(X_n+1=j X_n=i, X_n-1,…)=P(X_n+1=j X_n=i)=:p_ij.; Conditional Probability, Independence & Bayes › Markov Chains & Transition Matrices
Multinomial Coefficients (distinct items): Split $n$ distinct items into labeled groups of sizes $n_1,\dots,n_r$ : \[ $\binom{n}{n_1,n_2,\dots,n_r}$ = $\frac{n!}{n_1!\,n_2!\cdots n_r!}$ .; Course Review › Distributions: Stars & Bars
Multiplication Rule: \[ P(A∩ B)=P(A) P(B A)=P(B) P(A B).; Course Review › Conditional Probability & Bayes
Multiply independent choices: When you make several choices that don't affect each other, multiply the number of options.; Core Ideas in Plain Terms › The Counting Principle
Necklaces vs. circular arrangements: A circular arrangement treats only rotations as identical: $(n-1)!$ .; Fundamental Counting: Permutations & Combinations › Going Deeper: Subtleties, Overcounting & Symmetry
Nonnegative Integer Solutions: The number of solutions to $x_1+x_2+\cdots+x_k=n$ with each $x_i\ge 0$ (identical items into distinct boxes) is \[ $\binom{n+k-1}{k-1}$ = $\binom{n+k-1}{n}$ .; Course Review › Distributions: Stars & Bars
Odds-Form Bayes: Updating hypothesis $H$ against $\bar H$ on evidence $E$ multiplies prior odds by the likelihood ratio: \[ $\frac{P(H\mid E)}{P(\bar H\mid E)}$ = $\frac{P(H)}{P(\bar H)}$ · $\frac{P(E\mid H)}{P(E\mid \bar H)}$ .; Course Review › Advanced Expectation & Markov Chains
One coefficient, three readings: For nonnegative integers with $k_1 + k_2 + \cdots + k_r = n$ , define \[ $\binom{n}{k_1,\,k_2,\,\dots,\,k_r}$ = $\frac{n!}{k_1!\,k_2!\cdots k_r!}$ .; Fundamental Counting: Permutations & Combinations › The Multinomial Coefficient as a Distribution
One permutation, many statistics — all by indicators: A uniformly random permutation $a_1,a_2,\dots,a_n$ of $\{1,\dots,n\}$ hides a zoo of natural statistics.; Expected Value, Linearity & Advanced Probability › Linearity Masterclass: Records, Inversions & Cycles
One table for every distribution problem: Placing $n$ balls into $k$ boxes has $2\times2\times3=12$ variants: balls identical or distinct, boxes identical or distinct, and the map unrestricted / injective (“at most one per box”) / surjective (“no box empty”).; Distributions: Stars & Bars and Integer Solutions › The Twelvefold Way
Onto Functions via Inclusion–Exclusion: The number of surjections (onto functions) from an $n$ –element set onto a $k$ –element set is found by excluding the maps that miss at least one target value: $ $\boxed{\,\operatorname{Surj}(n,k) = \sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n.}$ $ This also count…; Inclusion–Exclusion, Derangements & Pigeonhole › Counting Surjections (Onto Functions)
Order Forced by Size: $R(3,3)=6$: Color the edges of a complete graph on $n$ vertices with two colors (say, acquainted / stranger).; Inclusion–Exclusion, Derangements & Pigeonhole › Ramsey Numbers & Probabilistic Pigeonhole
Ordered and unordered ways to break up $n$: A composition of $n$ is an ordered sequence of positive parts summing to $n$ ; a partition is the same but order is ignored.; Distributions: Stars & Bars and Integer Solutions › Compositions vs. Partitions
Ordered arrangements: $n!; Fundamental Counting: Permutations & Combinations › Factorials & Permutations
Particular $+$ homogeneous, with resonance: A linear recurrence with a forcing term, \[ a_n=c_1a_n-1+…+c_ka_n-k+g(n), \] is solved by \[ a_n = a_n^(h) + a_n^(p), \] where $a_n^{(h)}$ is the general solution of the homogeneous part (characteristic roots, as before) and $a_n^{(p)}$ …; Recursion, Catalan Numbers & Generating Functions › Nonhomogeneous & Higher-Order Linear Recurrences
Partitioning a Set into Blocks: The Stirling number of the second kind $S(n,k)$ counts the ways to partition an $n$ –element set into exactly $k$ nonempty, unlabeled blocks.; Inclusion–Exclusion, Derangements & Pigeonhole › Stirling Numbers of the Second Kind & Bell Numbers
Pascal's Rule: \[ $\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$ .; Binomial Theorem, Pascal & Combinatorial Identities › Pascal's Triangle & Pascal's Rule
Pascal's Rule: \[ $\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$ .; Course Review › Binomial Theorem & Identities
Pascal's Triangle (rows $n=0$ to $8$ ): \[; Course Review › Reference Tables
Permutations (order matters, no repeats): Arrange $k$ of $n$ distinct objects in ordered slots: \[ P(n,k)= $\frac{n!}{(n-k)!}$ =n(n-1)…(n-k+1), P(n,n)=n!.; Course Review › Fundamental Counting
Permutations with Identical Objects (multinomial): Arrange $n$ objects with $n_i$ copies of type $i$ ( $\sum n_i = n$ ): \[ $\frac{n!}{n_1!\,n_2!\cdots n_r!}$ .; Course Review › Fundamental Counting
Permutations With No Fixed Point: A derangement is a permutation in which no element stays in its original position.; Inclusion–Exclusion, Derangements & Pigeonhole › Derangements
Pick the right measure: length, area, or volume: Uniform random points still give $P(E) = \dfrac{\text{measure of favorable region}}{\text{measure of whole region}}$ , but in $2$ or $3$ variables the “measure” is an area or a volume.; Probability Fundamentals & Geometric Probability › Higher-Dimensional Geometric Probability
Pigeonhole in Number Theory & Geometry: Number theory.; Inclusion–Exclusion, Derangements & Pigeonhole › Going Deeper: Connections & Advanced Tools
Pigeonhole Principle: Place $n$ items into $k$ boxes: some box holds at least $\left\lceil \dfrac{n}{k}\right\rceil$ items (basic case: $n>k \Rightarrow$ a box has $\ge 2$ ).; Course Review › Inclusion–Exclusion, Derangements & Pigeonhole
Positive Integer Solutions: For $x_i\ge 1$ , give each variable one unit first ( $y_i=x_i-1\ge 0$ ): \[ $\binom{n-1}{k-1}$ .; Course Review › Distributions: Stars & Bars
Probability as a ratio of measures: When an outcome is a uniformly random point in a region — a spot on a segment, an instant in a time interval, a dart in a target — the sample space is continuous and we replace counting with measure: \[ P(E) = length of favorable interval…; Probability Fundamentals & Geometric Probability › Geometric Probability (Length & Area)
Probability is a counting ratio: Once outcomes are equally likely, every probability question is two counting questions: count $|E|$ (favorable) and count $|S|$ (total), then divide.; Probability Fundamentals & Geometric Probability › Probability as Favorable over Total (Counting-Based)
Probability of a union of many events: For any events $A_1,\dots,A_n$ , the probability that at least one occurs is \[ P (_i=1^n A_i) = ∑_i P(A_i) - ∑_i<j P(A_i∩ A_j) + ∑_i<j<k P(A_i∩ A_j∩ A_k) - … + (-1)^n+1 P (_i=1^n A_i).; Probability Fundamentals & Geometric Probability › Inclusion–Exclusion for Probability & the Union Bound
Probability once you already know something: The conditional probability of $A$ given that $B$ has occurred is \[ P(A B) = $\frac{P(A\cap B)}{P(B)}$ , P(B) > 0.; Conditional Probability, Independence & Bayes › Conditional Probability $P(A\mid B)$
Reaching $N$ before $0$: A gambler holding $\$k$ bets $\$1$ per round, winning with probability $p$ and losing with probability $q=1-p$ , until reaching a target $\$N$ (win) or $\$0$ (ruin).; Conditional Probability, Independence & Bayes › Gambler's Ruin
Reading a proof: Do not read a proof the way you read a rule.; Fundamental Counting: Permutations & Combinations › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Counting Strategies: Casework, Complementary & Overcounting › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Distributions: Stars & Bars and Integer Solutions › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Binomial Theorem, Pascal & Combinatorial Identities › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Inclusion–Exclusion, Derangements & Pigeonhole › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Recursion, Catalan Numbers & Generating Functions › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Probability Fundamentals & Geometric Probability › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Conditional Probability, Independence & Bayes › Why It Works
Reading a proof: Do not read a proof the way you read a rule.; Expected Value, Linearity & Advanced Probability › Why It Works
Recurrences as matrix powers: A coupled linear recurrence among finitely many states is one matrix $T$ acting on a state vector.; Recursion, Catalan Numbers & Generating Functions › The Transfer-Matrix Method
Recursion & Fibonacci Tilings: Set up $a_n$ from smaller cases by conditioning on the last choice.; Course Review › Recursion, Catalan & Generating Functions
Reversing the conditioning: Combining $P(B_i\cap A)=P(A\mid B_i)P(B_i)$ with the law of total probability gives Bayes' Theorem: \[ P(B_i A) = P(A B_i) P(B_i)∑_j P(A B_j) P(B_j) = $\frac{P(A\mid B_i)\,P(B_i)}{P(A)}$ .; Conditional Probability, Independence & Bayes › Bayes' Theorem
Roots of Unity Filter: To sum binomial coefficients over $k$ in one residue class mod $m$ , average $(1+\omega^j)^n$ over the $m$ -th roots of unity $\omega=e^{2\pi i/m}$ : \[ ∑_k≡ r (m) $\binom{n}{k}$ = $\frac{1}{m}$ ∑_j=0^m-1ω^-jr(1+ω^j)^n.; Course Review › Advanced Reference
Rotation counting and the general ballot theorem: The reflection principle is one proof of the Catalan/ballot counts; the cycle lemma is a slicker, purely combinatorial one.; Recursion, Catalan Numbers & Generating Functions › The Cycle Lemma & the Ballot Problem
Row Sums: \[ ∑_k=0^n $\binom{n}{k}$ =2^n, ∑_k=0^n(-1)^k $\binom{n}{k}$ =0 (n≥ 1).; Course Review › Binomial Theorem & Identities
Seating around a table: Arrangements around a circle count only relative position: rotating everyone one seat gives the same arrangement.; Fundamental Counting: Permutations & Combinations › Circular Permutations
Series as bookkeeping devices: A (ordinary) generating function packages a sequence $a_0,a_1,a_2,\dots$ into one formal power series \[ A(x)=∑_n≥ 0a_n x^n .; Recursion, Catalan Numbers & Generating Functions › Generating Functions (introduction)
Signature techniques of advanced expectation: The four moves below appear again and again in olympiad and AMC/AIME problems:; Expected Value, Linearity & Advanced Probability › Going Deeper: Where These Ideas Combine
Solving Linear Recurrences (characteristic roots): For $a_n=c_1 a_{n-1}+\cdots+c_d a_{n-d}$ , solve $x^{d}=c_1 x^{d-1}+\cdots+c_d$ .; Course Review › Advanced Reference
Solving Recurrences (generating functions): Multiply the recurrence by $x^n$ , sum over $n$ , and solve for $A(x)=\sum a_n x^n$ as a rational function; expand via partial fractions and $\frac{1}{(1-rx)^{m}}$ to read off $a_n$ .; Course Review › Advanced Reference
Splitting distinct objects into fixed-size groups: The number of ways to partition $n$ distinct objects into labeled groups of sizes $n_1,n_2,\dots,n_k$ (with $n_1+\cdots+n_k=n$ ) is the multinomial coefficient \[ $\binom{n}{n_1,\,n_2,\,\dots,\,n_k}$ = $\frac{n!}{n_1!\,n_2!\cdots n_k!}$ .; Distributions: Stars & Bars and Integer Solutions › Multinomial Coefficients
Stationary Distribution: A distribution $\pi$ is stationary for transition matrix $P$ when it is unchanged by a step: \[ π P=π, ∑_i π_i=1.; Course Review › Advanced Expectation & Markov Chains
Stirling Numbers (2nd kind) & Bell Numbers: $S(n,k)$ partitions an $n$ -set into $k$ nonempty unlabeled blocks; Bell number $B_n=\sum_k S(n,k)$ counts all partitions: \[ S(n,k)=S(n-1,k-1)+k S(n-1,k), B_n=∑_k=0^nS(n,k).; Course Review › Advanced Reference
Stirling Numbers $S(n,k)$ (2nd kind), $n\le 6$: \[; Course Review › Advanced Expectation & Markov Chains
Sum and alternating sum of a row: \[ ∑_k=0^n $\binom{n}{k}$ =2^n, ∑_k=0^n(-1)^k $\binom{n}{k}$ =0 (n≥ 1).; Binomial Theorem, Pascal & Combinatorial Identities › Row Sums & Alternating Sums
Surjections (onto functions): Functions from an $n$ -set onto a $k$ -set, by PIE: \[ ∑_j=0^k(-1)^j $\binom{k}{j}$ (k-j)^n = k! S(n,k).; Course Review › Inclusion–Exclusion, Derangements & Pigeonhole
The absorption / committee–chair identity: \[ k $\binom{n}{k}$ =n $\binom{n-1}{k-1}$ .; Binomial Theorem, Pascal & Combinatorial Identities › Combinatorial (Committee–Chair) Identities
The Basic Principle: If $n$ objects are placed into $k$ boxes and $n > k$ , then some box contains at least two objects.; Inclusion–Exclusion, Derangements & Pigeonhole › The Pigeonhole Principle
The Binomial Theorem: For any nonnegative integer $n$ , \[ (x+y)^n=∑_k=0^n $\binom{n}{k}$ x^ n-k y^ k.; Binomial Theorem, Pascal & Combinatorial Identities › The Binomial Theorem & Specific Coefficients
The Catalan numbers: The Catalan numbers are \[ C_n= $\frac{1}{n+1}$ $\binom{2n}{n}$ = $\binom{2n}{n}$ - $\binom{2n}{n+1}$ , C_n+1=∑_i=0^nC_i C_n-i.; Recursion, Catalan Numbers & Generating Functions › Catalan Numbers
The characteristic-equation method: For a linear recurrence with constant coefficients \[ a_n=c_1a_n-1+c_2a_n-2, \] guess $a_n=r^n$ .; Recursion, Catalan Numbers & Generating Functions › Solving Simple Linear Recurrences
The complement shortcut: The complement rule says $P(A) = 1 - P(\text{not } A)$ .; Core Ideas in Plain Terms › Going Deeper: Complements and Expected Value
The core idea: A recurrence counts a large problem in terms of smaller versions of itself.; Recursion, Catalan Numbers & Generating Functions › Setting Up Recurrences
The expected value of a random variable: A random variable $X$ assigns a number to each outcome of a random experiment.; Expected Value, Linearity & Advanced Probability › Expected Value (Definition)
The Extremal Principle: Many existence problems yield to: consider the largest, smallest, or otherwise most extreme object and argue about it.; Inclusion–Exclusion, Derangements & Pigeonhole › Going Deeper: Connections & Advanced Tools
The Full Formula: For sets $A_1,\dots,A_n$ , alternate sums over single sets, pairs, triples, and so on: $$| _i=1^n A_i | = ∑_i |A_i| - ∑_i<j|A_i∩ A_j| + ∑_i<j<k|A_i∩ A_j∩ A_k| - … + (-1)^n+1|A_1∩…∩ A_n…; Inclusion–Exclusion, Derangements & Pigeonhole › General Inclusion–Exclusion
The idea: When a counting problem has no single clean formula, split it into cases that are mutually exclusive (no outcome lands in two cases) and exhaustive (every outcome lands in some case).; Counting Strategies: Casework, Complementary & Overcounting › Casework Counting
The identity, and what it looks like in Pascal's triangle: Claim.; Identities and Techniques, Proved › The Hockey Stick Identity
The master decision: Before counting, ask: does swapping two chosen items produce a different outcome?; Fundamental Counting: Permutations & Combinations › Order Matters vs. Order Doesn't (Choosing vs. Arranging)
The multiset counting formula: Suppose you want to choose $n$ items from $k$ types, where each type is available in unlimited supply and order does not matter.; Distributions: Stars & Bars and Integer Solutions › Combinations with Repetition
The one move behind every identity in this topic: Almost every binomial identity a contest asks for is proved the same way: find a set of objects, count it one way, count it another way, and set the two answers equal.; Identities and Techniques, Proved › Counting the Same Thing Twice
The Sharpened Count: If $n$ objects go into $k$ boxes, then some box contains at least $ $\boxed{\left\lceil \frac{n}{k} \right\rceil}$ $ objects.; Inclusion–Exclusion, Derangements & Pigeonhole › Generalized Pigeonhole & Extremal Arguments
The standard families and their key probabilities: Most contest setups reduce to one of a few named distributions.; Probability Fundamentals & Geometric Probability › A Catalog of Discrete Distributions & a Preview of Expected Value
The stars-and-bars picture: To distribute $n$ identical items among $k$ distinct boxes (any box may get zero), draw $n$ stars and $k-1$ bars in a row.; Distributions: Stars & Bars and Integer Solutions › Stars and Bars (identical items to distinct boxes)
The statement: Let a finite group $G$ of symmetries act on a set $X$ of configurations (colorings, labelings, …).; Counting Strategies: Casework, Complementary & Overcounting › Burnside's Lemma (Orbit-Counting Theorem)
The two rules that power all of counting: Multiplication Principle (AND).; Fundamental Counting: Permutations & Combinations › Addition & Multiplication Principles
The workhorse formula for colorings: When $g$ permutes the $n$ “slots” (beads, faces, cells) and you may color each slot freely with $c$ colors, a coloring is fixed by $g$ iff every slot in a cycle of $g$ receives the same color.; Counting Strategies: Casework, Complementary & Overcounting › Burnside's Lemma (Orbit-Counting Theorem)
Three derivations worth knowing: (A) The Catalan closed form by reflection.; Recursion, Catalan Numbers & Generating Functions › Going Deeper: Closed Forms and Proofs
Three lenses on the same identities: 1.; Binomial Theorem, Pascal & Combinatorial Identities › Going Deeper: Proofs, Generating Functions & Extracting Coefficients
Turning “how many” into a sum of $0/1$ variables: An indicator $\mathbf{1}_{A}$ equals $1$ if event $A$ happens and $0$ otherwise.; Expected Value, Linearity & Advanced Probability › Indicator Random Variables
Turning identities into products of series: Every summation identity in this unit is a shadow of a single equation between generating functions, read off by comparing one coefficient.; Binomial Theorem, Pascal & Combinatorial Identities › Coefficient Extraction: The Unifying Method
Unordered selections: A combination chooses $k$ objects from $n$ distinct objects when order does not matter: \[ $\binom{n}{k}$ = $\frac{n!}{k!\,(n-k)!}$ = $\frac{P(n,k)}{k!}$ .; Fundamental Counting: Permutations & Combinations › Combinations
Upper bounds via inclusion–exclusion: Lower bounds are easy (substitute).; Distributions: Stars & Bars and Integer Solutions › Bounded Variables (upper limits)
Vandermonde's Identity: \[ ∑_k=0^p $\binom{m}{k}$ $\binom{n}{p-k}$ = $\binom{m+n}{p}$ .; Binomial Theorem, Pascal & Combinatorial Identities › Vandermonde's Identity
Vandermonde's Identity: \[ ∑_k=0^p $\binom{m}{k}$ $\binom{n}{p-k}$ = $\binom{m+n}{p}$ .; Course Review › Binomial Theorem & Identities
Waiting Time & Coupon Collector: Geometric waiting time for a prob- $p$ event: $E=\dfrac1p$ .; Course Review › Expected Value
What we are counting: An experiment is any process with an uncertain result.; Probability Fundamentals & Geometric Probability › Sample Spaces & Equally Likely Outcomes
When knowing $B$ tells you nothing about $A$: Events $A$ and $B$ are independent exactly when \[ P(A∩ B) = P(A) P(B), \] equivalently (when the conditionals are defined) $P(A\mid B) = P(A)$ and $P(B\mid A)=P(B)$ .; Conditional Probability, Independence & Bayes › Independence
When plain division is legal: The shortcut $\text{Answer}=M/|G|$ (over-count divided by the number of symmetries) is valid exactly when the group action is free: no nontrivial symmetry fixes any configuration, so every orbit has the full size $|G|$ .; Counting Strategies: Casework, Complementary & Overcounting › The “Divide by Symmetry” Trap, Formalized
When the objects are distinguishable: If $n$ distinct objects are placed into $k$ distinct boxes and each object is chosen independently, there are \[ k^n \] ways (each object picks its box).; Distributions: Stars & Bars and Integer Solutions › Distributing Distinct Objects
Why the squares are the interesting case: The hockey stick adds binomial coefficients.; Identities and Techniques, Proved › Sums of Squares and Cubes, from Binomial Coefficients
Why these fool everyone: Each trap hides a conditioning step.; Conditional Probability, Independence & Bayes › Classic Traps: Monty Hall, Two-Child, False Positives