Binomial Coefficients

Section 2.2 Binomial Coefficients

Binary strings are closely related to subsets of finite sets, which is our next topic.

Definition 2.2.1.

Given a set \(A\text{,}\) a subset of \(A\) is a set of elements of \(A\text{.}\) The collection of all subsets of \(A\) is called the power set of \(A\) and is denoted by \(2^A\text{.}\) We write \([n]:=\{1,2,\ldots,n\}\) to denote the set of integers between \(1\) and \(n\text{.}\)

🔗

Example 2.2.2.

Suppose that we have the set \([6]:=\{1,2,3,4,5,6\}\text{.}\) Then the set \(\{1,3,4\}\) is a subset of \([6]\text{,}\) while \(\{1,7\}\) is not a subset of \([6]\text{.}\) Thus, we would write \(\{1,3,4\}\in 2^{[6]}\) and we would write \(\{1,7\}\notin 2^{[6]}\text{.}\)

🔗

Checkpoint 2.2.3.

Discuss the above example and the notation used in it. Create another example of a subset and a non-subset of a set.

🔗

Proposition 2.2.4.

There is a one-to-one correspondence between the binary strings in \(\Bin(n)\) and the subsets of \([n]\text{.}\)

🔗

Proof.

We will produce a map from binary strings to subsets of \([n]\text{.}\) We will write this map as a function

\begin{equation*} \phi : \Bin(n)\to 2^{[n]} \, . \end{equation*}

Given a binary string \(a:=(a_1,a_2,\ldots,a_n)\text{,}\) if \(a_i=1\text{,}\) then we include \(i\) in \(\phi(a)\text{.}\) This produces a subset of \([n]\text{.}\)

🔗

What do we need to check to verify that we have a one-to-one correspondence? We need to check that:

this map is well-defined (each binary string goes to only one set),
🔗

🔗
this map is one-to-one (no two strings to go the same subset), and
🔗

🔗
this map is onto (every subset is mapped to by some string).
🔗

🔗

Once these three things are checked, then the proof is complete.

🔗

Checkpoint 2.2.5.

With your group, make a logical argument to justify why each of the three conditions above in the proof hold, which completes our proof that \(\phi\) is a one-to-one correspondence.

🔗

One-to-one correspondences have a special name.

🔗

Definition 2.2.6.

Given two sets \(A\) and \(B\text{,}\) a bijection is a function from \(A\) to \(B\) that is a one-to-one and onto correspondence.

🔗

Fact 2.2.7.

If there is a bijection from \(A\) to \(B\text{,}\) then \(|A|=|B|\text{.}\)

🔗

Corollary 2.2.8.

\(|2^{[n]}|=|\Bin(n)|=2^n \, .\)

🔗

Observe that we use the notation \(2^A\) for the power set of \(A\) because when \(A\) is finite, we have \(|2^A|=2^{|A|}\text{.}\)

🔗

We next introduce some of the best numbers in the entire universe!!!!. Seriously, they are totally awesome.

🔗

Definition 2.2.9.

The number of subsets of \([n]\) of size \(k\) is denoted by \(\binom{n}{k}\) and is called the \((n,k)\)-binomial coefficient. We define \(\binom{0}{0}:=1\text{.}\)

🔗

Checkpoint 2.2.10.

Show that \(\binom{n}{0}=1\text{.}\)

🔗

Checkpoint 2.2.11.

Show that \(\binom{n}{1}=n\text{.}\)

🔗

Checkpoint 2.2.12.

Show that \(\binom{n}{n-1}=n\text{.}\)

🔗

Checkpoint 2.2.13.

What is \(\binom{5}{3}\text{?}\)

🔗

Theorem 2.2.14.

\begin{equation*} \binom{n}{0}+\binom{n}{1}+\cdots + \binom{n}{n-1}+\binom{n}{n} = \sum_{k=0}^n\binom{n}{k}=2^n \end{equation*}

