Section 2.4 Counting Bit Strings

Strings consisting only of \(\bs{0}\) s and \(\bs{1}\) s, or bit strings, play a central role in computer science. All numbers, data, logical commands, and computer programs are encoded in a computer as bit strings. Similarly, every text message or email message is encoded as a bit string. In fact, we might say that

Bit strings are a fundamental structure of computer science because all of computer science can be defined using bit strings.

In this section, we count bit strings, demonstrate clever ways to count by modeling using bit strings, and discuss exponential notation and logarithms.

Subsection 2.4.A Bit Strings

We start with a definition.

Definition 2.4.1 Bit string.

A character that is \(\bs{0}\) or \(\bs{1}\) is a bit.
A bit string is a string where each character is a bit. For example, \(\bs{1101}\) is a bit string.
The weight of a bit string is the number of \(\bs{1}\) s in the bit string. For example, the bit string \(\bs{1101}\) has length four and weight three.
The empty bit string \(\lambda\text{,}\) pronounced “lambda”, is the unique bit string of length zero. The symbol \(\lambda\) is a place holder. If we had just a blank space, you would not know that we meant the empty bit string. In computer science, the empty bit string is used as a start to build a new bit string. If we start with \(\lambda\) and write \(\bs{1}\) at the end of the string, the resulting bit string is \(\bs{1}\) (and we no longer write \(\lambda\)).

Here is an example of listing bit strings using a possibility tree.

Example 2.4.2 Listing bit strings in a possibility tree.

List all bit strings of length three by drawing a possibility tree.
Solution.

We draw the possibility tree in Figure 2.4.3. The list is \(\bs{000}\text{,}\) \(\bs{001}\text{,}\) \(\bs{010}\text{,}\) \(\bs{011}\text{,}\) \(\bs{100}\text{,}\) \(\bs{101}\text{,}\)\(\bs{110}\text{,}\) \(\bs{111}\text{.}\)

Figure 2.4.3. The possibility tree of all bit strings of length three.
List all bit strings of length four and weight two.
Solution.

We draw the possibility tree below. Each bit string has weight two, which means that it has exactly two \(\bs{1}\) s and two \(\bs{0}\) s. In the tree we need to be careful– any time we have two \(\bs{1}\) s or two \(\bs{0}\) s, we have only one branch (either to just \(\bs{0}\) or to just \(\bs{1}\)) instead of the usual two branches (to \(\bs{0}\) and to \(\bs{1}\)). The strings are \(\bs{0011}\text{,}\) \(\bs{0101}\text{,}\) \(\bs{0110}\text{,}\) \(\bs{1001}\text{,}\) \(\bs{1010}\text{,}\) \(\bs{1100}\text{.}\)

Figure 2.4.4. The possibility tree of all bit strings of length four and weight two.

Now it is your turn to work with bit strings.

Activity 2.4.A Listing bit strings.

Give an example of a bit string of length four.
Give an example of a bit string of length five and weight three.
List all bit strings of length four using a possibility tree. Be sure to include the list itself.
Make a table showing the number of bit strings of length \(n\) for \(n= 1, 2, 3, 4\text{.}\) Hint: You can count the answers in your possibility tree from (c).
Based on the values in your table, how many bit strings of length five should there be?
Explain how you can use steps Theorem 2.2.3 to count the number of bit strings of length five. Did you get the same answer?
Conjecture the number of bit strings of length \(n\text{.}\)
List the bit strings of length five and weight three by drawing a possibility tree. Your tree should include only those bit strings.

Subsection 2.4.B Number of Bit Strings

One special situation that is counted using steps is the number of bit strings of length \(n\text{.}\) Make sure that you have completed Activity 2.4.A because we are about to reveal the answers.

Example 2.4.6 Conjecture number of bit strings of length \(n\).

How many bit strings of length \(n\) are there? State your answer as a conjecture.

Solution.

There is one bit string of length 0 (\(\lambda\)), two bit strings of length one (\(\bs{0}\text{,}\) \(\bs{1}\)) and four bit strings of length two (\(\bs{00}\text{,}\) \(\bs{01}\text{,}\) \(\bs{10}\text{,}\) \(\bs{11}\)). In Example 2.4.2, we listed the eight bit strings of length three. In Activity 2.4.B, we counted 16 bit strings of length four and 32 bit strings of length five. Notice that each integer is twice the previous number, suggesting that we are multiplying by two. Table 2.4.7 shows these examples written as a product of twos.

Table 2.4.7. The number of bit strings of length \(n\) for \(n=1,2,3,4,5\)

\(n\)	Number of bit strings of length \(n\text{.}\)

0	1

1	\(2 = 2\)

2	4 = \(2 \times 2\)

3	\(8 = 2 \times 2 \times 2\)

4	\(16 = 2 \times 2 \times 2 \times 2\)

5	\(32 = 2 \times 2 \times 2 \times 2 \times 2\)

Based on these examples, it is reasonable to conjecture that there are

