Pascal's Formula

We have already seen a relationship between the entries in each row of Pascal's Triangle and the total number of $k$-combinations from an $n$-element set. We will now solidify their relationship with a formula. Before we do so though, we will redraw Pascal's triangle as follows:

If we start the top of Pascal's triangle to be $1$ then we can now say that each entry in Pascal's triangle is obtained by summing the entry directly above and one to the left with the entry directly above. We have already seen how the total number of $k$-combinations from an $n$-element set relates to Pascal's triangle though, which leads us to the following formula.

Theorem 1 (Pascal's Formula): The number of $k$-combinations of an $n$-element set $A$ can be obtained with the formula $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

We will prove Theorem 1 both algebraically and combinatorially.

• Proof 1: We simplfy the righthand side of the formula above.

(1)

\begin{align} \quad \binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-1-[k-1])!} + \frac{(n-1)!}{k!(n-1-k)!} \\ \quad = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-[k+1])!} \\ \quad = \frac{(n-1)!}{(k-1)!(n-k)(n-[k+1])!} + \frac{(n-1)!}{k(k-1)!(n-[k+1])!} \\ \quad = \frac{k(n-1)!}{k!(n-k)!} + \frac{(n-k)(n-1)!}{k!(n-k)!} \\ \quad = \frac{k(n-1)! + (n-k)(n-1)!}{k!(n-k)!} \\ \quad = \frac{(n-1)! n}{k!(n-k)!}\\ \quad = \frac{n!}{k!(n-k)!} \\ \quad = \binom{n}{k} \quad \blacksquare \end{align}

• Proof 2: Let $A = \{ x_1, x_2, ..., x_n \}$ be an $n$-element set. The number of $k$-combinations using elements from $A$ is equal to the number of subsets of $A$ whose size is $k$. Consider the arbitrary element $x_n \in A$.

• Define the set $X$ to be the set of subsets of $A$ whose size is $k$ and that contain $x_n$, that is:

(2)

\begin{align} \quad X = \{ B : B \subseteq A \: , \: \lvert B \rvert = k \: , \: \mathrm{and} \: x_n \in B \} \end{align}

• Since $x_n$ is contained in each of these subsets $B$ then we must choose $k - 1$ elements out of the remaining $n - 1$-element set $A \setminus \{ x_n \} = \{ x_1, x_2, ..., x_{n-1} \}$ to form our $k$-combination. There are $\binom{n-1}{k-1}$ ways to do this.

• Define the set $Y$ to be the set of subsets of $A$ whose size is $k$ and that do not contain $x_n$, that is:

(3)

\begin{align} \quad Y = \{ B : B \subseteq A \: , \: \lvert B \rvert = k \: , \: \mathrm{and} \: x_n \not \in B \} \end{align}

• Since $x_n$ is not contained in each of these subsets $B$ then we must choose $k$ elements out of the remaining $n - 1$-element set $A \setminus \{ x_n \} = \{ x_1, x_2, ..., x_{n-1} \}$ to form our $k$-combination. There are $\binom{n-1}{k-1}$ ways to do this.

• Note that the sets $X$ and $Y$ form a partition of all $k$-combinations of elements from $A$, $\binom{n}{k}$ . Therefore by applying the addition principle we see that:

(4)

\begin{align} \quad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad \blacksquare \end{align}