New Discrete Math Edition released

 I am pleased to announce the latest edition of Discrete Math, An Inquiry Based Approach. This latest edition includes additional guided practice, clarifies tasks, and corrects grammatical errors. The structure and contents remains essentially the same as before. Below is the table of contents. If you are interested in using the book or would like to have the book approved for use in your district or state, please contact me.

Table of Contents 0. Introduction ..................................................................................… page 7 1. 

Counting and Discrete Probability …………………………………………………….… page 10 

1.1. Initial Investigations …………………………………..…..………………………… page 10 

1.2. Figurate Numbers ……………………………….………..……………….………… page 11

1.3. Finite Differences ……………………………….………..………………..…………page 12

1.4. Polygonal Numbers ………..……………………………..………………..…………page 14

1.5. Combinations and Permutations ……………………...………………...........………page 15 

1.6. The Pigeonhole Principle ……………………………………..……….....…………. page 18 

1.7. Advanced Counting ……………………………………..……………..…………..…page 19 

1.8. Discrete Probability ……………………………………..………..…...…………..… page 20 

1.9. Conditional Probability …………………………..……..………....…………………page 22 

1.10. Probability Practice and Mastery Quiz ………………………….........…………….page 25 

2. Graph Theory ……………………………………..…………………...……………… page 28 

2.1. Introduction to Graphs ………………………………..………………....…..……… page 28 

2.2. Graph Theorems ………...………………………………..………………………… page 33 

2.3. Mail Route Practice ……………..……………..………..……..…………………… page 37 

2.4. Hamilton Paths and Circuits …………..……………..……….......………………… page 38 

2.5. Planar Graphs …………….………………………………..……..………………… page 41 

2.6. Complete and Complementary Graphs …………………………............………….. page 45 

2.7. Graph Coloring …………………………………………..………………………… page 49 

2.8. Edge Coloring …..……………………………………......………………………… page 54 

3. Elementary Number Theory ………..……………………...………………………… page 57 

3.1. Prime Numbers …………………………..………………..……………..………… page 57 

3.2. Prime Number Distribution ………...………………..………………......………… page 60 

3.3. Prime Number Sequences ……………...……………..……………....…………… page 64 

3.4. Relative Primes ………..………………………………...………………………… page 66 

3.5. Prime Sums ………………………………………….…..………………………… page 69 

3.6. Prime Factorization ……….……………………………..………………………… page 70 

3.7. Perfect Numbers ………………………...……………….………………………… page 73 

3.8. Mersenne Primes and Prime Formulas ……...…..………….............……………… page 76 

3.9. Euclidean Algorithm ………………………………..…..……..…………………… page 78 

4. Cryptography ……………………………………..………....……………………..… page 81 

4.1. Caesar Ciphers ……………………...……………………....……………………… page 81 

4.2. Cipher Functions …………..……………………………..………………………… page 83 

4.3. Affine Ciphers …………………....………………………....……………………… page 87 

4.4. Chinese Remainder Theorem ……….………………..……......…………………… page 88 

4.5. Congruences ……………………………….……………...………………………... page 90 

4.6. Solving Congruences ……………………………………..………………………... page 94 

4.7. Congruences and Divisibility ………………..………..…….....………...………… page 97 

4.8. Modular Arithmetic …………….………………………..………………………… page 100 

4.9. Primality Tests ……………………………………...……..……………..………… page 101 

4.10. Cryptography Revisited ………………………………...………………………… page 103 

4.11. Diffie-Hellman Exchange ……….……………………..……………….………… page 104 

4.12. Cracking the Diffie-Hellman Exchange ……………...…………………............... page 108 

4.13. RSA Protocol ……………………………...……………………………………… page 110

 4.14. RSA Practice ………………………….……………………..………………....… page 112 

5. Set Theory and Boolean Algebra ……...………………………..…………….……… page 114

 5.1. Understanding Sets ……………………..………………..……………………...… page 114 

5.2. Set Operations ……………………………….……………..………………….…… page 117 

