\(1\) \(\underline{\text{Trees-A Branch of Discrete Mathematics}}\) Trees provide poets with inspiration as they sway through the breeze and their leaves, bursting with color, rustle in the wind. It is no wonder, then, that mathematicians coined the term “tree” in describing special classes of structured graphs. One author, Joe Malkevitch, makes it his goal to “convince you (readers) that mathematical trees are no less lovely than their biological counterparts.”

In discrete mathematics, and more specifically graph theory, a tree is a connected graph with no cycles. When the graph is not connected, naturally we call this a forest. In addition, a vertex of degree \(1\) is called a leaf. These kind of mathematical structures were first studied by mathematician Arthur Cayley. In \(1889\) Cayley published a formula stating that for \(n \geq 1\), the number of trees with \(n\) vertices is \(n^{n-2}\).

A few other properties of trees include the following:

Given two vertices, \(x\) and \(y\), there is a unique path from \(x\) to \(y\)

If we remove any edge of a tree, the graph is no longer connected

If a tree has \(n\) vertices, then it has \(n-1\) edges

The concept of mathematical trees has applications in various fields including science, the enumeration of saturated hydrocarbons, the study of electrical circuits, and many more (Harary, 1994, p. 4).

\(1\) \(\underline{\text{An Introduction to Graph Theory}}\) The concepts of graph theory go all the way back to the eighteenth century when, in 1736, Euler published what is believed to be the first paper on the very subject. It contained a famous problem known as the Königsberg Bridges Problem. This is a puzzle which considers the question of whether or not a person, starting from their home, could pass over each of the seven bridges that crossed the Pregal River exactly once before returning home. Euler was able to reconstruct the problem in such a way that allowed for him to lay the foundation of graph theory. To solve the puzzle, Euler replaced the land masses with vertices and let edges represent the bridges. The mathematical structure that became of his work is now called a graph.

\(1\) \(\underline{\text{Parity}}\)

Parity, in terms of mathematics, describes the classification of an integer as either even or odd. An even number is defined as an integer that is divisible by \(2\) while an odd number is one that is not. A more formal definition states that an even number is an integer \(n\) of the form \(n=2k\) where \(k\) is an integer. On the other hand, an odd number is an integer of the form \(n=2k+1\). In set notation we see:

\[\text{Even} \hspace{0.5mm} = \hspace{0.5mm} {2k : k \in \mathbb{Z}}\]

\[\text{Odd} \hspace{0.5mm} = \hspace{0.5mm} {2k+1 : k \in \mathbb{Z}}\]

In number theory, the idea of parity allows us to solve some mathematical problems simply by making note of odd and even numbers. In the same way, the impossibility of some mathematical constructions can be proven. For example, consider the following question:

\(1\) \(\underline{\text{Public Key Cryptography}}\)

Public key cryptography (from the Greek roots “crypto” and “graphon,” meaning “hidden writing”) is perhaps the most discreet application of discrete mathematics (Benjamin, 2009). The most famous method for public key cryptography is called the RSA method. This method was discovered in 1977 by three mathematicians Rivest, Shamier, and Adleman.

To carry out this method, one would begin by defining \(n\) to be the product of two primes \(p\) and \(q\). We must also choose a private key, as it is called, and we will name this \(d\). Then, we compute \(\phi({n})\) which is equivalent to \((p-1)(q-1)\). As long as \(d\) is relatively prime to \(\phi({n})\), we can set up the equation \(de-\phi({n})f=1\) and solve for \(e\) and \(f\) using the Euclidean Algorithm. The value for \(e\) is made public. Therefore, the information that is published is \(n\) and \(e\) while all other values are kept private.

The message that is sent is \(M^e \equiv C \pmod{n}\) where the original message is denoted \(M\) and the encrypted message is \(C\). To decrypt our message, one would compute \(C^d \equiv M \pmod{n}\).

\(1\) \(\underline{\text{Card Shuffling}}\) In discrete mathematics, a riffle shuffle is a shuffling of cards in which the top half is placed in one hand and the other half lies in the opposite hand. The cards are then alternatively interlaced with one another. There are two different types of riffle shuffles that will be the topic of discussion: the out-shuffle and the in-shuffle. An out-shuffle keeps the top card on top and the bottom card on bottom. When the top card is, instead, placed in the second position we have an in-shuffle.

Consider a typical \(52\) card deck. If we name and order the cards \(0,1,2,3,4...\), then after an out-shuffle we receive the order \(0,26,1,27,2,28...\). After an in-shuffle, the cards appear as \(26,0,27,1,28,2...\). Note that the first card is in the \(0\) position. To return to the original order, we must make \(8\) out-shuffles. Interestingly enough, however, it takes \(52\) in-shuffles.

\(1\) \(\underline{\text{Binary Notation}}\)

We define binary numbers as the powers of two that lay the foundation for the additive building blocks of positive integers. Note that the word binary comes from “Bi” meaning two. In this system, integers are expressed in terms of only \(0\)s and \(1\)s. The values that represent each integer are calculated by finding the sum of the powers of two that make up the given number. We pull out the amount of times that each power of two occurs. For example, the decimal number ten is written as “\(1010\)” because it is \(\underline{1}\) \(\cdot\) \(2^3+ \underline{0} \) \(\cdot\) \(2^2 + \underline{1} \cdot 2^1 + \underline{0} \cdot 2^0 \). Notice that this starts with the largest power of two. We read “\(1010\)” as “one-zero-one-zero” as opposed to one thousand and ten. The binary representation of the first few natural numbers are shown in the table below.

