Course Review

Multiplication (AND). A task done in independent stages with $n_1,n_2,\dots,n_k$ ways per stage has $n_1 n_2 \cdots n_k$ total outcomes. Addition (OR). Disjoint cases add: $|A_1|+\cdots+|A_k|$. Ex. 2 letters then 3 digits: $26^2\cdot 10^3 = 676{,}000$ plates.

Arrange $k$ of $n$ distinct objects in ordered slots:

Ex. Gold/silver/bronze among $8$ runners: $P(8,3)=8\cdot7\cdot6=336$.

Choose $k$ of $n$ distinct objects, ignoring order:

Ex. A $4$-person committee from $10$: $\dbinom{10}{4}=210$.

Arrange $n$ objects with $n_i$ copies of type $i$ ($\sum n_i = n$):

Ex. MISSISSIPPI: $\dfrac{11!}{1!\,4!\,4!\,2!}=34{,}650$.

Arrangements around a circle count only relative position (fix one seat to remove $n$ rotations):

Ex. $6$ people at a round table: $(6-1)!=120$.

Split into disjoint, exhaustive cases; count each; add. Choose the split that makes each case easy and keeps cases from overlapping. Ex. Rolls of two dice summing to a multiple of $4$: cases sum$=4,8,12$ give $3+5+1=9$.

Count the opposite and subtract from the total: $|E| = |S| - |E^c|$. Ideal for “at least one.” Ex. $3$-digit numbers with a digit $7$: $900 - 8\cdot9\cdot9 = 252$.

Build a valid object step by step, multiplying the choices available at each step (keep the count per step constant, or split into cases). Ex. $5$ books, dictionary on an end: $2\cdot 4! = 48$.

Count an easy ordered/labeled way, then divide by the symmetries you introduced: rotations ($\div n$), reflections ($\div 2$), interchangeable groups ($\div k!$). Ex. Split $6$ players into $3$ unlabeled pairs: $\dfrac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!}=\dfrac{90}{6}=15$.

If a set is hard to count, find a one-to-one correspondence with a set you can count; equal sizes. Ex. Grid paths $(0,0)\to(4,3)$ $\leftrightarrow$ strings of $4$ R's, $3$ U's: $\dbinom{7}{3}=35$.

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

Ex. $10$ identical candies among $4$ kids: $\dbinom{13}{3}=286$.

For $x_i\ge 1$, give each variable one unit first ($y_i=x_i-1\ge 0$):

Ex. $10$ candies, each kid at least one: $\dbinom{9}{3}=84$.

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). Ex. $x_1+x_2+x_3=10$, each $\le 4$: $\binom{12}{2}-3\binom{7}{2}+3\binom{2}{2}=66-63+3=6$.

Split $n$ distinct items into labeled groups of sizes $n_1,\dots,n_r$:

Ex. Deal $9$ distinct cards into piles of $4,3,2$: $\dfrac{9!}{4!\,3!\,2!}=1260$.

Ex. Coefficient of $x^2$ in $(1+x)^5$ is $\dbinom{5}{2}=10$.

Ex. $\dbinom{5}{2}=\dbinom{4}{1}+\dbinom{4}{2}=4+6=10$.

Ex. Subsets of a $5$-set: $2^5=32$; equal numbers of even- and odd-sized subsets.

Ex. $\dbinom{2}{2}+\dbinom{3}{2}+\dbinom{4}{2}=1+3+6=10=\dbinom{5}{3}$.

Ex. Pick $2$ from $3$ boys $+$ $4$ girls: $\sum_k \binom{3}{k}\binom{4}{2-k}=\binom{7}{2}=21$.

Ex. $3\dbinom{6}{3}=6\dbinom{5}{2}=60$; paths to $(4,3)$: $\dbinom{7}{4}=35$.

Ex. $\le 100$ divisible by $2$ or $3$: $50+33-16=67$.

Ex. $4$ letters, wrong envelopes: $D_4=9$.

Functions from an $n$-set onto a $k$-set, by PIE:

