Formula sheet

A factorial is the product of all positive integers less than or equal to a given positive integer. In other words,

The number of ways of arranging $n$ objects in a line is $n!$.

The number of ways of arranging $n$ objects in a circle, where rotations of the same arrangement aren't considered distinct, is $(n-1)!$.

The number of ways of arranging $n$ objects in a circle, where rotations and reflections of the same arrangement aren't considered distinct, is

The number of ways to arrange $k$ objects out of $n$ total objects is

The number of ways to order a word is

where $n$ is the number of letters and $d_1, d_2, d_3, \ldots$ are the number of times each letter that occurs more than once appears in the word.

The number of ways to choose $k$ objects out of a total of $n$ objects is

This is usually read "$n$ choose $k$".

The number of subsets of a set of size $n$ is $2^n$.

When all outcomes are equally likely,

Many counting and probability problems can be solved by splitting them into several cases, counting each case, and adding.

When doing casework, always try to minimize the number of cases you have to deal with.

If a problem asks for the probability that an event $A$ happens given that another event $B$ has happened, only the outcomes in $B$ are still possible:

When the outcomes are not equally likely, work with probabilities instead:

The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties, while making sure that elements satisfying more than one property are not counted twice.

$|A \cup B|$ is the number of elements of the union of $A$ and $B$: everything that is in $A$ or in $B$ (or both). Duplicates are only written once.

$|A \cap B|$ is the number of elements of the intersection of $A$ and $B$: only the elements that are in both sets.

Given two sets $A_1$ and $A_2$,

Basically, we count the possibilities in the 2 "things" and subtract the duplicates.

Given three sets $A_1$, $A_2$, $A_3$,

Count the possibilities in the 3 "things", subtract the duplicates in all 3 pairs of sets, then add back the elements that are in all 3 sets.

If $A_1, A_2, \ldots, A_n$ are finite sets, then

Add the singles, subtract the pairs, add the triples, and keep alternating.

The number of ways to place $n$ identical objects into $k$ distinguishable bins is

Stars and bars is extremely useful, and can often be adapted based on situations. For example, if each bin has to have at least 1 object in it, we assign each bin 1 object to start off with and apply our formula with $n - k$ objects and $k$ distinguishable bins:

For $n \ge 1$,

That is, $\binom{n}{0} + \binom{n}{2} + \cdots = \binom{n}{1} + \binom{n}{3} + \cdots$

Pascal's Triangle is a triangular array of binomial coefficients. It contains many patterns that make complex calculations much easier.

Row $n$ (counting the top row as row 0) holds $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Below, the first rows are written as binomial coefficients; Show me gives rows 0 to 10 as numbers.

The number of rectangles of all sizes in a rectangular grid of size $m \times n$ is

The number of squares in an $n \times n$ grid of squares is

The number of ways to get from $(0,0)$ to a point $(m,n)$ moving only up and right is

In a polyhedron, if you add up the number of sides on every face, you get 2 times the number of edges of the polyhedron. This is because each edge is part of 2 faces.

If you add up the number of edges connected to every vertex, you also get 2 times the number of edges, since each edge is counted at 2 different vertices.

For example, a cube has 4 sides per face and 6 faces, so it has $\frac{4 \times 6}{2} = 12$ edges. Also, there are 3 edges per vertex and 8 vertices, so there are $\frac{3 \times 8}{2} = 12$ edges.

Geometric probability is a way to calculate probability by measuring the number of outcomes geometrically, in terms of length, area, or volume. The key to solving geometric probability is

1. Try a few examples for the different cases, and always mark the extreme cases.
2. Figure out the region the shape maps out.
3. Use geometry to find the area of this region.

Expected value is the weighted average of the outcomes: each outcome counts in proportion to how likely it is.

The expected value of a random quantity $X$ is

where the $x_i$ are the possible values of $X$ and $P(x_i)$ is the probability that each one happens.

In words: multiply each value by its probability, then add.

For any random quantities $x_1, x_2, \dots, x_n$, independent or dependent,

The expected value of a total is the sum of the expected values of its parts.

Recursion is the process of finding smaller values and using them to calculate larger values.

Solving a problem with recursion is a multi-step process:

1. Solve the problem for a few smaller base cases by hand.
2. In general, you need as many base cases as there are terms on the right-hand side of your recursion.
3. For a general $f(n)$, find a recursive equation in terms of earlier values by looking at the different ways to get to that point.
4. Calculate $f(n)$ step by step until you reach the number you want.

Often it is simpler to define two recursive functions, say $a(n)$ and $b(n)$, where the actual answer is some combination of the two (for example $a(n) + b(n)$).

We use states when we want the probability of “a win” from different positions or turns. For a states problem, follow three steps:

1. Assign a variable to the probability of winning from each position.
2. Write an equation for the probability of winning from each position, in terms of the other states.
3. Solve the system of equations.

Always look out for symmetry in states problems: positions you have an equal probability of winning from can share one variable. That makes the equations much simpler.

For states recursions, it is often a good idea to simply make a table of the probability of being at each location at every time step. Remember: the total probability at each step must always be $1$.

