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:

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

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

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

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

Characteristic euqation: $x^2-r_1x-r_2 = 0$
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$
To find the constants, fill in $a_1$ $a_2$ and solve the system of equations