Ex. Onto maps $\{1,2,3\}\to\{a,b\}$: $2^3-2=6$.

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$). Ex. $13$ people share a birth month: some month has $\lceil 13/12\rceil=2$.

Set up $a_n$ from smaller cases by conditioning on the last choice. Tiling a $1\times n$ strip with $1\times1$ and $1\times2$ pieces:

Ex. $1\times 4$ strip: $a_4=5$ tilings.

Counts balanced parentheses, non-crossing paths, triangulations, binary trees. Ex. Valid sequences of $3$ pairs of parentheses: $C_3=5$.

Encode a sequence $a_n$ as coefficients of $\sum a_n x^n$; products of series combine choices. Key:

Ex. Ways to make $6$ from parts $\{1,2\}$: coefficient of $x^6$ in $\frac{1}{(1-x)(1-x^2)}$ is $4$.

Ex. Two dice sum to $7$: $\dfrac{6}{36}=\dfrac16$.

Compute favorable and total outcomes with the same counting rules (order-consistent on both). Ex. $2$ aces in a $5$-card hand: $\dfrac{\binom{4}{2}\binom{48}{3}}{\binom{52}{5}}$.

Events are independent iff

Ex. Two coins both heads: $\tfrac12\cdot\tfrac12=\tfrac14$.

When outcomes fill a continuous region, probability is a ratio of measures (length, area, volume):

Ex. Random point in $[0,1]^2$ with $x+y<1$: area $\tfrac12$, so $P=\tfrac12$.

Ex. Die shows even, chance it's $2$: $\dfrac{1/6}{1/2}=\dfrac13$.

Ex. Two cards, both hearts (no replacement): $\dfrac{13}{52}\cdot\dfrac{12}{51}=\dfrac{1}{17}$.

For a partition $B_1,\dots,B_n$ of the sample space:

Ex. Urn A (bag $\tfrac12$): $P(\text{red})=\tfrac12\cdot\tfrac{2}{5}+\tfrac12\cdot\tfrac{1}{3}=\tfrac{11}{30}$.

Ex. Test $99\%$ accurate, disease rate $1\%$: $P(\text{sick}\mid +)=\dfrac{.99(.01)}{.99(.01)+.01(.99)}=\tfrac12$.

Ex. One fair die: $E[X]=\dfrac{1+2+\cdots+6}{6}=3.5$.

Always true, even for dependent variables:

Ex. Sum of $10$ dice: $10\cdot 3.5=35$.

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)$. Ex. Expected fixed points of a random permutation of $n$: $n\cdot\tfrac1n=1$.

Let $E$ be the expected value from a state; condition on the next step and solve the resulting equation(s). Ex. Flips until first head: $E=1+\tfrac12 E \Rightarrow E=2$.

Geometric waiting time for a prob-$p$ event: $E=\dfrac1p$. Collecting all $n$ coupons:

Ex. All $6$ die faces: $6H_6=6\cdot\tfrac{49}{20}=14.7$.

multicols2

• 3pt
• order matters, no repeat $\rightarrow$ $P(n,k)$
• order doesn't matter $\rightarrow$ $\binom{n}{k}$
• repeated letters/objects $\rightarrow$ multinomial $\frac{n!}{n_1!\cdots n_r!}$
• around a circle $\rightarrow$ $(n-1)!$
• “at least one” $\rightarrow$ complement $1-P(\text{none})$
• distribute identical items $\rightarrow$ stars and bars
• distinct items into groups $\rightarrow$ multinomial
• overlapping conditions / “or” $\rightarrow$ inclusion--exclusion
• nothing in its place $\rightarrow$ derangement $D_n$
• something forced to repeat $\rightarrow$ pigeonhole
• balanced / non-crossing $\rightarrow$ Catalan $C_n$
• process built step by step $\rightarrow$ recursion
• “given that” / updated info $\rightarrow$ conditional / Bayes
• continuous / random point $\rightarrow$ geometric probability
• expected count of something $\rightarrow$ linearity + indicators
• repeated states with memory $\rightarrow$ expectation via states
• time until first success $\rightarrow$ waiting time $1/p$
• weird binomial sum $\rightarrow$ known identity / count two ways

