Counting (review)

Rule of sum and product:

Choose one item from a set of size $s_1$ and one item from a set of size $s_2$: $s_1s_2$ choices.

Choose one item from a set of size $s_1$ or one item from a set of size $s_2$: $s_1+s_2$ choices.

Permutations and combinations

$P(n,k)=$ the number of ways of ordering $k$ objects, chosen from a collection of $n$ objects.

$P(n,k)=n(n-1)\cdots(n-k+1)$

$P(n,n)=n(n-1)\cdots 2\cdot 1=n!$ ($n$ factorial).

$P(n,k)=\frac{n!}{(n-k)!}$.

$C(n,k)=$ the number of ways to choose $k$ objects, unordered, from a collection of $n$ objects.

$P(n,k)=C(n,k)\cdot k!$

$C(n,k)=\frac{n!}{k!(n-k)!}$.

$C(n,k)={n\choose k}$