A student has 6 pencils, all of different colors. He chooses three and puts them in his pencil case. How many possibilities are there?
There are $\binom{6}{3}$ possibilities to choose 3 pencils from a pencil case of 6 pencils.

## Proposition 5.

We have

1. $\binom{n}{k}=\binom{n}{n-k}$
2. $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.
3. $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^{n}$
4. $\binom{n}{k}=\frac{n!}{(n-k)!k!}$

## Proof. We have

1. "With $n$ elements, choosing the $k$ elements to keep is the same as choosing the $n-k$ elements to discard." Therefore, $\binom{n}{k}=\binom{n}{n-k}$.
2. Let $n$ elements be $\{A, B, \cdots, N\}$, and we want to choose $k$ of them. Consider the first element $A$. Either we keep it or we leave it aside. If we keep it, we need to choose $k-1$ more elements from $\{B, \cdots, N\}$ (with $n-1$ elements). This gives $\binom{n-1}{k-1}$ possible choices. If we do not keep $A$, we then need to choose $k$ elements from $\{B, \cdots, N\}$, which gives $\binom{n-1}{k}$ possible choices. Conclusion: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.
3. $\binom{n}{0}$ is the number of subsets of size $0$, $\binom{n}{1}$ is the number of subsets of size $1$, $\binom{n}{2}$ is the number of subsets of size $2$, etc... Therefore, $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}$ is the total number of all subsets, which is $2^{n}$.
4. If the order were important, choosing the first element gives $n$ possibilities, the second element gives $n-1$ possibilities, etc., the $k$-th element gives $n-k+1$ possibilities, and we would have $n \times(n-1) \times \cdots \times(n-k+1)$ possibilities. Since the order does not matter, each group of $k$ elements will appear $k!$ times. Therefore,

$$
\binom{n}{k} \times k!=n \times(n-1) \times \cdots \times(n-k+1)=\frac{n!}{(n-k)!}
$$