🔗

Proof.

We know that \(2^n\) is the cardinality of the power set of \([n]\text{.}\) Further, we know that in the sum

\begin{equation*} \sum_{k=0}^n\binom{n}{k} \end{equation*}

each subset is counted once by a unique summand. Thus, each of these expressions counts the cardinality of the power set of \([n]\text{,}\) hence they are equal.

🔗

Checkpoint 2.2.15.

Discuss this proof: does it make sense? Why or why not? Check this proof with small examples. Note the strategy is to count the number of subsets of \([n]\) in two different ways, which leads to two different symbolic formulas for the total number.

🔗

Corollary 2.2.16.

There are \(\binom{n}{k}\) binary strings of length \(n\) with \(k\) ones.

🔗

Proof.

There is a one-to-one correspondence between binary strings of length \(n\) with \(k\) ones and subsets of \([n]\) with \(k\) elements. Thus, these two sets have the same cardinality, which is \(\binom{n}{k}\text{.}\)

🔗

Binomial coefficients form a beautiful triangle called the arithmetical triangle, also known as Pascal’s triangle, which happens because of the following arithmetic recurrence.

🔗

Theorem 2.2.17.

For all \(0\leq k\leq n\text{,}\) we have

\begin{equation*} \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \, . \end{equation*}

🔗

Let \(\binom{[n]}{k}\) denote the set of all \(k\)-element subset of \([n]\text{.}\)

🔗

Proof.

We can write this as a disjoint union:

\begin{align} \amp \binom{[n]}{k} = \left\{ A:A\in\binom{[n-1]}{k} \right\}\uplus \left\{ \{n\}\cup A:A\in\binom{[n-1]}{k-1} \right\} \tag{2.2.1} \end{align}

Therefore, we have that the cardinality of the left-hand set is the sum of the cardinalities of the two right-hand sets, which is exactly the formula claimed in the theorem.

🔗

Checkpoint 2.2.18.

Check that (2.2.1) is true for \(n=5,k=2\text{.}\) Then, give a logical argument (a proof!) that it is true for every value of \(n\) and \(k\text{.}\)

🔗

Remark 2.2.19.

Review some of the illustrations at the wikipedia page for Pascal’s triangle

en.wikipedia.org/wiki/Pascal%27s_triangle

🔗

One of the most important roles played by the binomial coefficients, and the reason for their name, is that they appear in coefficients of polynomials that are powers of binomials.

🔗

Theorem 2.2.20.

\begin{equation*} (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k} \end{equation*}

🔗

Proof.

If we distribute all the factors in \((x+y)^n\) but we do NOT commute any variables, then each term is an ordered sequence of \(n\) variables, each either \(x\) or \(y\text{.}\) For example,

\begin{equation*} (x+y)^3 = xxx+xxy+xyx+yxx+xyy+yxy+yyx+yyy \, . \end{equation*}

If we replace each \(x\) with a \(1\) and each \(y\) with a \(0\text{,}\) then each of these terms corresponds to a binary string. Therefore, the coefficient of \(x^ky^{n-k}\) in \((x+y)^n\) is the number of binary strings with \(k\) ones, which is \(\binom{n}{k}\text{,}\) as desired.

🔗

Checkpoint 2.2.21.

Discuss the proof above with your group. Work out some complete examples for small values of \(n\text{.}\)

🔗

Corollary 2.2.22.

\begin{equation*} (x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k \end{equation*}

🔗

Finally, you might be wondering if there is a formula for binomial coefficients, and yes, there is. However, it is important to be able to think about these numbers using both their combinatorial structure (which we have been doing) and using the following formula.

🔗

Theorem 2.2.23.

\begin{equation*} \binom{n}{k} = \frac{n!}{k!(n-k)!} \end{equation*}

🔗

You will see a proof of this later in the course on a homework problem.

🔗

Prev Top Next