# Counting

## 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!}$$

where:

• $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