Skip to main content
\( \def\negchoose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\mchoose}[2]{\left(\!\binom{#1}{#2}\!\right)} \newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\left[{#1\atop#2}\right]_q} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\alert}{\fbox} \def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #1} \newcommand{\s}[1]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,1.5)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,1.5)} \def\E{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\circleC{(0,-1) circle (1)} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\twosetbox{(-2,-1.4) rectangle (2,1.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; } \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

PrefacePreface

This book was written specifically to be used as the textbook for the Master's level Discrete Mathematics course at the University of Northern Colorado. This course is part of a MA in Mathematics with a Teaching Emphasis. Most of the students in the course are current secondary math teachers. This intended audience has influenced the style and content of the book in a few important ways.

First, we acknowledge that not everyone reading this book will be immediately familiar with the content of a standard undergraduate discrete mathematics course. Little is assumed about the reader's previous work in the subject, beyond a general understanding of how abstract mathematics proceeds, as well as some basic ability with mathematical proof. Even here, the first chapter on Graph Theory serves as an excuse to review basic proof techniques. For the reader completely unfamiliar with these and the basic objects of mathematical study (sets and functions), background material is included in an Appendix.

Topics have been selected to illustrate larger concepts of interest to secondary teachers. We have put an emphasis on understanding simple concepts deeply and in more than one way. Although some topics intersect secondary curriculum, most of the questions here are at a higher level. Still, the problem solving strategies and big ideas illustrated by our questions have applications to secondary mathematics. This emphasis is quite different than other mid level discrete and combinatorics textbooks, since we are not preparing our readers to begin a career in research mathematics.

While this course is not a course on teaching mathematics, we have tried to model good pedagogical practice. As you will see, almost all of the textbook consists of “Activities” that guide students to discover mathematics for themselves. This will require quite a bit more work both from students and instructors, but we strongly believe that the best way to learn mathematics is by doing mathematics. Most of all, discovering mathematics is fun.

How to use this book

This book is mostly about solving problems, and using those problems and their solutions to develop mathematics and mathematical understanding. The main three chapters consist of more than 300 activities which the reader is asked to complete. That is how you should use the book. As you read, when you come to an activity, really take some time to try to solve it. Many of the activities are broken down into tasks to help guide you to a solution. If you get stuck, check for a hint. In the pdf, problems with hints are marked with a small “[hint]” link that will take you to the hint in the back of the book; clicking on the number of the hint will return you to the activity. The online version has expandable hint links under any activities for which they are provided.

Solutions are not provided explicitly, but often the important content of an activity will be explained further into the book. We have made every effort to make the problems “self checking” so that you do not run the risk of learning something false.

For the most part, if you are unable to complete an activity, assuming you have put a reasonable effort in already, it would be safe to move on. If the activity is meant to guide you to a fundamental concept, that will become apparent, and later activities and exposition will help you uncover that concept. Other activities are meant to provide interesting examples of these big ideas, but missing any one of them will not impede your progress on other activities.