5.3. Venn Diagrams ……………………………...……………..………………..……… page 121 

5.4. DeMorgan’s Laws …………….……………………………………..……...……… page 122 

5.5. Cartesian Products ……………………………………….…….…………...……… page 123 

5.6. Boolean Algebra …………………………..………………..……..…………..…… page 124 

5.7. Boolean Functions ……………….………………………..………....……..……… page 126 

5.8. Boolean Identities ……………..…………………………..……………………..… page 129 

5.9. Truth Tables ……………………………………..…………..…….……..………… page 131 

5.10. Logic Gates ……………………………………………….…..………………..… page 134 

6. Logic and Proof …………………………………………………….....………..…… page 139 

6.1. Statements and Negation ………………..……………..…………......…………… page 139 

6.2. The Language of Logic …………………………….……..…………….....……… page 141 

6.3. Showing Truth …………………………….………………..…………..………… page 143 

6.4. Methods of Proof ……………………...…………………..……………………… page 146 

7. Citations …………………………………………………….....………...………….. page 152

Copyright 2016-2021 Michael G. Pugliese

Using Ellipses to Estimate Correlation

I recently had the privilege to participate in my fifth AP Statistics reading. One activity that I especially look forward to during the reading is the Best Practices Night. This year was even more special as I was one of the presenters at this year's Best Practices Night. Many of my colleagues encouraged me to submit this talk during informal discussions. Because of the reception the talk received, I decided to share the talk so that others may benefit from it as well.

What students need to understand going into this are the following:

1. Correlation measures the strength of a linear association,
2. A scatter plot that follows a straight line has a correlation of ±1, and
3. A scatter plot with no linear association has a correlation of zero.

Take two scatter plots, one of zero correlation and one of positive one correlation, and draw ellipses around them (see fig. 1).

fig. 1

Now, while ellipses have a major and minor axis, my students don't remember much about ellipses by the time they take AP Statistics, so I simply refer to the length and width of the ellipse.

Ask your students how can the length and width be used to help estimate the value of r? Fairly shortly, students will say you can get the correlation of zero by simply subtracting L - W. That works great, but it doesn't give use the correlation of 1. With a little more thought, students will realize the dividing this quantity by L will yield the correlation of 1.

So, this is what we'll use, (L - W) / L. Correlation is unitless, and when this division is made, units will cancel out. This means it doesn't matter what is used to measure the length and width of the ellipse. Students can use markings on a paper, a ruler, their pencil or pen, or even their finger. The slope of the ellipse's length will determine whether the correlation is positive or negative.

fig. 2

Once students understand how this works, you can start examining the impact outliers have on correlation or what impact adding or removing a point from the scatter plot will have on correlation.

fig. 3

In fig. 3, the new point causes the ellipse to become longer while the width remains the same. This means that the numerator in our estimation equation becomes larger, so this point causes correlation to increase.

fig. 4

In fig. 4, the new point causes the ellipse to become wider while the length stays about the same. In this case, the numerator becomes smaller, which means that the correlation is weaker with this new point in the data set.

fig. 5

In fig. 5, the new point changes both the length and width. More importantly, the new point changes the slope of the ellipse length from positive to negative. In this situation, the outlier is causing the sign of the correlation to change.

You can even use ellipses to help students understand why a linear association may not be the best way to describe the relationship in the scatter plot.

fig. 6

Students, at this point, will naturally enclose the scatter plot with something that turns out to not be an ellipse. They will even start to measure the length and width of the enclosure. You have to remind them that correlation only measures linear associations and that they need to draw an ellipse.

What they will notice is that the ellipse does not provide uniform coverage of the scatter plot and their amoeba enclosure does a better job of capturing the scatter plot. This gap of coverage in the ellipse indicates that a linear association will not be the best way to describe the relationship for this data set.

By using ellipses to estimate correlation, students are able to:

• visualize the strength of a linear association,
• understand the impact of outliers on correlation,
• understand the impact of adding and removing points from a scatter plot on correlation, and
• recognize when non-linear associations are stronger than linear associations

