Definition 2.1.1.
A binary string of length \(n\) is an ordered list of \(n\) values which are either \(0\) or \(1\text{.}\)
Section 2.1 Binary Strings
We will begin with one of the most fundamental sets in combinatorics.
We can define binary strings another way, using products of sets. When we define notation, we will use the symbol "\(:=\)" to indicate that it is a definition. This helps to distinguish between when we are defining new notation and when we are proving equality between two objects.
Definition 2.1.2.
Given two sets \(A\) and \(B\text{,}\) the product of these two sets is defined to be
\begin{equation*}
A\times B := \{(a,b):a\in A, b\in B\}
\end{equation*}
which is the set of all ordered pairs where the first element is from \(A\) and the second element is from \(B\text{.}\) The size, or cardinality, of a set is the number of elements in that set, which we denote by \(|A|\text{.}\) If an element \(x\) is in the set \(A\text{,}\) then we write \(x\in A\text{.}\) If \(x\) is not in the set \(A\text{,}\) then we write \(x\notin A\text{.}\)
We can iterate products, so for example, \(A^n\) consists of all ordered lists consisting of \(n\) elements from \(A\text{.}\)
Example 2.1.3.
You already have experience using product notation! For example, you are used to seeing notation such as
\begin{equation*}
\mathbb{R}^3=\mathbb{R}\times \mathbb{R}\times \mathbb{R}
\end{equation*}
in calculus or matrix algebra to represent an ordered list of three real numbers, i.e., a vector of length three.
Remark 2.1.4.
Rules for checkpoints, which will either be a problem to solve or a question to discuss:
-
First, begin the discussion by going around your group and having each person spend 10-seconds sharing an initial strategy for solving the problem, or sharing a answer to the question if it is a discussion question.
-
Second, go around the group again and give a 10-second follow-up answer. This allows everyone to have a chance to offer their thoughts before the general problem-solving or discussion begins.
-
Third, as a group, solve the problem or engage in the discussion for the checkpoint.
Checkpoint 2.1.5.
List the binary strings in \(\{0,1\}^4=\{0,1\}\times\{0,1\}\times\{0,1\}\times\{0,1\}\text{.}\)
Checkpoint 2.1.7.
Suppose that you were asked to make a list of all the binary strings in \(\{0,1\}^{10}\text{.}\)
-
What would your strategy be for listing them? In other words, how would you systematically list all possible binary strings?
-
How do you know that your strategy would result in a complete list of all binary strings of length \(10\text{?}\)
These exercises lead us to the following observation.
Theorem 2.1.8.
We will give two proofs. The first proof uses combinatorial reasoning. Combinatorial reasoning is where you make an argument based on the structure of the set of outcomes that you are studying -- in this case, we are considering the set of binary strings.
Combinatorial Reasoning Proof of Theorem 2.1.8.
A binary string is a list of entries \((a_1,a_2,\ldots,a_n)\text{.}\) Each \(a_i\) is either \(0\) or \(1\text{.}\) Thus, there are \(n\) independent choices to make of either \(0\) or \(1\text{,}\) one choice for each entry, to determine the binary string. This gives
\begin{equation*}
2 \cdot 2 \cdots 2 \cdot 2 = 2^n
\end{equation*}
outcomes, hence our result is proved.
Checkpoint 2.1.9.
Discuss the combinatorial reasoning proof with your group. Does the proof make sense? Why or why not?
The second proof is a proof using recursion. In a recursive proof, we establish a logical argument that uses a known structure to produce a new structure. For this proof, we will need the following.
Fact 2.1.10.
The multiplication principle states that for two finite sets \(A\) and \(B\) we have
\begin{equation*}
|A\times B| = |A|\times |B| \, .
\end{equation*}
We will also need the following definitions. We use \(\emptyset=\{\}\text{,}\) called the empty set, to denote a set with no elements.
Definition 2.1.11.
Given two sets \(A\) and \(B\text{,}\) the union of these two sets is defined to be
\begin{equation*}
A\cup B := \{x: x\in A \text{ and/or } x\in B\} \, .
\end{equation*}
The intersection of these two sets is defined to be
\begin{equation*}
A\cap B := \{x: x\in A \text{ and } x\in B\} \, .
\end{equation*}
If \(A\cap B = \emptyset\text{,}\) then we write the union as \(A\uplus B\) and call it a disjoint union.
Recursive Proof of Theorem 2.1.8.
Let \(\Bin(n)\) denote the set of binary strings of length \(n\text{.}\) Our goal is to prove that \(|\Bin(n)|=2^n\text{.}\) It is straightforward to check that \(|\Bin(1)|=2\) and \(|\Bin(2)|=4=2^2\) and \(|\Bin(3)|=8=2^3\text{.}\)
Our strategy will be to show that if we know \(|\Bin(n)|=2^n\text{,}\) then we can prove \(|\Bin(n+1)|=2^{n+1}\text{.}\) If we show this general statement, then using \(|\Bin(3)|=8=2^3\text{,}\) we can conclude that \(|\Bin(4)|=2^4\text{.}\) Then, knowing \(|\Bin(4)|=2^4\text{,}\) we can conclude that \(|\Bin(5)|=2^5\text{.}\) This chain of logical implications continues, so that we have our desired result for any length of binary strings.
Our strategy is the following observation:
\begin{align}
\amp \Bin(n+1) = \Bin(n)\times \{1\} \uplus \Bin(n)\times \{0\} \tag{2.1.1}
\end{align}
Once we know that (2.1.1) holds, then the result follows because
\begin{align*}
|\Bin(n+1)| \amp = |\Bin(n)\times \{1\} \uplus \Bin(n)\times \{0\}| \\
\amp = |\Bin(n)\times \{1\}| + |\Bin(n)\times \{0\}|\\
\amp = (|\Bin(n)| \times 1) + (|\Bin(n)| \times 1) \\
\amp = 2\cdot |\Bin(n)| = 2\cdot 2^{n}=2^{n+1}
\end{align*}
Checkpoint 2.1.12.
Check that (2.1.1) is true when \(n=3\text{.}\) Work together to generate an argument (a proof!) showing that this is true for every \(n\text{.}\)
Checkpoint 2.1.13.
Discuss with your group why the logical implications in this proof shows that \(|\Bin(n)|=2^n\) for every positive integer \(n\text{.}\)