Expected value states work almost exactly like probability states. The only difference: in every equation, we add 1. For example,

We add $1$ because it takes $1$ move to go from $A$ to $B$.

For any nonzero $x$:

If

then

Sum of odd powers:

The signs in the second factor alternate between positive and negative.

Difference of powers:

The signs in the second factor are all positive.

1. Substitution
2. Elimination
3. Adding/Subtracting/Multiplying Equations
4. Group terms together
5. Find common denominator
6. Don't always have to find every variable
7. Use symmetry between variables
8. Make smart substitutions that can simplify your expression
9. Look for common factorizations

The solutions to the quadratic equation

are

In the quadratic formula,

(the part inside the square root) is the discriminant of the quadratic.

1. If the discriminant $b^2 - 4ac$ is $0$, then the quadratic has a double (repeated) root.
2. If the discriminant $b^2 - 4ac$ is positive, the quadratic has 2 different real roots.
3. If the discriminant $b^2 - 4ac$ is negative, the quadratic has no real roots.

In a quadratic equation

the sum of its roots is

and the product of its roots is

In a polynomial

with roots $r_1, r_2, r_3, \dots, r_n$, the following holds:

The signs alternate: a sum of products of an odd number of roots gets a minus sign, an even number gets a plus sign.

A polynomial

can be written as

where $r_1, r_2, r_3, \ldots, r_n$ are the $n$ roots of the polynomial.

A polynomial

(the leading coefficient is $1$) can be written as

where $r_1, r_2, r_3, \ldots, r_n$ are the $n$ roots of the polynomial.

When a problem asks for an expression like $(k - r)(k - s)(k - t)$, where $r$, $s$ and $t$ are the roots of a monic polynomial $P$, it is just $P(k)$, by the representation above. The same works for a polynomial that is not monic, except the product is

where $a_n$ is the coefficient of the $x^n$ term.

A polynomial of degree $n$ (its largest term has power $n$) has $n$ complex roots, counted with multiplicity. For example, a double root counts as $2$ roots.

The remainder when a polynomial $P(x)$ is divided by $x - r$ is $P(r)$.

$x - r$ divides a polynomial $P(x)$ if $P(r) = 0$. This is a direct consequence of the Remainder Theorem.

A polynomial

is symmetric if

Basically, opposite coefficients are equal.

To solve a symmetric polynomial $P(x) = a_0 x^n + a_1 x^{n-1} + \cdots + a_1 x + a_0$ of even degree:

• Divide by $x^{n/2}$.
• Group the $x^k$ and $\frac{1}{x^k}$ terms together.
• Make the substitution

and write every term in your expression with $y$.

• Solve the reduced polynomial.

If

has roots $r_1, r_2, r_3, \ldots, r_n$, then

has roots

Flip the coefficients of a polynomial and its roots become the reciprocals of the original roots.

If

has roots $r_1, r_2, r_3, \ldots, r_n$, then

has roots

