Permutations #

Order matters

Without repetitions: $$nP_r = \frac{n!}{(n-r)!}$$

With repetitions (mutiply possibilities for each position): $$n^r$$

Limited repetitions (pistinguishable permutations):

$$\frac{n!}{k_1!k_2!\dots k_t!}$$


  • $n$ objects
  • $k$ amount of time each object appears

Combinations #

Order does not matter:

The number of $n$ objects taken $r$ at a time is: $$_nC_r = \frac{n!}{r!(n - r)!}$$

With repetitions:

$$_{n + r - 1}C_r = \frac{n!}{r!(n - r)!}$$

Pigeonhole principle #

If $n$ pigeons are assigned to $m$ pigeonholes, and $m < n$, then at least one pigeonhole contains two or more pigeons.

Extended Pigeonhole Principle #

If $n$ pigeons are assigned to $m$ pigeonholes, then one of the pigeonholes must contain at least $\lfloor(n - 1)/m \rfloor+ 1$ pigeons.

Recurrence relations #

Backtracking #

Substitute the definition until a pattern emerges.

The sum of sequential numbers $1$ to $n$: $$ \frac{n(n+1)}{2} $$

Find out the constant by substituting $a_0$

Linear Homogenous Recurrence Relations #

Linear homogenous reltation of degree $k$: $$a_n = r_1a_{n-1} + r_2a_{n-2} + \dots + r_ka_{n-k}$$

To find an explicit formuala for euqations of degree 2:

  1. Characteristic euqation: $x^2-r_1x-r_2 = 0$
  2. Solve the equation, then the explicit forumla is:
    • For two distinct roots: $a_n = c_1r_1^n + c_2r_2^n$
    • For a single root: $a_n = c_1r^n + c_2nr^n$
  3. To find the constants, fill in $a_1$ $a_2$ and solve the system of equations