Example 4.1.
If \(A=\{a,b,c,d\}\text{,}\) then
\begin{equation*}
\binom{A}{2}=\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\text{,}
\end{equation*}
which implies that \(\binom{4}{2}=6\text{.}\)
Chapter 4 Combinations
The notion of \(k\)-permutations captures arrangements of distinct objects where order matters. But what should we do if we want to capture a situation where the order of the objects does not matter? Since the order of the objects in a set does not matter, this is the model we should use.
If \(A\) is a set and \(B\subseteq A\) with \(|B|=k\text{,}\) we refer to \(B\) as a \(k\)-subset of \(A\text{.}\) The collection of all \(k\)-subsets of \(A\) is defined via
\begin{equation*}
{\binom{A}{k}:=\{B\subseteq A\mid |B|=k\}.}
\end{equation*}
The binomial coefficient is defined via
\begin{equation*}
{\binom{n}{k}:=\text{ number of \(k\)-subsets of an \(n\)-element set } .}
\end{equation*}
In particular, if \(|A|=n\text{,}\) then \(\lvert\binom{A}{k}\rvert=\binom{n}{k}\text{.}\) We read “\(\binom{n}{k}\)” as “\(n\) choose \(k\)”. Alternate notations for binomial coefficients include \(C(n,k)\) and \(_n C_k\text{.}\) We will see later why \(\binom{n}{k}\) is referred to as a binomial coefficient.
Problem 4.2.
For any \(A\text{,}\) including the empty set, what is \(\binom{A}{0}\text{?}\) For \(n\geq 0\text{,}\) what is \(\binom{n}{0}\) equal to?
Problem 4.3.
For \(n\geq 0\text{,}\) what is \(\binom{n}{n}\) equal to?
If we let \(n\) and \(k\) vary, we can organize the binomial coefficients in a triangular array, often referred to as Pascal’s Triangle. See Table 4.1.
| \(n\setminus k\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | 6 |
| \(0\) | \(1\) | ||||||
| \(1\) | \(1\) | \(1\) | |||||
| \(2\) | \(1\) | \(2\) | \(1\) | ||||
| \(3\) | \(1\) | \(3\) | \(3\) | \(1\) | |||
| \(4\) | \(1\) | \(4\) | \(6\) | \(4\) | \(1\) | ||
| \(5\) | \(1\) | \(5\) | \(10\) | \(10\) | \(5\) | \(1\) | |
| \(6\) | \(1\) | \(6\) | \(15\) | \(20\) | \(15\) | \(6\) | \(1\) |
Problem 4.4.
Suppose you have a pool of 6 applicants for a job opening. Let’s assume you believe the values in Table 4.1.
-
How many ways can you choose 3 of the 6 applicants to interview?
-
How many ways can you hire 3 of the 6 applicants for 3 distinct jobs?
Problem 4.5.
What are the row sums in Pascal’s Triangle? That is, what is the following sum equal to for any \(n\geq 0\text{?}\)
\begin{equation*}
\sum_{k=0}^n\binom{n}{k}:=\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n}\text{.}
\end{equation*}
Problem 4.6.
Using the meanings of \(k\)-subset and \(k\)-permutation, explain why
\begin{equation*}
P(n,k)=\binom{n}{k} \cdot k!\text{.}
\end{equation*}
Using the previous problem, we immediately get the following handy formula for computing binomial coefficients.
Theorem 4.7.
For \(0\leq k\leq n\text{,}\) we have
\begin{equation*}
{\binom{n}{k}=\frac{n!}{k!(n-k)!} =\frac{P(n,k)}{k!}.}
\end{equation*}
In the last expression above, the numerator of \(\frac{P(n,k)}{k!}\) is counting how many distinct arrangements (order matters) there are of \(k\) objects taken from \(n\) objects and the denominator is essentially unordering arrangements (by Division Principle) that consist of the same objects.
Problem 4.8.
A state senate consists of 19 Republicans and 14 Democrats. In how many ways can a committee be chosen if:
-
The committee contains 6 senators without regard to party?
-
The committee contains 3 Republicans and 3 Democrats?
Problem 4.9.
How many bit strings of length 10 have exactly three 1’s?
Problem 4.10.
How many bit strings of length 6 have an odd number of 0’s?
Problem 4.11.
As we noted earlier, we did quite a bit of brute force to determine how many paths I could take to get coffee in Problem 1.15. Find a solution that utilizes binomial coefficients.
Problem 4.12.
How many strings of 10 lower-case English letters have exactly two \(g\)’s and exactly three \(v\)’s?
Problem 4.13.
Assume \(1\leq k\leq n\text{.}\)
-
Using the definition of \(\binom{n}{k}\) in terms of \(k\)-subsets (as opposed to the formula in Theorem 4.7), explain why\begin{equation*} {\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.} \end{equation*}This identity is often called Pascal’s Identity (or Pascal’s Recurrence).
-
Connect the formula above with Problem 1.15 involving my walk to get coffee.
Problem 4.14.
Assume \(1\leq k\leq n\text{.}\) It turns out that
\begin{equation*}
{\binom{n}{k}=\binom{n}{n-k}.}
\end{equation*}
-
Prove the identity above using the formula for \(\binom{n}{k}\) given in Theorem 4.7.
-
Explain why the identity is true by using the definition of \(\binom{n}{k}\) in terms of \(k\)-subsets.
The upshot is that each row of Pascal’s Triangle is a palindrome.
Problem 4.15.
Explain why
\begin{equation*}
{1+2+\cdots +n=\binom{n+1}{2}}
\end{equation*}
by counting the number of handshakes that could occur among a group of \(n+1\) people in two different ways.
By the way, the number defined by \({t_n:=1+2+\cdots +n}\) is called the \(n\)th Triangular number (due to the shape we get by representing each number in the sum by a stack of balls).
Problem 4.16.
Without appealing to the previous problem, find a visual proof of the following:
\begin{equation*}
{1+2+\cdots +n=\frac{n(n+1)}{2}}\text{.}
\end{equation*}
Hint: Consider a rectangular array of balls that has \(n\) rows and \(n+1\) columns.
Problem 4.17.
Consider the linear equation \(x_1+x_2+x_3=11\text{.}\) How many integer solutions are there if:
-
\(x_1,x_2,x_3\geq 0\text{?}\)
-
\(x_1,x_2,x_3> 0\text{?}\)
-
\(x_1\geq 1, x_2\geq 0, x_3\geq 2\text{?}\)
Problem 4.18.
How many ways can you distribute 5 identical lollipops to 6 kids?
These last two problems illustrate a technique known as stars and bars. In general, \(n\) stars tally the number of objects and \(k-1\) bars separate them into \(k\) distinct categories.
Theorem 4.19.
The number of possible collections of \(n\) objects of \(k\) different types is
\begin{equation*}
{\binom{n+k-1}{k-1}=\binom{n+k-1}{n}.}
\end{equation*}
Problem 4.20.
Zittles come in 5 colors: green, yellow, red, orange, and purple. How many different collections of 32 Zittles are possible?