\(1\) \(\underline{\text{Recurrence Relations}}\) Throughout one’s education and as one progresses through grade levels, a common math problem that students are faced with are puzzles in which they have to determine what number comes next in a sequence. For example, a teacher may ask a student to fill in the missing number given the following:

\[1,4,5,9,14 \underline{\hspace{1cm}}, ...\]

A student may then notice a pattern of adding the two terms before to get to the next. This idea, at its very core, is an illustration of a recurrence relation.

Defined mathematically, a recurrence relation is an equation in which the next term in the sequence is dependent upon or acts as a function of the previous term(s).

Using the case above, and applying it to recurrence relations, we would write the relation as: \(a_n=a_{n-1}+a_{n-2}\) where the initial conditions are \(a_0=1\) and \(a_1=4\).

Some of the more well known examples from the study of discrete mathematics include the Fibonacci sequence as well as binomial coefficients. While the Fibonacci sequence defined by \(F_n=F_{n-1}+F_{n-2}\) where \(F_1=F_2=1\) is fairly easy to recognize as a recurrence relation, binomial coefficients are not primarily described in this way. However, we see from the following illustration that they can, indeed, be accepted as following a recurrence relation. \[{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\]

A game that has been derived from the idea of recurrence relations that some may find entertaining is called the Tower of Hanoi. This was invented by Edouard Lucas in 1883. If this name sounds familiar, it is because Edouard Lucas is more famously known for his recurrence relation called the Lucas Numbers, which follow the same relation as the Fibonacci sequence. In this game, there are a certain number of disks and three “towers.” The objective is to move all the disks stacked on one tower over to another without placing larger disks on smaller ones. An illustration can be seen as such:

\(1\) \(\underline{\text{Fibonacci Sequence}}\) According to some accounts, Fibonacci is regarded as one of the most famous names in mathematics. It was Fibonacci, also known by the name Leonardo Pisano, that helped popularize our modern number system in the Latin-speaking world (Knott, 2013). However, he is more widely recognized for what we now call the Fibonacci Sequence. It was when he was contemplating the reproduction of rabbits, and trying to calculate how many pairs of rabbits there would be in one year, that Fibonacci came across the formula, which will become familiar: \(x_{n+1}=x_n+x_{n-1}\).

This recurrence relation was used to define the Fibonacci Sequence as such: \(F_n=F_{n-1}+F_{n-2}\) where \(F_1=F_2=1\). Calculating the first few terms we see the numbers \(1,1,2,3,5,8,13,21...\). These numbers are called the Fibonacci numbers.

These numbers appear in a plethora of areas from nature, art, geometry, etc. A few examples of where these numbers occur include the following:

Honeybee colonies

Spirals and shells

Plants and flowers

\(1\) \(\underline{\text{Pascal's Triangle}}\) In discrete mathematics, Pascal’s triangle is the arrangement of binomial coefficients in such a way that a triangle is formed. Although such a pattern was studied centuries before his time, we refer to Pascal’s triangle in relation to Blaise Pascal, a French mathematician. The triangle was originally developed by the ancient Chinese, but Pascal was the first person to discover the importance of all of the patterns that occur within it. His work allegedly stemmed from the popularity of gambling. After considering a question asked to him about gambling with dice, Pascal’s \(\textit{Arithmetical Triangle}\) resulted.

The triangle is created by starting at the top, row \(0\), with the number \(1\). Each row afterwards begins and ends with \(1\) and the pattern follows that as you move through the row, you add the number above and to the left with the number above and to the right for any given position. A portion of Pascal’s triangle is shown below.

\(1\) \(\underline{\text{Binomial Coefficient}}\) In mathematics, the binomial coefficient is written as \({n \choose k}\) and can be pronounced as “\(n\) choose \(k\).” Alternatively, binomial coefficients are also sometimes given the notation \(C(n,k)\). In this case, the \(C\) stands for the word “choices” or “combination” (Benjamin, 2009, p. 8). This is because there are \({n \choose k}\) ways of choosing \(k\) elements from a set containing a number of \(n\) elements. For example, we can consider the set \(A=\{1,2,3,4\}\). If we wish to know how many subsets of \(2\) can be created using this set, we are essentially asking how many ways there are of choosing \(2\) elements from a set with \(4\) total elements. Therefore, we can identify that \(k=2\) and \(n=4\). Hence, we have \({4 \choose 2}\). To calculate such a problem, we typically would want to write out by hand all the possible combinations. Doing so, one would find that there are six pairs of size two subsets, namely \(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2,3\}\), \(\{2,4\}\), and \(\{3,4\}\). However, it becomes clear to see that when we are dealing with large sets of values, this work can become tedious. Therefore, it is convenient to utilize the following formula:

\[{n \choose k} = \frac{n!}{(n-k)! \cdot k!}\]

This blog is powered by Authorea

Start writing now