$\newcommand{\nc}{\newcommand}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Zz}{\mathbb{Z}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\ple}{\preceq}$ $\nc{\ds}{\displaystyle}$ $\nc{\fp}[2]{#1^{\underline{#2}}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\dom}{dom}$ $\DMO{\rng}{rng}$
Notation For $n \in \mathbb{N}$, let $[n]$ denote the set $\{1,2,\ldots n\}$. So $|[n]| = n$, in particular $[0] = \emptyset$.
Q. Professor Pong has five different gifts (gift 1 to 5) to give to 3 different students Alice, Bob and Chris. How many ways can he do so?
A. Professor Pong has 5 choices for Alice and then 4 choices for Bob and final has 3 choices of gifts for Chris. So all together, he has
$$5\times 4 \times 3 = 60$$ways of giving out the gifts.
Nothing special about the number of gifts and the number of students in this example above. So the number of ways to give out $n$ gifts to $k$ people is
$$\fp{n}{k} = \underbrace{n(n-1)\cdots (n-k+1)}_{k\ \text{terms}}.$$More generally, $$\fp{x}{k} = x(x-1)\cdots (x-k+1)$$
is called $x$ to the falling $k$ (the $k$-th falling power of $x$).
An $k$-permutation of a set $X$ is an injective map from $[k]$ to $X$.
If $X$ is understood, then such a map can be represented by a $k$-tuple with no repetition of elements of $X$.
E.g. If $X=\{A,B,C,D,E\}$, then $(B,E,C)$ is the $3$-permutation of $X$, $1 \mapsto B$, $2 \mapsto E$ and $3 \mapsto C$.
Such a map can be regarded as a way of giving gift 1 to $B$ and gift 2 to $E$ and gift 3 to $C$.
Each $k$-permutation of a size of $[n]$ determines a way of giving $n$ gifts to $k$ people as vice versa.
Thus, the number of $k$-permutations of a set of size $n$ is
$$P(n,k) := n(n-1)\cdots (n-k+1) = \frac{n!}{(n-k)!}.$$In particular, $P(n,n) = n!$ is the number of bijections of a set of size $n$ and $P(n,k) =0$ when $k > n$.
Remark
Exercise. Compute $P(10,7)$.
Q. Professor Pong are reading 5 books, (A)nalysis, (B)oolean Algebra, (C)ombinatorics, (D)ata Structures and (E)rgodic Theory. He can only bring 3 for his Spring Break trip. How many choices does he have?
A. If the order of putting the books into the backpack matters, then Professor Pong would have $P(5,3)=60$ ways of packing three books.
However, the order of picking the books does not matter!
For example, the $3$-permuations $(A,C,E)$ and $(E,A,C)$ corresponding to the same collection of books.
In fact, all permutations of $(A,C,E)$ correspond to the same choice.
And there are $P(3,3) = 3! = 6$ ways of permuting each triple of distinct letters.
Therefore, each size 3 subcollection of these 5 books is counted precisely by $3!$ permutations.
Hence, the answer to our question is
$$ \frac{P(5,3)}{3!} = \frac{5!}{(5-3)!3!} = \frac{5!}{2!3!} = 10.$$A subset of size $k$ of $X$ is call a $k$-subset (aka a $k$-combination) of $X$.
Let $\ds \binom{X}{k}$ denote the sets of all $k$-subsets of $X$.
Exercise. Write down $\binom{X}{3}$ for the set $X = \{A,B,C,D,E\}$.
Neither the number of books Professor Pong are reading nor the number of books he can bring on a trip are special.
Therefore, for a set $X$ of size $n$,
$$ \left| \binom{X}{k} \right| = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)!k!}.$$We denote this number, called $n$ choose $k$, by $C(n,k)$ or $\ds \binom{n}{k}$.
With the last notation, we have
$$\ds \left|\binom{X}{k}\right| = \binom{|X|}{k}.$$Choosing a subset of a set is equivalent to choosing its complement, hence
$$ \binom{n}{k} = \binom{n}{n-k} $$In combinatorics, *numbers are often expressed in terms of* $P(n,k)$ and $C(n,k)$.
An $n$-bit is a binary sequence of length $n$.
The weight of an $n$ bit is the number of $1$'s in it, or equivalently the sum of its digits.
Denoted by $B^n$ the set of all $n$-bits and $B^n_k$ the set of all $n$-bits of weight $k$.
For example $01100$ is a $5$-bit of weight $2$.
Our old friend, the map:
$$A \longleftrightarrow 1_A$$is a 1-to-1 correspondence between $\ds \binom{[n]}{k}$ and $B^n_k$.
E.g. The 5-bit $01100$ corresponds to the subset $\{1,2\}$ of $[5]$.
Therefore
$$|B^n_k| = \left|\binom{[n]}{k}\right| = \binom{n}{k}.$$Let
$$B^n_k(i) = \{ x \in B^n_k \colon \text{last bit of $x$ is $i$} \}$$Then clearly $B^n_k$ is the disjoint union of $B^n_k(0)$ and $B^n_k(1)$.
Dropping the last bit is a bijection between $B^n_k(0)$ and $B^{n-1}_k$.
It is also a bijection between $B^n_k(1)$ and $B^{n-1}_{k-1}$.
E.g. $01100 \in B^5_2(0) \mapsto 0110 \in B^4_2$ and $10001\in B^5_2(1) \mapsto 1000\in B^4_1$.
Thus, we have the following *fundamental recurrence*:
$$|B^n_k| = |B^n_k(0)| + |B^n_k(1)| = |B^{n-1}_k| + |B^{n-1}_{k-1}|.$$That is,
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}.$$This recursive relation leads to the famous Pascal Triangle.
Exericse. Add up the numbers in each row of the Pascal Triangle for a few rows, notice anything?
Exercise. For $n,k \ge 1$, show that
$$ k \binom{n}{k} = n\binom{n-1}{k-1}.$$There is a lot of interaction between algebra and combinatorics.
The numbers $\ds \binom{n}{k}$ are also knowns as the binomial coefficients because of the following fundamental result.
Binomial Theorem. $\displaystyle (x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k}$.
Exercise. Verify the Binomial Theorem by expanding $(x+y)^2$, $(x+y)^3$, $(x+y)^4$?
Here is a *proof by counting*: In expanding $\underbrace{(x+y)(x+y) \cdots (x+y)}_n$, if we use $1$ for $x$ and $0$ for $y$, then each term in the expansion corresponds to a unique $n$-bit. E.g. $(01100) \leftrightarrow yxxyy$ in expanding $(x+y)^5$.
Like terms corresponds to $n$-bits of the same weight, so there are $|B^n_k| = \binom{n}{k}$ $x^ky^{n-k}$ terms and hence the theorem.
By setting $x=y=1$, we get back the identity $$ 2^n = (1+1)^n = \sum_{k=0}^n \binom{n}{k}. $$
By setting $x=-1, y =1$, we get $$ 0 = (1-1)^n = \sum_{k=0}^n (-1)^k \binom{n}{k}. $$
Binomial coefficients also counts the number of lattice paths.
A lattice path is a shortest path between two points on the plane lattice ($\mathbb{Z}^2$).
Q. How many lattice paths are there between $(2,3)$ and $(4,5)$? In general, how many lattice paths between two given lattice points on the plane?
A. By translation, we can assume that one of the points is the origin.
By symmetry (reflection),
\begin{align*} &\text{# of lattice paths from $(0,0)$ to $(m,n)$} = \\ &\text{# of lattice paths from $(0,0)$ to $(|m|, |n|)$} \end{align*}so we can assume both $m,n \ge 0$.
Any such lattice path must have $m$ (r)ight steps and $n$ (u)p steps
and so correspond to an $(m+n)$-tuple consisting of $m$ r's and $n$ u's.
Therefore, the number of lattice paths from $(0,0)$ to $(m,n)$ ($m,n \ge 0$) is the coefficient of the terms $r^mu^n$ in the expansion of $(r+u)^{m+n}$ which is $$ \binom{m+n}{m} = \binom{m+n}{n} $$ according to the binomial theorem.
Example. Let's compute how many lattice paths from $(-2,3)$ to $(4,-5)$.
First, the answer is the same as the many of lattice paths from $(-2,3)+(2,-3) = (0,0)$ to $(4,-5) + (2,-3)=(6,-8)$.
Thus, the answer is $\ds \binom{|6|+|-8|}{|6|} = \binom{14}{6}$.