\begin{equation*} \underbrace{2 \times 2 \times \ldots \times 2}_{n \text{ times } } \end{equation*}

bit strings of length \(n\text{.}\)

Products in the format of the answer to Example 2.4.6 occur often enough that they have a name and notation. For example, our product is 2 to the power of \(n\) which is denoted

\begin{equation*} 2^n= \underbrace{2\times 2 \times \ldots \times 2} _{n \text{ times } } \end{equation*}

We can prove our conjecture from Example 2.4.6 using steps.

Theorem 2.4.8 Number of bit strings of length \(n\).

There are \(2^n\) bit strings of length \(n\text{.}\)

Proof.

Imagine building each bit string of length \(n\) by filling in the \(n\) spaces:

\begin{equation*} \underline{}~\underline{} ~\underline{}~\ldots ~\underline{}~ \end{equation*}

There are two ways to fill in each space: either \(\bs{0}\) or \(\bs{1}\text{.}\) We fill in the spaces in a sequence of steps.

Step 1: Fill in the first space (2 ways).

Step 2: Fill in the second space (2 ways).

Step 3: Fill in the third space (2 ways).

We continue to fill spaces until Step \(n\text{:}\) Fill in the last space (2 ways).

Since steps multiply Theorem 2.2.3, the total number of bit strings of length \(n\) is

\begin{equation*} \underbrace{ 2 \times 2 \times \ldots \times 2} _{n \text{ times } } = 2^n \end{equation*}

Let’s practice counting bit strings.

Activity 2.4.B Counting bit strings.

How many bit strings of length eight are there?
How many bit strings of length eight and weight one are there? Hint: How many places are there for the one \(\bs{1}\text{?}\)
How many bit strings of length eight and weight two are there? Hint: We can build such a bit string by putting a \(\bs{0}\) or \(\bs{1}\) in each of eight spaces:

\begin{equation*} \underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~ \end{equation*}

but we need exactly two spaces to have \(\bs{1}\) so filling in the spaces from left to right will not work and there are too many to draw a possibility tree. Instead, consider choosing which two spaces to fill in with \(\bs{1}\text{.}\) Since the remaining spaces are \(\bs{0}\) s, the number of bit strings of length eight and weight two equals the number of ways to choose the two spaces for \(\bs{1}\) s.
Conjecture the number of bit strings of length \(n\) with weight \(k\) or, equivalently, exactly \(k\) \(\bs{1}\) s.

Sometimes, a counting problem asks about subsets of a set, which is convenient because \(\binom{n}{k}\) counts the number of \(k\)-element subsets of a set of \(n\) elements. As we saw in Activity 2.4.B, a counting problem might have nothing to do with subsets, but we can rephrase the problem in terms of subsets. Here is another example.

Example 2.4.10 Bit strings of length 100 and weight three.

How many bit strings of length 100 and weight three are there?

Solution.

Let’s figure out a way to rephrase this problem in terms of subsets. We can build such a bit string by putting a \(\bs{0}\) or \(\bs{1}\) in each of 100 spaces:

\begin{equation*} \underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}\dots\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}} \end{equation*}

Following the hint in Activity 2.4.B, let’s choose which spaces have \(\bs{1}\) s.

Step 1: Fill in three spaces with \(\bs{1}\text{.}\) We choose a subset of three spaces for \(\bs{1}\) s from the set of 100 spaces. There are \(\binom{100}{3}\) ways to do this step.

Step 2: Fill in the remaining 97 spaces with \(\bs{0}\text{.}\) There is one way to do this step because the 97 \(\bs{0}\) s go into the remaining 97 spaces. Alternatively, you can think of choosing a subset of 97 spaces for the \(\bs{0}\) s from the set of 97 remaining spaces. There are \(\binom{97}{97} =1\) ways to do this step.

Since steps multiply Theorem 2.2.3, there are \(\binom{100}{3}(1) = \binom{100}{3}\) bit strings of length 100 and weight three. Our final answer is \(\binom{100}{3}\text{,}\) which a quick internet search shows equals 161,700 , too many to list by hand!

We can generalize our answer and rationale from Example 2.4.10, to get a formula for the number of bit strings of length \(n\) with exactly \(k\) \(\bs{1}\) s (or with exactly \(k\) \(\bs{0}\) s).

Theorem 2.4.11 Number of bit strings of length \(n\) with exactly \(k\) \(\str{1}\)s (or with exactly \(k\) \(\str{0}\)s).

The number of bit strings of length \(n\) with exactly \(k\) \(\bs{1}\) s (or with exactly \(k\) \(\bs{0}\) s) is \(\binom{n}{k}\text{.}\)

Let’s see this theorem in action.

Example 2.4.12 Counting bit strings with given number of \(\bs{0}\)s or \(\bs{1}\)s.

Count the number of bit strings of length five and weight three.
Solution.

