Section 2.1 Organized Listing

We begin with a puzzle.

Make sure that you have tried Activity 2.1.A before reading on.

In Activity 2.1.A and Example 2.1.3, we saw our first example of a recursive solution where we use tilings of smaller boards to tile a larger board. Specifically, we can tile a \(1 \times n\) board using the tilings for the next two smaller boards: a \(1 \times (n-1)\) board and a \(1 \times (n-2)\) board. We study recursions in Chapter 8 Recursion and Induction. We can use this recursion to count the number of tilings on a \(1 \times n\) board.

Throughout this course, we use mathematical structures. One structure is a set, which is understood to be an unordered collection of elements. For example, the set \(\{1,4,5\}\) has three elements: 1, 4, and 5. The set \(\{4,1,5\}\) is the same as the set \(\{1,4,5\}\) because \(\{4,1,5\}\) has the same three elements: 1, 4, and 5. That is, the order in which we list the elements in a set does not matter. There is no need to repeat elements within a set because it does not change the set. For example, the set \(\{2,7,2\}\) is the same as the set \(\{2,7\}\) because each set has two elements: 2 and 7. Sets are very important in mathematics. In fact, we might say that

Since discrete mathematics comes from all areas of mathematics, it should not be surprising that this textbook uses a large mathematical vocabulary. Some words in that vocabulary are not defined. For example, the words “set” or “element” are not defined in the previous paragraph, although we hope that their meaning is clear from the narrative. It turns out that any vocabulary must be built on a set of undefined words because you have to start somewhere. We try to keep the list of undefined terms as short as possible.

When we can, we give a formal mathematical definition of a new word that states what the word means in mathematics. We sometimes add a quick example or note, but those additions are not officially part of the definition. Definitions in mathematics also serve another purpose. There might be several different, but equivalent, ways to explain the meaning of a word. In such situations, a definition establishes an agreement on which of those different explanations is the official mathematical definition of the word.

Here are a few examples of definitions. First, there are a few ways to refer to types of numbers.

The integers \(0,1,2,3,4,5,6,7,8,9\) have a special name.

We also have a name for the result of adding, subtracting, or multiplying two integers.

Here is an example that uses these definitions.

Try working with sets.

The short version of the answer is that we try to be organized, and if possible, we try to write the list in a standard order. For example, in Activity 2.1.A you might have organized your list based on whether the tiling started with a square or a domino, or you might have organized your list based on the number of dominoes. In Activity 2.1.B you might have organized your work by considering the smallest or largest element in your set. In general, we can create an organized list by breaking the problem into special cases.

Another example of a mathematical structure is a string. Your passwords are probably all strings. We represented a tiling of a \(1 \times n\) board with squares and dominoes as a string of dots (\(\bullet\)) and dashes (\(\boldsymbol{-}\)) in Activity 2.1.A. Here is the definition of string and more vocabulary about strings.

In our next example, we highlight two organizational strategies for creating lists: considering cases or drawing a possibility tree

²

Possibility trees get their name from natural trees because they have branches.

.

Notice in Example 2.1.14 that we considered the letters in alphabetical order, the order of the English alphabet: \(\str{a}\text{,}\) \(\str{b}\text{,}\) \(\str{c}\text{,}\) \(\str{d}\text{,}\) \(\str{e}\text{,}\) \(\str{f}\text{,}\) \(\str{g}\text{,}\) \(\str{h}\text{,}\) \(\str{i}\text{,}\) \(\str{j}\text{,}\) \(\str{k}\text{,}\) \(\str{l}\text{,}\) \(\str{m}\text{,}\) \(\str{n}\text{,}\) \(\str{o}\text{,}\) \(\str{p}\text{,}\) \(\str{q}\text{,}\) \(\str{r}\text{,}\) \(\str{s}\text{,}\) \(\str{t}\text{,}\) \(\str{u}\text{,}\) \(\str{v}\text{,}\) \(\str{w}\text{,}\) \(\str{x}\text{,}\) \(\str{y}\text{,}\) \(\str{z}\)

\(\str{A}\text{,}\) \(\str{B}\text{,}\) \(\str{C}\text{,}\) \(\str{D}\text{,}\) \(\str{E}\text{,}\) \(\str{F}\text{,}\) \(\str{G}\text{,}\) \(\str{H}\text{,}\) \(\str{I}\text{,}\) \(\str{J}\text{,}\) \(\str{K}\text{,}\) \(\str{L}\text{,}\) \(\str{M}\text{,}\) \(\str{N}\text{,}\) \(\str{O}\text{,}\) \(\str{P}\text{,}\) \(\str{Q}\text{,}\) \(\str{R}\text{,}\) \(\str{S}\text{,}\) \(\str{T}\text{,}\) \(\str{U}\text{,}\) \(\str{V}\text{,}\) \(\str{W}\text{,}\) \(\str{X}\text{,}\) \(\str{Y}\text{,}\) \(\str{Z}\) For strings beginning with \(\str{a}\text{,}\) we first list the string ending in \(\str{2}\) and then the string ending in \(\str{6}\text{.}\) That is, we considered the digits in numerical order, from smallest to largest.

Practice using possibility trees to create lists.

In the possibility trees that we have drawn so far, each branch is of the same length. Let’s look at an example where the branches are different lengths.

Often, the numbers we consider in this textbook are integers. For example, we might make a conjecture that involves an unknown integer. Historically, integers were commonly named using the letters \(i,j,k,l,m\text{,}\) or \(n\) because some computer programming languages, such as Fortran, used to reserve these letters for integer quantities (perhaps because the word “integer” begins with \(i\) and then \(n\)). In this textbook, we use a variety of letters for integers, although we tend to save the letters \(x\text{,}\) \(y\text{,}\) and \(z\) for real-valued (decimal) quantities.

When you studied algebra, you probably worked a lot with quantities named \(x\text{,}\) occasionally with quantities named \(y\text{,}\) \(z\text{,}\) or \(t\text{,}\) and rarely with quantities named \(n\text{,}\) \(m\text{,}\) \(k\text{,}\) or other common letters for integers. The rules of algebra remain the same for whatever letters we use, but it can take some practice to be comfortable working with a variety of letters. In this section, we discuss integer arithmetic. To start with, it is useful to name various arithmetic properties of the integers.

Let’s practice working with the vocabulary factor and term.

We can use the distributive propensity to combine like terms, which means terms having a common factor.

Now it is your turn to practice some integer algebra.