Number of ways to select $k$ objects from a collection of $n$ objects.
- if order matters: permutation
- if order doesn’t matter: combination
Let $k, n$ be integers, $k \leq n$. We have $n$ distinct objects, we wish to count number of ways to pick $k$ of these and arrange them in a sequence. i.e. number of sequences of length $k$ made up of the $n$ objects.
$$ \begin{align*} \text{Number of permutations} &= n(n-1)(n-2)…(n-(k-1)) \br &=\frac{n(n-1) … (n-k+1)(n-k) … 2 \cdot 1}{(n-k)(n-k-1)…2\cdot 1} \br &=\frac{n!}{(n-k)!} \end{align*} $$
In particular, if $k = n$, number of ways to arrange $n$ objects is $n!$.
Let $\binom{n}{k}$ denote number of ways to form a $k$-elements subset from $n$ objects.
$\binom{n}{k}$ is called binomial coefficient.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
$$\sum_{k=1}^n\binom{n}{k}p^k(1-p)^{n-k} = 1$$
</span>
</span>
<span class="proof__expand"><a>[expand]</a></span>