This text aims to give an introduction to select topics in discrete mathematics at a level appropriate for first or second year undergraduate math majors, especially those who intend to teach middle and high school mathematics. The book began as a set of notes for the Discrete Mathematics course at the University of Northern Colorado. This course serves both as a survey of the topics in discrete math and as the “bridge” course for math majors, as UNC does not offer a separate “introduction to proofs” course. Most students who take the course plan to teach, although there are a handful of students who will go on to graduate school or study applied math or computer science. For these students the current text hopefully is still of interest, but the intent is not to provide a solid mathematical foundation for computer science, unlike the majority of textbooks on the subject.
Another difference between this text and most other discrete math books is that this book is intended to be used in a class taught using problem oriented or inquiry based methods. When I teach the class, I will assign sections for reading after first introducing them in class by using a mix of group work and class discussion on a few interesting problems. The text is meant to consolidate what we discover in class and serve as a reference for students as they master the concepts and techniques covered in the unit. None-the-less, every attempt has been made to make the text sufficient for self study as well, in a way that hopefully mimics an inquiry based classroom.
The topics covered in this text were chosen to match the needs of the students I teach at UNC. The main areas of study are combinatorics, sequences, logic and proofs, and graph theory, in that order. Induction is covered at the end of the chapter on sequences. Most discrete books put logic first as a preliminary, which certainly has its advantages. However, I wanted to discuss logic and proofs together, and found that doing both of these before anything else was overwhelming for my students given that they didn't yet have context of other problems in the subject. Also, after spending a couple weeks on proofs, we would hardly use that at all when covering combinatorics, so much of the progress we made was quickly lost. Instead, there is a short introduction section on mathematical statements, which should provide enough common language to discuss the logical content of combinatorics and sequences.
Depending on the speed of the class, it might be possible to include additional material. In past semesters I have included generating functions (after sequences) and some basic number theory (either after the logic and proofs chapter or at the very end of the course). These additional topics are covered in the last chapter.
While I (currently) believe this selection and order of topics is optimal, you should feel free to skip around to what interests you. There are occasionally examples and exercises that rely on earlier material, but I have tried to keep these to a minimum and usually can either be skipped or understood without too much additional study. If you are an instructor, feel free to edit the LaTeX or PreTeXt source to fit your needs.
Improvements to the 3rd Edition.
In addition to lots of minor corrections, both to typographical and mathematical errors, this third edition includes a few major improvements, including:
- More than 100 new exercises, bringing the total to 473. The selection of which exercises have solutions has also been improved, which should make the text more useful for instructors who want to assign homework from the book.
- A new section in on trees in the graph theory chapter.
- Substantial improvement to the exposition in chapter 0, especially the section on functions.
- The interactive online version of the book has added interactivity. Currently, many of the exercises are displayed as WeBWorK problems, allowing readers to enter answers to verify they are correct.
The previous editions (2nd edition, released in August 2016, and the Fall 2015 edition) will still be available for instructors who wish to use those versions due to familiarity.
My hope is to continue improving the book, releasing a new edition each spring in time for fall adoptions. These new editions will incorporate additions and corrections suggested by instructors and students who use the text the previous semesters. Thus I encourage you to send along any suggestions and comments as you have them.
University of Northern Colorado, 2019