By Theorem 2.4.11, there are \(\binom{5}{3}\) bit strings of length five and weight three. Note that \(\binom{5}{3}=10\text{,}\) which should agree with the tree you drew in Activity 2.4.A (h).
Count the number of bit strings of length eight and weight two.
Solution.

By Theorem 2.4.11, there are \(\binom{8}{2}\) bit strings of length eight and weight two, which is the answer to Activity 2.4.B (c).
How many bit strings of length 100 are exactly half \(\bs{0}\) s and half \(\bs{1}\) s?
Solution.

By Theorem 2.4.11 there are \(\binom{100}{50}\) such bit strings.

Subsection 2.4.C Detour: Rephrasing the Question

Sometimes a counting problem does not mention bit strings, but we can rephrase the problem in terms of bit strings, which is convenient because we know Theorem 2.4.8 and Theorem 2.4.11. Try your hand at such an example.

Activity 2.4.C From point \(a_1\) to point \(c_4\).

In this activity we are interested in direct paths from \(a_1\) to \(c_4\) in Figure 2.4.14. We begin each direct path at \(a_1\) and then walk one unit to the right or one unit down at each step until we reach \(c_4\text{.}\) We are not allowed to walk to the left or up.

Figure 2.4.14. Going from point \(a_1\) to point \(c_4\text{.}\)

Give an example of a direct path from \(a_1\) to \(c_4\text{.}\) How many steps did you take?
Draw a possibility tree to list all possible direct paths. Hint: The original node is \(a_1\) which has branches to \(a_2\) and to \(b_1\text{.}\)
How many direct paths from \(a_1\) to \(c_4\) are there?
We can represent each path by a bit string where \(\bs{1}\) represents walking one unit to the right and \(\bs{0}\) represents walking one unit down. What is the bit string whose path is \(a_1a_2b_2b_3c_3c_4\text{?}\)
What is the path whose bit string is \(\bs{00111}\text{?}\)
Explain how to use Theorem 2.4.11 to count the number of paths. You should get the same answer as in (c).
We can describe the grid in Figure 2.4.14 as being \(3 \times 4\) because it has 3 rows of letters and 4 columns of letters. Conjecture the number of direct paths from the upper left corner to the lower right corner in a \(5 \times 7\) grid.
Generalize. That means conjecturing the number of direct paths from the upper left corner to the lower right corner in a \(r \times c\) grid.

Subsection 2.4.D Algebra: Exponential Notation and Logarithms

In Theorem 2.4.8, we proved that there are \(2^n\) bit strings of length \(n\) where

\begin{equation*} 2^n=\underbrace{2\times 2 \times \ldots \times 2}_{n \text{ times } } \end{equation*}

This exponential notation is a shorthand for a product of the same number multiplied by itself repeatedly.

Definition 2.4.15 Exponential notation.

When \(n\) is a positive integer, \(b\) raised to the power of \(n\) (or just \(b\) to the \(n\)) is

\begin{equation*} b^n = \underbrace{b\times b \times \ldots \times b}_{n \text{ times } } \end{equation*}

For example,

\begin{equation*} 2^5 = \underbrace{2 \times 2 \times 2 \times 2 \times 2}_{5 \text{ times } } = 32 \end{equation*}

and

\begin{equation*} (-2)^5 = \underbrace{(-2) \times (-2) \times (-2) \times (-2) \times (-2)}_{5 \text{ times } } = -32\text{.} \end{equation*}

Note that exponentiation is not commutative. For example, \(2^5=32\) but \(5^2 = 5 \times 5 = 25\text{.}\) We practice evaluating powers without using technology to understand the definition, but, of course, you can use technology to check. Many computational tools, such as calculators, spreadsheet programs, or an Internet search, use the notation \(\land\) to indicate a power.
In the expression \(b^n\text{,}\) the integer \(b\) is the base, the number that we are repeatedly multiplying. The integer \(n\) is the exponent, the number of times we multiply the base. The quantity \(b^n\) is the power of \(b\text{,}\) the final product. For example, in \(2^5\text{,}\) the base is 2, the exponent is 5, and the power of 2 is 32.
For \(b\neq 0\text{,}\) it is convenient to define \(b^0=1\text{.}\) For example, \(2^0=1\) is the number of bit strings of length zero.
The expression \(b^2\) is \(s\) squared. For example, \(10^2 = 10 \times 10 = 100\text{.}\) This name comes from the fact that the area of a square with sides of length \(b\) is \(b^2\text{.}\)
The expression \(b^3\) is \(b\) cubed. For example, \(4^3 = 4 \times 4 \times 4 = 64\text{.}\) This name comes from the fact that the volume of a cube with sides of length \(b\) is \(b^3\text{.}\)

Let’s work with these definitions.

Example 2.4.16 Exponential notation.

In this example, we only use technology to check our answers.

Evaluate \(10^4\text{.}\)
Solution.

By definition,

\(10^4\) = \(\underbrace{10 \times 10 \times 10 \times 10}_{4 \text{ times } }\)

= \(100 \times 10 \times 10\)