I encourage you to have your students use ellipses to estimate correlation.

p.s. For those of you interested, there is an excellent paper on correlation entitled Thirteen Ways to Look at the Correlation Coefficient (Rodgers and Nicewander, 1988). If you look at item 10, you can see that the (L - W) / L is a less precise estimate of the formula given in the article. I will confess, I found the article after having used this method for many years. I didn't want to submit my presentation idea before having a more formal confirmation of its validity.

A new look at Gaussian summation

Yesterday in my discrete math class, I had the opportunity to build to a summation formula in a slightly different manner than in the past. The class was working on finding the values of triangular numbers. Many students saw the recursive nature of the situation and realized that by simply adding consecutive integers they could calculate the value of a triangular number. They wanted to have a more efficient way to calculate but were not coming up with any ideas.

One student did come up with a way to calculate the result and had justification through manipulation of dot arrangements. The issue was how to get the rest of the class to a point where presenting this student's ideas would make sense.

I had an idea and decided to see where it would lead. I began by writing 1 + 2 + 3 + 4 + 5 + 6 + 7 on the board and asking students how they would add these in their head. Students are naturally inclined to form 10's as these are nice anchor values to use. Many students said they would add values 3 + 7 and 4 + 6 to get 10’s and then add the remaining values.

I then added an 8 into the mix and wrote out 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8. Students again made pairs to form 10’s. The issue is that the process changes in that different values are now being gathered up at the end. I asked the class if there was a consistent process that they could use when adding the values. A consistent process would enable us to find values of triangular numbers without having to think too much about how to do it.

At this point, several students noticed that adding 1 + 6 = 7, 2 + 5 = 7 and 3 + 4 = 7. The students said you could then multiply 3 x 7 and add the final 7 to get an answer. I wondered if this would work consistently and asked students to try it with 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9. Students did and said it worked. I pushed students to consider how this process worked. They realized that you subtract one from the last value and then multiply the last value by half the second to the last value. They basically thought of the process as (8/2) 9 + 9. The class said this was the same process when adding the integers 1-7.

I asked students to use this process to calculate T75. They readily did this without issue. I then wondered if the formula worked if there were an even number of values instead of an odd number of values. Students tried this and found it worked .

Now they had this part down, it was time to push them to finding a formula. I told the class I wanted to write out the series without having to specify what the final value actually is. I wrote out the sum like this: 1 + 2 + 3 + 4 + 5 + 6 + 7 + … + (n - 1) + n, where n is the final value. I asked students to use the process they were just using to calculate the value of Tn. Students were readily able to write out that Tn = n(n-1)/2 + n.

Students saw that there is no magic about where the formula comes from. Using their logic and processes, the formula was simply an extension of their thinking. It also demonstrates how the formula and math help make life easier by providing them a more efficient and effective way to calculate values of triangular numbers.

Students were now in a position to see a justification tied to the triangular number representation through dots. Besides providing a different way to approach developing a formula, the presentation of an alternative way to derive a formula provided an in to discuss the algebraic equivalence of formulas.

I was glad that I pursued this idea as it helped students build confidence and comfort with the math involved in our work with triangular numbers.

Starting up discrete math

The first few days of my discrete math class are rolling out as expected. Besides covering operational issues, the opening of the class pushes students to break their perception of what a math class looks like and how it operates.

I have been pleased with how responsive the class has been. When pushed to think of problems in new and different ways or to look for patterns and connections to physical representations, the class has really pushed themselves.

After working through some Pascal triangle investigations, we started working with figurate numbers. I opened with square numbers, as usual, to work on thinking of familiar entities differently. When we transitioned to triangular numbers, the class easily dove into working with the representations and patterns. The exciting part was that students saw how to calculate triangular numbers but wanted to have a more efficient way to perform the calculation. I'll be interested to see what processes and formulas they come up with.

For those interested, here is the table of contents from my discrete math ebook. You can get a sense of the material that is covered and how the course progresses through the topics.

Discrete Math

An Inquiry Based Approach

