22.4: Properties

Note: In this section we will use the alternative notation \(C^n_k\) in place of \(C(n, k). \)

The combination values \(C^n_k\) as we vary \(n\) and \(k\) exhibit some patterns — see Figure \(\PageIndex{1}\) below.

Figure \(\PageIndex{1}\): Pascal's triangle.

Studying the version of Pascal's triangle involving the actual combination values, here are some of the patterns we observe.

• The values are symmetric about a vertical line through the centre of the triangle.
• It appears that every entry is the sum of the two entries immediately above.
• It appears that each row sums to a power of \(2\text{.}\)

We have already observed the first pattern as arising from the equivalence of choosing versus rejecting elements to form a subset (see Corollary 22.2.1 and Remark 22.2.1).

The next two propositions confirm that the other two observed patterns continue throughout the triangle.

Proposition \(\PageIndex{1}\)

For \(n \ge 2\) and \(1\le k \le n-1\text{,}\) we have \(C^n_k = C^{n-1}_{k-1} + C^{n-1}_{k} \text{.}\)

Answer

We could prove this equality just by comparing the factorial formulas involved on the left-hand and right-hand sides. But instead we will consider each of these combination values as representing the number of subsets of a certain size.

Write

\begin{equation*} A = \mathbb{N}_{<n} = \{0,1,2,\ldots,n - 1\} \end{equation*}
so that \(\vert A \vert = n\text{.}\) Then the left-hand side of the equality in the statement of the proposition represents the number of subsets of \(A\) of size \(k\text{.}\) Let's break that collection of subsets into two subcollections.

Subsets of \(A\) of size \(k\) that contain \(0\).
Each of these subsets will consist of \(0\) along with \(k - 1\) nonzero elements. As \(A\) contains \(n - 1\) nonzero elements from which to choose, there are \(C^{n-1}_{k-1}\) ways to select those additional subset elements from \(A\text{.}\)

Subsets of \(A\) of size \(k\) that do not contain \(0\).
Each of these subsets must consist of \(k\) nonzero elements. As \(A\) contains \(n - 1\) nonzero elements from which to choose, there are \(C^{n-1}_{k}\) ways to select those subset elements from \(A\text{.}\)

Adding these two disjoint cases together using the Addition Rule yields the right-hand side of the equality.

Proposition \(\PageIndex{2}\)

For \(n\ge 0\text{,}\) we have \(\displaystyle \sum_{k=0}^n C^n_k = 2^n\text{.}\)

Proof.

First, recall that the notation on the left-hand side is summation notation:

\begin{equation*} \sum_{k=0}^n C^n_k = C^{n}_{0} + C^{n}_{1} + \cdots + C^{n}_{n} \text{.} \end{equation*}
Let \(A = \mathbb{N}_{<n}\text{,}\) so that \(\vert A \vert = n\text{.}\) Then \(\vert \mathscr{P}(A) \vert = 2^n\) (Theorem 12.2.9). So the right-hand side of the equality represents the number of possible subsets of \(A\text{.}\)

On the other hand, for each index \(k\) in the sum on the left-hand side, the term \(C^n_k\) is the number of subsets of \(A\) of size \(k\text{.}\) Using the Addition Rule, the sum of these terms must also be the total number of possible subsets of \(A\text{.}\)

Here is one further property of the choose function.

Proposition \(\PageIndex{3}\)

For \(0 \le m \le n\text{,}\) we have

\begin{equation*} C^{n+1}_{m+1} = \sum_{k=m}^n C^{k}_{m} \text{.} \end{equation*}

Proof.

Suppose \(A\) is a finite set with \(\vert A \vert = n + 1\text{.}\) (For example, we could use \(A = \mathbb{N}_{<n+1}\text{,}\) but that might get confusing between numbers as elements of \(A\) and numbers as cardinalities of subsets of \(A\text{.}\)) Then the left-hand side of the equality is the number of subsets of \(A\) of size \(m + 1\text{.}\) Here is a systematic way we could create that those subsets.

Choose an ordering of the elements of \(A\text{,}\) so that

\begin{equation*} A = \{a_1,a_2,\ldots,a_{n+1}\} \text{,} \end{equation*}
though we will not count this choice of ordering. Then, proceed as follows.

1. Write

\begin{equation*} B_1 = \{a_1,a_2,\ldots,a_{m+1}\}\text{,} \end{equation*}
so that \(B_1 \subseteq A\) with \(\vert B_1 \vert = m + 1\text{.}\) Then there is exactly \(1 = C^{m+1}_{m+1}\) subset of \(B_1\) of size \(m + 1\text{,}\) which is \(B_1\) itself. And this subset of \(B_1\) is also a subset of \(A\text{.}\)

2. Write

\begin{equation*} B_2 = \{a_1,a_2,\ldots,a_{m+1},a_{m+2}\}\text{,} \end{equation*}
so that \(B_1 \subseteq B_2 \subseteq A\) with \(\vert B_2 \vert = m + 2\text{.}\) Using only the elements of \(B_2\text{,}\) to create a new subset \(X \subseteq A\) of size \(m + 1\) that we have not already counted we must include the new element \(a_{m+2}\text{,}\) with the remaining \(m\) elements to make up \(X\) chosen from \(B_1\text{.}\) So we get \(C^{m+1}_{m}\) new subsets of \(A\) of size \(m+1\) from \(B_2\text{.}\)

3. Write

\begin{equation*} B_3 = \{a_1,a_2,\ldots,a_{m+1},a_{m+2},a_{m+3}\}\text{,} \end{equation*}
so that \(B_2 \subseteq B_3 \subseteq A\) with \(\vert B_3 \vert = m + 3\text{.}\) Using only the elements of \(B_3\text{,}\) to create a new subset of \(X \subseteq A\) of size \(m + 1\) that we have not already counted we must include the new element \(a_{m+3}\text{,}\) with the remaining \(m\) elements to make up \(X\) chosen from \(B_2\text{.}\) So we get \(C^{m+2}_{m}\) new subsets of \(A\) of size \(m+1\) from \(B_3\text{.}\)

And so on. The last step in this process is when we create new subsets of size \(m+1\) by first choosing to include \(a_{n+1}\text{,}\) and then choosing the remaining \(m\) elements from \(A \smallsetminus \{a_{n+1}\}\text{,}\) giving us \(C^{n}_{m}\) new subsets.

Every subset \(X \subseteq A\) of size \(m + 1\) is accounted for in the above process, since every such subset must contain at least one element with index \(m + 1\) or larger. If \(a_N\) is the element in \(X\) with the largest index, then \(X\) is one of the subsets considered in step \(\ell\text{,}\) where \(N = m + \ell\text{.}\)

So adding up each of these disjoint cases using the Addition Rule must yield the total number of subsets of \(A\) of size \(m + 1\text{.}\) Replacing the \(C^{m+1}_{m+1}\) total from the first step with \(C^{m}_{m}\) (since both are equal to \(1\)) to match the pattern of the subsequent steps, we obtain

\begin{equation*} C^{n+1}_{m+1} = C^{m}_{m} + C^{m+1}_{m} + \cdots + C^{n}_{m} \text{,} \end{equation*}
as desired.