= \(1{,}000 \times 10\)

= \(10{,}000\text{.}\)

Check that \(10 \land 4 =\) 10,000. Notice that \(10^4\) has 4 zeros.
Evaluate \((-10)^4\) and \(-10^4\text{.}\)
Solution.

By definition,

\((-10)^4\) = \(\underbrace{(-10) \times (-10) \times (-10) \times (-10)}_{4 \text{ times } }\)

= \(100 \times (-10) \times (-10)\)

= -1,000 \(\times (-10)\)

= 10,000.

Check that \((-10) \land 4 = 10{,}000\text{.}\) On the other hand, according to Definition 2.1.20 (a), exponents are higher in the order of operations in than subtraction (and negation), so

\begin{equation*} -10^4=-(10^4)=-10,000\text{.} \end{equation*}

Check that \(-10 \land 4 = -10{,}000\text{.}\)
Evaluate \(3^1\text{.}\)
Solution.

By definition,

\begin{equation*} 3^1 = \underbrace{3}_{1 \text{ time } } = 3\text{.} \end{equation*}

Check that \(3 \land 1 = 3\text{.}\)
Evaluate \(5^0\text{.}\)
Solution.

By definition, \(5^0 =1\) and check that \(5 \land 0 =1\text{.}\)

It can be useful to write an integer as a power of a base \(b\text{.}\) For example, we can write \(10,000 =10^4\) or \(32 = 2^5\text{.}\) There is a name for the exponent.

Definition 2.4.17 Logarithm.

The logarithm base 10 of an integer \(k\text{,}\) denoted \(\fn{log}(k)\) is the exponent of the power 10 that equals \(k\text{.}\) That is, \(\fn{log}(k)=n\) if \(10^n=k\text{.}\) For example, \(\fn{log}(100 ) = 2\) because \(10^2=100\text{.}\)
The logarithm base 2 of an integer \(k\text{,}\) denoted \(\fn{lg}(k)\text{,}\) is the exponent of the power of 2 that equals \(k\text{.}\) That is, \(\fn{lg}(k)=n\) if \(2^n=k\text{.}\) For example, \(\fn{lg}(32) = 5\) because \(2^5=32\text{.}\)
In this textbook, we only use base 2 and base 10, but logarithms can be defined in general.
¹

In this textbook, we only calculate logarithms of exact powers. We do not calculate quantities such as \(\fn{log}(25)\) or \(\fn{lg}(3)\text{.}\) We have defined \(b^n\) when \(n\) is a nonnegative integer, but it is beyond the scope of this textbook to define what \(b^x\) for any real number \(x\text{.}\) With that definition, we can take evaluate logarithms of any positive real number. For example, \(\fn{log}(25) \approx 1.398\) and \(\fn{lg}(3) \approx 1.585\text{.}\)
The logarithm base \(b\) of an integer \(k\text{,}\) denoted \(\fn{log}_b(k)\) is the exponent of the power of \(b\) that equals \(k\text{.}\) That is, \(\fn{log}_b(k)=n\) if \(b^n=k\text{.}\) For example, \(\fn{log}_5(125) = 3\) because \(5^3=125\text{.}\) In this notation, \(\fn{log}\) is short for \(\fn{log}_{10}\) and \(\fn{lg}\) is short for \(\fn{log}_2\text{.}\) In calculus, a noninteger base \(b=e \approx 2.718\) is important. The corresponding logarithm is named \(\str{ln}\text{.}\)

Here are a few more examples.

Example 2.4.18 Evaluating logs.

In this example, we evaluate without using technology.

Evaluate \(\fn{log}(1,000,000 )\text{.}\)
Solution.

Since \(1,000,000 = 10^6\text{,}\) it follows that \(\fn{log}(1,000,000 )=6\text{.}\)
Evaluate \(\fn{lg}(4)\) and \(\fn{lg}(256)\text{.}\)
Solution.

First, since \(2^2=4\text{,}\) it follows that \(\fn{lg}(4)=2\text{.}\) Next, since \(2^8=256\text{,}\) it follows that \(\fn{lg}(256)=8\text{.}\)

Practice working with exponents and logarithms.

Activity 2.4.D Exponents and logarithms.

On this problem, only use technology to check your answers.

Evaluate \(10^6\text{,}\) \(3^2\text{,}\) \(10^0\text{,}\) \(2^3\text{.}\)
Evaluate \((-3)^2\text{,}\) \(-3^2\text{,}\) \((-2)^3\text{,}\) \(-2^3\text{.}\)
Evaluate \(\fn{log}(1,000 )\text{,}\) \(\fn{log}(10)\text{,}\) and \(\fn{log}(1)\text{.}\)
Evaluate \(\fn{lg}(16)\text{,}\) \(\fn{lg}(128 )\text{,}\) and \(\fn{lg}(2)\text{.}\)
Find an integer \(k\) such that \(\fn{log}(k) = 10\text{.}\)
Find an integer of \(n\) such that \(\fn{lg}(n) = 10\text{.}\)
Simplify \(2^32^5\) by writing it as a single power.
Simplify \((2^3)^2\) by writing it as a single power.
Simplify \(2(2^{n-1})\) by writing it as a single power.