by

Mike Pugliese

August 2016 - August 2017

Table of Contents

1. Counting and Discrete Probability …………………………………………………….… page   3
1. Initial Investigations ……………………………………..………………………… page  3
2. Figurate Numbers ……………………………….………..………………………… page  4
3. Finite Differences  ……………………………….………..………………………… page  7
4. Polygonal Numbers ………..……………………………..………………………… page  9
5. Combinations and Permutations  ……………………...……………………… page 10
6. The Pigeonhole Principle  ……………………………………..…………………. page 12
7. Advanced Counting ……………………………………..………………………..… page 13
8. Discrete Probability ……………………………………..………..……………..… page 15
9. Conditional Probability …………………………..……..………………………… page 17
10. Probability Practice and Mastery Quiz ………………………………………. page 20
2. Graph Theory  ……………………………………..…………………………………….……… page 21
1. Introduction to Graphs ………………………………..…………………..……… page 21
2. Graph Theorems ………...………………………………..………………………… page 27
3. Mail Route Practice ……………..……………..………..………………………… page 31
4. Hamilton Paths and Circuits …………..……………..………………………… page 32
5. Planar Graphs …………….………………………………..………………………… page 35
6. Complete and Complementary Graphs …………………………………….. page 39
7. Graph Coloring ………………………………………..…..………………………… page 43
3. Elementary Number Theory  ………..…………………………..………………………… page 50
1. Prime Numbers …………………………..………………..………………………… page 50
2. Prime Number Distribution ………...………………..………………………… page 53
3. Prime Number Sequences ……………...……………..………………………… page 57
4. Relative Primes ………..…………………………………..………………………… page 59
5. Prime Sums …………………………………………..……..………………………… page 62
6. Prime Factorization ……….……………………………..………………………… page 63
7. Perfect Numbers ………………………...………………..………………………… page 66
8. Mersenne Primes and Prime Formulas ……...…..………………………… page 69
9. Euclidean Algorithm ………………………………..…..………………………… page 71
4. Cryptography ……………………………………..…………………………………..………… page 74
1. Caesar Ciphers ……………………...……………………..………………………… page 74
2. Cipher Functions …………..……………………………..………………………… page 76
3. Affine Ciphers …………………....………………………..………………………… page 80
4. Chinese Remainder Theorem ……….………………..………………………… page 81
5. Congruences ……………………………….………………..………………………… page 83
6. Solving Congruences ……………………………………..………………………… page 88
7. Congruences and Divisibility ………………..………..………………………… page 90
8. Modular Arithmetic …………….………………………..………………………… page 93
9. Primality Tests ……………………………………...……..………………………… page 95
10. Cryptography Revisited ………………………………...………………………… page 97
11. Diffie-Hellman Exchange ……….……………………..………………………… page 98
12. Cracking the Diffie-Hellman Exchange ……………...…………………...… page 101
13. RSA Protocol ……………………………...………………..………………………… page 103
14. RSA Practice ………………………….……………………..………………………… page 105
5. Set Theory and Boolean Algebra ……...………………………..………………………… page 108
1. Understanding Sets ……………………..………………..………………………… page 108
2. Set Operations ……………………………….……………..………………………… page 111
3. Venn Diagrams ……………………………...……………..………………………… page 115
4. DeMorgan’s Laws and Cartesian Products …………….…………………… page 116
5. Boolean Algebra …………………………..………………..…………………..…… page 118
6. Boolean Functions ……………….………………………..………………..……… page 120
7. Boolean Identities ……………..…………………………..………………………… page 122
8. Truth Tables ……………………………………..…………..……………..………… page 124
9. Logic Gates ……………………………………………….…..……………………..… page 128
6. Logic and Proof …………………………………………………….....…………………..…… page 132
1. Statements and Negation ………………..……………..………………………… page 132
2. The Language of Logic …………………………….……..………………..……… page 134
3. Showing Truth …………………………….………………..………………………… page 136
4. Methods of Proof ……………………...…………………..………………………… page 139