Let $P(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$ have roots $r_1, r_2, \ldots, r_n$, and let

Then

and so on. Here $a_j = 0$ whenever $j$ is negative (that can show up once $k > n$).

In words:

1. Multiply $S_k$ by the leading coefficient $a_n$.
2. Multiply $S_{k-1}$ by the next coefficient $a_{n-1}$, then $S_{k-2}$ by $a_{n-2}$, and so on, adding the products.
3. Stop when you reach $S_0$: instead of $S_0$, multiply that last coefficient by $k$. (If the coefficients run out first, just stop.)
4. Set the sum equal to $0$.

In words:

Substitute $a_n = a_1 + (n - 1)d$ to get

In general, the terms of a geometric sequence can be represented as

where

• $r$ is the common ratio between consecutive terms
• $n$ is the number of terms

For $r \ne 1$,

For $-1 < r < 1$,

In simple terms, the sum of the first $n$ odd numbers is $n^2$.

To think about it intuitively, just take $2$ out of each term:

Expand the first few and last few terms, and cancel out any terms you see.

Turned around: $\text{sum} = \text{mean} \times \text{number of terms}$. Most mean problems are really sum problems.

After arranging the numbers in increasing or decreasing order:

• If the number of terms is odd, the median is the middle number.
• If the number of terms is even, the median is the average of the middle two numbers.

The geometric mean of the positive numbers $a_1, a_2, a_3, \ldots, a_n$ is

The harmonic mean of the positive numbers $a_1, a_2, a_3, \ldots, a_n$ is

In words: the reciprocal of the average of the reciprocals.

The quadratic mean (root mean square) of $a_1, a_2, a_3, \ldots, a_n$ is

For positive numbers, $\text{QM} \ge \text{AM} \ge \text{GM} \ge \text{HM}$, with equality exactly when all the numbers are equal (Chapter 40 proves it).

Equivalently,

If one person can do something in $a$ amount of time, and someone else can do the same thing in $b$ amount of time, working together they can do it in

time.

Equivalently,

Keep the units matched: miles per hour goes with time in hours. Convert minutes first.

Primes are numbers that have exactly two factors: $1$ and the number itself. For example, $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$ are all primes.

Prime factorization writes a number as a product of primes.

Example: the prime factorization of $60$ is $2^2 \times 3 \times 5$.

If the prime factorization of a number is

then the number of factors of this number is

If the prime factorization of a number is

then the sum of the factors of this number is

For each prime $p$ in the prime factorization, first find the sum of $p^k$ over all the possible exponents $k$ (from $0$ up to the exponent of $p$). Then multiply these sums over all of the primes to get the sum of all the factors of the number.

If a number $n$ has $f$ factors (count them with the number-of-factors formula), then the product of the factors of $n$ is

For a prime $p$, the number of factors of $p$ in $n!$ is

The sum stops once $p^k > n$, because every later term is $0$.

The Greatest Common Divisor (GCD) of two or more nonzero integers is the largest positive integer that divides each of them.

It is also called the GCF (Greatest Common Factor). The two names mean the same thing.

The Least Common Multiple (LCM) of two or more nonzero integers is the smallest positive integer that is divisible by each of them.

$\gcd(m, n)$ takes the lowest exponent of each prime in the prime factorizations of $m$ and $n$.

$\operatorname{lcm}(m, n)$ takes the highest exponent of each prime.

For example, $24 = 2^{3} \cdot 3$ and $36 = 2^{2} \cdot 3^{2}$, so $\gcd(24, 36) = 2^{2} \cdot 3 = 12$ and $\operatorname{lcm}(24, 36) = 2^{3} \cdot 3^{2} = 72$.

The product of the GCD and the LCM of two numbers equals the product of the two numbers:

If two numbers have a common factor $c$, then

where $x > y$ and $k$ is a positive integer.

The equation

has integer solutions $x, y$ if and only if $\gcd(a, b)$ divides $c$.

means that the number $n$ leaves the same remainder as $a$ when divided by $b$. Equivalently, $b$ divides $n - a$. Read it as “$n$ is congruent to $a$ mod $b$”.

If $a \equiv x \pmod{n}$ and $b \equiv y \pmod{n}$, then

(The book prints the first congruence as “$a = x \pmod n$”; it means $\equiv$.)

If $a \equiv x \pmod{n}$, then

for every positive integer $m$.

To find the last digit(s) of a huge power $a^b$, compute the first few values of $a^b$ and look for a pattern. The remainders must eventually repeat, so the pattern carries over to large $b$.

If $n$ has the prime factorization $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, then

where $\varphi(n)$ is the number of positive integers $\le n$ that are relatively prime to $n$.

Steps: 1. Find the prime factorization of $n$. 2. For each prime $p_i$, form $1 - \frac{1}{p_i}$ and multiply them. 3. Multiply that product by $n$.

For $n > 1$,

if and only if $\gcd(a, n) = 1$.

If $p$ is a prime and $p \nmid a$, then

(The book says “if and only if $p$ is a prime and $\gcd(a, n) = 1$”. The converse is false: $561 = 3 \cdot 11 \cdot 17$ is not prime, yet $a^{560} \equiv 1 \pmod{561}$ for every $a$ coprime to $561$.)

If $ab \equiv 1 \pmod{n}$, then $a$ is the modular inverse of $b$ (mod $n$), and $b$ is the inverse of $a$. We write

An inverse of $a$ exists exactly when $\gcd(a, n) = 1$.

For a prime $p$,

For non-negative $n$,

In modular arithmetic, write a big base as “small number + multiple of 10”: in $(1 + 10)^{n}$ every term from $10^3$ on vanishes mod $1000$, so $(1 + 10)^n \equiv 1 + 10n + 100\binom{n}{2} \pmod{1000}$.

If a positive number $x$ satisfies

where the $n_i$ are pairwise relatively prime, then $x$ has a unique solution modulo $n_1 n_2 \cdots n_k$.

To solve a pair of congruences you can either guess and check until a number satisfies both, or use the algebraic method:

1. Start with $n \equiv r_1 \pmod{m_1}$ and $n \equiv r_2 \pmod{m_2}$, with $m_1$ and $m_2$ relatively prime.
2. Rewrite the first algebraically: $n = k m_1 + r_1$.
3. Put it into the second: $k m_1 + r_1 \equiv r_2 \pmod{m_2}$, so $k \equiv (r_2 - r_1)\cdot m_1^{-1} \pmod{m_2}$.
4. Find $m_1^{-1} \pmod{m_2}$ by guess and check.
5. Now you know $k \equiv k_0 \pmod{m_2}$; write $k = m_2 t + k_0$.
6. Substitute back into $n = k m_1 + r_1$.
7. Read off the final congruence $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$.

(The book's step 3 reads “$m_1 \equiv (r_2 - r_1)\cdot k^{-1}$”, and step 5 uses undefined letters $b, d$; fixed here.)

For relatively prime $m_1, m_2$, the solution of $n \equiv r_1 \pmod{m_1}$ and $n \equiv r_2 \pmod{m_2}$ is

(The book leaves out the final modulus $m_1 m_2$.)