Let’s look at examples of writing a combination of powers as a single power.

Example 2.4.20 Simplifying exponents.

Simplify \(2^42^6\) by writing it as a single power.
Solution.

Using Definition 2.4.15, we have

\begin{align*} 2^42^6 \amp = (\underbrace{2\times 2\times 2 \times 2}_{4 \text{ times } }) \times (\underbrace{2\times 2\times 2 \times 2 \times 2 \times 2}_{6 \text{ times } })\\ \amp = \underbrace{2\times 2\times 2\times 2\times 2 \times 2 \times 2 \times 2 \times 2 \times 2}_{10 \text{ times } })\\ \amp = 2^{10}\text{.} \end{align*}

Notice that the base remains 2 and that since the powers shared a common base, the exponents added: \(4+6=10\text{.}\)
Simplify \((10^2)^3\) by writing it as a single power.
Solution.

Using Definition 2.4.15, we have

\begin{align*} (10^2)^3 \amp = (\underbrace{10^2\times 10^2\times 10^2}_{3 \text{ times } })\\ \amp = (\underbrace{(10 \times 10)\times (10 \times 10)\times (10 \times 10)}_{3 \text{ times } })\\ \amp = \underbrace{10\times 10\times 10\times 10\times 10 \times 10}_{6 \text{ times } })\\ \amp = 10^6\text{.} \end{align*}

Notice that the exponents multiplied: \(2 \times 3=6\text{.}\)
Write \(8^2\) as a power of 2.
Solution.

First, write \(8 = 2^3\text{.}\) Then, using what we learned in (b) we get

\begin{equation*} 8^2=\left(2^3\right)^2 = 2^{2\times 3}=2^6\text{.} \end{equation*}

You can check that \(8^2=64\) and \(2^6=64\text{.}\)

We state these rules for exponents as a theorem, but, when in doubt, we suggest that you use the definition instead.

Theorem 2.4.21 Simplifying exponents.

For any integer \(b\) and positive integers \(n\) and \(m\) we have the following rules.

Simplifying a product of powers (of the same base): \(b^mb^n=b^{m+n}\text{.}\)
Simplifying a power of a power: \(\left(b^m\right)^n=b^{mn}\text{.}\)

Here is an example of a common expression that we can simplify using these rules.

Example 2.4.22 Simplify \(2\cdot2^{n-1}\).

Simplify \(2\cdot2^{n-1}\) using Theorem 2.4.21.
Solution.

We can write \(2=2^1\) to get

\begin{equation*} 2\cdot2^{n-1} = 2^12^{n-1}=2^{1+(n-1)}=2^n \end{equation*}
Confirm your answer to (a) using the definition of exponents.
Solution.

We can write

\begin{equation*} 2\cdot2^{n-1} = 2 \times \underbrace{2 \times 2 \times \cdots \times 2}_{(n-1) \text{ times } } = \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times } } =2^n \end{equation*}

It is acceptable to leave exponential notation or logarithms in your answers.

Remark 2.4.23 Not evaluating counts, final version.

Unless stated otherwise, when counting you may leave any answer greater than twenty in a format that could easily be evaluated on a calculator. In particular, your answer may involve addition, subtraction, multiplication, division, exponents, logarithms, factorials, binomial coefficients, and parentheses.

Subsection 2.4.E Exercises

Subsubsection Exercises for 2.4.A Bit Strings

1. Practice.

Calculate the length and weight of the bit string \(\bs{101100}\text{.}\)
Calculate the length and weight of the bit string \(\bs{0}\text{.}\)
Give an example of a bit string of length ten and weight four.

Check.

Length six and weight three.
Length one and weight zero.
Hint: your bit string should have four \(\bs{1}\) s and six \(\bs{0}\) s.

2. Practice.

List all bit strings of length five and weight two using a possibility tree.

3. Understand.

In each part, list all bit strings of length five satisfying the stated property using a possibility tree. In each case, your tree should only include the bit strings that satisfy the stated property.

Bit strings with more \(\bs{0}\) s than \(\bs{1}\) s.
Bit strings that do not contain consecutive \(\bs{0}\) s, which means that \(\bs{00}\) does not appear in the bit string.
Bit strings where any \(\bs{0}\) is immediately followed by \(\bs{1}\text{.}\)

Check.