multicols

Row $n$ sums to $2^n$; entry $k$ is $\dbinom{n}{k}$; each entry is the sum of the two above it (Pascal's rule).

The number of distinct configurations under a symmetry group $G$ equals the average number of colorings fixed by each group element:

Ex. $2$-color a necklace of $4$ beads under $4$ rotations: $\tfrac14(2^4+2^1+2^2+2^1)=6$.

$S(n,k)$ partitions an $n$-set into $k$ nonempty unlabeled blocks; Bell number $B_n=\sum_k S(n,k)$ counts all partitions:

Surjections from $n$-set onto $k$-set $=k!\,S(n,k)$. Ex. $S(4,2)=7$, so onto maps $\{1,2,3,4\}\to\{a,b\}$ number $2!\cdot 7=14$.

Since $D_n=n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ converges to $n!/e$ fast,

Ex. $D_5=\lfloor 120/e+0.5\rfloor=\lfloor 44.65\rfloor=44$.

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}$:

Ex. $\sum_{k\equiv 0\ (2)}\binom{n}{k}=\tfrac12\big(2^n+0^n\big)=2^{n-1}$ for $n\ge 1$.

For any real (or complex) $\alpha$ with $|x|<1$, and the negative-power expansion:

Here $\binom{\alpha}{k}=\dfrac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}$. Ex. $\dfrac{1}{(1-x)^{3}}$ has $x^n$ coefficient $\dbinom{n+2}{2}$ (stars and bars).

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). Ex. $\sum k\binom{4}{k}=4\cdot 2^{3}=32$; $\sum\binom{4}{k}^2=\binom{8}{4}=70$.

Counts: balanced parentheses, Dyck paths never dipping below the axis, triangulations of an $(n{+}2)$-gon, full binary trees with $n{+}1$ leaves, and non-crossing chord matchings. Ex. $C_4=\binom{8}{4}-\binom{8}{3}=70-56=14$.

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$. Distinct roots $r_i$ give $a_n=\sum A_i r_i^{n}$; a root of multiplicity $m$ contributes $(A_0+A_1 n+\cdots+A_{m-1}n^{m-1})r^{n}$. Fix constants from initial values. Ex. $a_n=2a_{n-1}-a_{n-2}$ has double root $1$: $a_n=A+Bn$ (arithmetic).

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$. Ex. Fibonacci: $A(x)=\dfrac{x}{1-x-x^{2}}\Rightarrow a_n=\dfrac{\varphi^{n}-\psi^{n}}{\sqrt5}$.

Beyond linearity and indicators ($E[\sum X_i]=\sum P(\text{event }i)$), for a nonnegative integer $X$ use the tail sum:

Geometric wait for a prob-$p$ event: $E=1/p$. Coupon collector over $n$ types: $E=n H_n$. Ex. Rolls to see all $6$ faces: $6H_6=14.7$.

Updating hypothesis $H$ against $\bar H$ on evidence $E$ multiplies prior odds by the likelihood ratio:

Ex. Prior odds $1{:}99$, likelihood ratio $99{:}1$ $\Rightarrow$ posterior odds $1{:}1$, i.e. $P=\tfrac12$.

Define hitting probabilities/times per state and condition on the first step. Fair-coin gambler's ruin from $$k$ with absorbing barriers $0$ and $N$:

Ex. Start at $$3$ of $$10$: reach goal with prob $\tfrac{3}{10}$, expected $21$ steps.

A distribution $\pi$ is stationary for transition matrix $P$ when it is unchanged by a step:

For an irreducible chain the long-run fraction of time in state $i$ is $\pi_i$, and the mean return time is $1/\pi_i$. Ex. Two-state chain with rates $a$ (out of $1$), $b$ (out of $2$): $\pi=\big(\tfrac{b}{a+b},\tfrac{a}{a+b}\big)$.

Row sums give the Bell numbers.

$B_n$ counts all set partitions of an $n$-set; $B_n=\sum_{k}\binom{n-1}{k}B_k$.