Combinatorics

Permutations (order matters)

Arranging $n$ different objects in a row: $n!$ ways. Choosing and arranging $r$ of them: $P(n,r)=\dfrac{n!}{(n-r)!}$. Around a circle, only relative order counts: $(n-1)!$. Practice: circular permutations problems.

Combinations (order does not matter)

Choosing $r$ of $n$ different objects: $\displaystyle\binom{n}{r}=\frac{n!}{r!\,(n-r)!}$.

Combinations with repetition (stars and bars)

Choosing $r$ items from $m$ types, repeats allowed, or putting $r$ identical objects into $m$ distinct boxes: $\displaystyle\binom{r+m-1}{m-1}$. Practice: stars and bars problems.

Inclusion–exclusion

To count what avoids several bad properties, subtract each bad case, add back the overlaps of two, subtract the overlaps of three, and so on:

It is the standard way to handle upper bounds in stars and bars problems.

Graph theory

Counting and structure on networks of points and lines: degrees, Euler paths, trees, coloring. Practice: graph theory problems.