Hint: Start the possibility tree with two branches to \(\bs{0}\) and \(\bs{1}\text{,}\) as usual. Next, branch to \(\bs{0}\) and \(\bs{1}\) again. After that, you need to be careful. If you ever have two \(\bs{1}\) s then the remainder of the bits are all \(\bs{0}\) s. There are 16 such bit strings. One is all \(\bs{0}\) s, five that have four \(\bs{0}\) s, and ten that have three \(\bs{0}\) s.
Hint: Start the possibility tree with two branches to \(\bs{0}\) and \(\bs{1}\text{,}\) as usual. After that, you need to be careful. After every \(\bs{1}\) there are still two branches (to \(\bs{0}\) and to \(\bs{1}\)), but after every \(\bs{0}\) there is a single branch to \(\bs{1}\text{.}\)
Hint: This part is similar to (b), except that the bit string must end in \(\bs{1}\) because a final \(\bs{0}\) would not be immediately followed by \(\bs{1}\text{.}\)

4. Recap.

Do you know …

What a bit is?
How to calculate the length of a bit string or construct a bit string of a given weight?
How to calculate the weight of a bit string or construct a bit string of a given weight?
What the symbol for empty bit string is?

5. Explore.

The Hamming distance between two bit strings is the number of places where their bits differ. For example, the Hamming distance between \(\bs{10011}\) and \(\bs{11010}\) is two because they have the same first bits (both \(\bs{1}\)), different second bits, the same third bits (both \(\bs{0}\)), the same fourth bits (both \(\bs{1}\)), and different fifth bits. Since the bit strings differ in two places (second and fifth), their Hamming distance equals two. Hamming distance is used in error-correcting codes to ensure the correct transmission of messages such as text messages.

Calculate the Hamming distance between \(\bs{00011}\) and \(\bs{11111}\text{.}\)
List all bit strings that are Hamming distance one from \(\bs{00011}\text{.}\)
Give an example of a bit string that is Hamming distance two from \(\bs{00011}\text{.}\)
If \(b\) is any bit string of length five, how many bit strings are Hamming distance one from \(b\text{?}\) Explain.
If \(b\) is any bit string of length five, how many bit strings are Hamming distance two from \(b\text{?}\) Explain.

Check.

Three
\(\bs{10011}\text{,}\) \(\bs{01011}\text{,}\) …, \(\bs{00010}\) Note that these are organized by which bit is different: first, second, …, fifth
Hint: check that exactly two bits are different.
Hint: See the note under (b).
Hint: We need to choose which two out of five bits to change.

Subsubsection Exercises for 2.4.B Number of Bit Strings

6. Practice.

Use the relevant theorems.

How many bit strings of length twenty are there?
How many bit strings of length twenty contain exactly three \(\bs{1}\) s?
How many bit strings of length twenty contain exactly three \(\bs{0}\) s?

Check.

\(\displaystyle 2^{20}\)
\(\displaystyle \binom{20}{3}\)
Hint: There are two ways to do this problem. We can choose the three places out of 20 for the \(\bs{0}\) s or we can choose the 17 places out of 20 for the \(\bs{1}\text{.}\) Either answer is correct.

7. Understand.

Use the relevant theorems.

How many bit strings of length nine are there?
How many bit strings of length nine or ten are there? Hint: Use cases.
Which number is greater: the number of bit strings of length nine or the number of bit strings of length less than nine? Calculate the actual numbers using technology. Note: do not forget the empty bit string.

8. Understand.

How many bit strings of length 100 begin with \(\bs{0}\text{?}\) Explain.
How many bit strings of length 100 begin with \(\bs{00}\text{?}\) Explain.
How many bit strings of length 100 begin with \(\bs{1}\) and end in \(\bs{0}\text{?}\)
How many bit strings of length 100 begin with or end in \(\bs{0}\text{?}\) Hint: To avoid double counting of bit strings that begin with \(\bs{0}\) and end in \(\bs{0}\text{,}\) consider Case 1: begins with \(\bs{0}\) and Case 2: begins with \(\bs{1}\) and ends in \(\bs{0}\text{.}\)

Check.

\(2^{99}\text{.}\) Hint: Steps multiply Theorem 2.2.3.
Hint: There are \(100-2=98\) spaces left to fill in.
Hint: Use the hint from (b).
Hint: Case 1 is similar to (b) and case 2 is exactly (c). Cases add Theorem 2.2.7.

9. Recap.

Do you know …

How many bit strings of length \(n\) there are?
How many bit strings of length \(n\) have exactly \(k\) \(\bs{1}\) s (or exactly \(k\) \(\bs{0}\) s)?

10. Explore.

A balanced ternary string is a string where each character is \(\bs{0}\text{,}\) \(\str{+}\text{,}\) or \(\str{-}\text{.}\) For example, \(\str{+0+}\) is a balanced ternary string of length five.

Draw a possibility tree listing all balanced ternary strings of length three.
How many balanced ternary strings of length three are there?
Count the number of balanced ternary strings of length ten.
How many balanced ternary strings of length \(n\) are there? State your answer as a conjecture.

11. Explore.

Consider strings using only the characters \(\str{A}\text{,}\) \(\str{B}\text{,}\) \(\str{C}\text{,}\) and \(\str{D}\text{.}\) Recall that a string is ordered and repeats are allowed. Also, we do not need to use all the characters.

How many such strings consist of exactly two \(\str{A}\) s and three \(\str{B}\) s?
How many such strings consist of exactly two \(\str{A}\) s, three \(\str{B}\) s, and four \(\str{C}\) s?
How many such strings consist of exactly two \(\str{A}\) s, three \(\str{B}\) s, four \(\str{C}\) s, and five \(\str{D}\) s?

Check.

Hint: Step 1 is to choose two of the five spaces for the \(\str{A}\) s. Step 2 is to choose three of the three remaining spaces for the \(\str{B}\) s. Note that there is only one way to do Step 2 (so you can safely ignore it).
One way of stating the answer is \(\binom{9}{2}\binom{7}{3}\binom{4}{4}\text{.}\)
Hint: Figure out how we got the answer to (b) and generalize.

12. Explore.

Conjecture the number of permutations of the set \(\{\str{1},\str{2},\ldots, \str{n}\}\text{.}\)
Prove your conjecture in the style of our proof of Theorem 2.4.8.

Subsubsection Exercises for 2.4.C Detour: Rephrasing the Question

13. Practice.

We are interested in going from \(a_1\) to \(c_4\) in Figure 2.4.14. As in Activity 2.4.C, we can represent each path by a bit string where \(\bs{1}\) represents walking one unit to the right and \(\bs{0}\) represents walking one unit down.

What is the bit string whose path is \(a_1b_1b_2b_3c_3c_4\text{?}\)
What is the path whose bit string is \(\bs{11010}\text{?}\)

Check.

\(\displaystyle \bs{01101}\)
\(\displaystyle a_1a_2a_3b_3\ldots\)

14. Understand.

You have fifteen (identical) coins. You want to put some coins in your piggy bank, some in your change jar at work, and some in your car.

How many ways are there to distribute your coins to these three locations? Note that “some” could mean zero in this context. Hint: Line up the fifteen coins. Put a dividing line after those you plan to put in the piggy bank, if any, and another line after those you plan to put in your change jar, if any. The remaining coins, if any, will go in your car. For example: six coins in the piggy bank, two coins in the change jar, and seven coins in the car could be represented as:

\begin{equation*} \circ ~ \circ ~ \circ ~ \circ ~ \circ ~ \circ ~ \mid ~ \circ ~ \circ ~ \mid ~ \circ ~ \circ ~ \circ~ \circ ~ \circ ~ \circ ~ \circ ~ \end{equation*}

whereas three coins in the piggy bank and the rest in the change jar would be:

\begin{equation*} \circ ~ \circ ~ \circ ~ \circ ~ \mid ~ \circ ~ \circ ~ \circ ~ \circ ~ \circ ~ \circ ~ \circ~ \circ ~ \circ ~ \circ ~ \circ ~ \mid ~ \end{equation*}

Explain how to rephrase our question about the coins as a question about bit strings. Then answer the question. Hint to the last part of the hint: squint.
Conjecture about the number of ways to distribute \(n\) coins to \(k\) locations.

Check.

Hint: Each coin is \(\bs{0}\) and each dividing line is \(\bs{1}\text{.}\) Note that the total length is \(15+2=17\text{.}\)
Hint: The total length is \(n+k-1\) because we only need \(k-1\) dividing lines.

15. Recap.

Do you know …

How to rephrase a question in terms of subsets and why that can be useful?
How to rephrase a question in terms of bit strings, and why that can be useful?

16. Explore.

In this problem we build on the ideas of Exercise 14.

How many nonnegative integer solutions are there to the equation \(x_1+x_2+x_3=15?\) Hint: how can we rephrase this question to be the same as the question in Exercise 14?
How many non-negative integer solutions are there to the equation \(x_1+x_2+x_3+x_4=20?\)
Make a conjecture about the number of non-negative integer solutions of the equation \(x_1+x_2+x_3+\ldots x_k=n\)

Check.

\(\displaystyle \binom{17}{2}\)
Hint: Let \(x_1\) be the number of coins in the first location, \(x_2\) be the number of coins in the second location, \(x_3\) be the number of coins in the third location, and \(x_4\) be the number of coins in the fourth location. Count the total number of coins and the number of dividing lines.
Hint: Count the total number of coins and the number of dividing lines.

Subsubsection Exercises for 2.4.D Algebra: Exponential Notation and Logarithms

17. Practice.

On this exercise, do not use technology. Be sure to show some work.

Evaluate \(2^4\text{,}\) \((-2)^4\text{,}\) and \(-2^4\text{.}\)
Evaluate \(10^{10}\text{.}\)
Evaluate \(4^1\) and \(4^0\text{.}\)

Check.

Hint: Use a calculator to check.
10,000,000,000
Hint: Use a calculator to check.

18. Practice.

On this exercise, do not use technology. Be sure to show some work.

Evaluate \(\fn{log}(10{,}000 )\text{,}\) \(\fn{log}(10)\text{,}\) and \(\fn{log}(1)\text{.}\)
Find a value \(n\) such that \(\fn{log}(n) = 3\text{.}\)
Evaluate \(\fn{lg}(64)\text{,}\) \(\fn{lg}(16)\text{,}\) \(\fn{lg}(2)\text{,}\) and \(\fn{lg}(1)\text{.}\)
Find a value of \(n\) such that \(\fn{lg}(n) = 3\text{.}\)

Check.

4, 1, 0
\(10^3\) (or 1,000 )
Hint: \(64=2^6\text{.}\)
Hint: The base is 2 and the logarithm tells you the exponent.

19. Understand.

Write each quantity as a single power.

\(\displaystyle k \times k\)
\(\displaystyle m^2m^7\)
\(\displaystyle 2 (2^9)\)
\(\displaystyle 10(10^{n-1})\)
\(\displaystyle 10(10^n)\)

Check.

\(\displaystyle k^2\)
Hint: How many \(m\)s are being multiplied?
Hint: How many twos are being multiplied?
\(\displaystyle 10^n\)
Hint: How many 10s are being multiplied?

20. Understand.

In this problem, all letters represent positive integers.

Factor \(n^3 + 3n^2\)
Factor \(k2^k -2^k\text{.}\)
Factor and simplify \(10^n-9(10^{n-1})\text{.}\) Hint: See Exercise 19 19.(d) and 19.(e).

Check.

Hint: Factor out \(n^2\text{.}\)
\(\displaystyle (k-1)2^k\)
Hint: Factor out \(10^{n-1}\text{,}\) using that \(10^n=10(10^{n-1})\text{.}\)

21. Recap.

Do you know …

What \(b^n\) means and how to pronounce it?
How to pronounce \(n^2\) and \(n^3\text{?}\)
How to evaluate \(5^0\text{,}\) \(5^1\text{,}\) and \(5^2\text{?}\)
Where exponents rank in the order of operations?
What \(\fn{log}\) and \(\fn{lg}\) mean and how to evaluate them?
How to rewrite a statement involving logs as a statement involving exponents?

22. Explore.

Play the online game 2048. Report here how long you played and how high a level you achieved. Try to get to at least 128.
List the powers of 2 from 1 to 2048 from memory (that is, not using any technology or computing any products).

23. Explore.

Write the exponential equation corresponding to \(\fn{lg}(128) = 7\text{.}\)
For numbers \(u\) and \(v\text{,}\) write \(a=\fn{lg}(u)\) and \(b=\fn{lg}(v)\text{.}\) Write the corresponding exponential equations.
Simplify \(2^{a+b}\) using Theorem 2.4.21 and 23.(b). Your answer should be in terms of \(u\) and \(v\text{.}\)
Use your answer to 23.(c) to evaluate \(\fn{lg}(uv)\text{.}\) Your answer should be in terms of \(a\) and \(b\text{.}\)
Use your answer to 23.(d) to write \(\fn{lg}(uv)\) in terms of \(\fn{lg}(u)\) and \(\fn{lg}(v)\text{.}\) Your answer is one of the rules known as a “law of logs”.

24. Explore.

Without calculating values, decide which is larger: \(10!\) or \(2^{10}\text{.}\) Hint: Use the definitions of factorials and powers to write each of \(10!\) and \(2^{10}\) as a product. Then use those products to answer the question.
Calculate \(10!\) and \(2^{10}\) using technology. Did you correctly determine which integer is larger?
Make a table for \(n = 0, 1, 2, \ldots, 10\) showing the values of \(2^n\) and the values of \(n!\text{.}\) Challenge yourself to reciting the powers of two and as many factorials as you can from memory, but then you are welcome to use computing technology. Hint: Use three rows labeled \(n\text{,}\) \(2^n\text{,}\) and \(n!\text{.}\)
Conjecture when \(n! \ge 2^n\text{.}\)

Check.

Hint: Compare

\begin{equation*} 10!=(10)(9)(8)(7)(6)(5)(4)(3)(2)(1) \end{equation*}

and

\begin{equation*} 2^{10} = (2)(2)(2)(2)(2)(2)(2)(2)(2)(2)\text{.} \end{equation*}

Note \(10>4 = (2)(2)\text{,}\) \(9>2\text{,}\) \(8?>2\text{,}\) …, \(2>2\text{.}\)
Yes
Hint: the last column of your table should have 10 in the first row, 1,024 in the second row, and 3,628,800 in the third row.
\(\displaystyle n \ge 4\)

Prev Top Next

\(10^4\)	=	\(\underbrace{10 \times 10 \times 10 \times 10}_{4 \text{ times } }\)
	=	\(100 \times 10 \times 10\)
	=	\(1{,}000 \times 10\)
	=	\(10{,}000\text{.}\)

\((-10)^4\)	=	\(\underbrace{(-10) \times (-10) \times (-10) \times (-10)}_{4 \text{ times } }\)
	=	\(100 \times (-10) \times (-10)\)
	=	-1,000 \(\times (-10)\)
	=	10,000.