oscarlevin/discrete-book

An open textbook for Discrete Mathematics, as taught at the University of Northern Colorado

Discrete Mathematics: An Open Introduction

An open textbook for Discrete Mathematics, as taught at the University of Northern Colorado. More information about the project is available on the book's main website.

The main branch now has the source code for the 3rd edition. Work on the 4th edition is done on the edition branch.

Compilation instructions

This text is written in PreTeXt, so the primary source files can be found in the source directory. These can be compiled into HTML or PDF files (as well as some other formats) using the following directions.

Preliminaries

The easiest way to build output formats from the source is to use the PreTeXt-CLI. To get this set up, follow the instructions in the PreTeXt guide. You will need Python, LaTeX, and pdf2svg (if you wish to compile the html version; this requires an extra step on Windows).

Open up a terminal and in your preferred directory, clone discrete-book repositories:

git clone https://github.com/oscarlevin/discrete-book.git

(If you had previously done this, you will likely want to get the most recent versions of the repository by entering git pull from the discrete-book folder.)

Then change to the discrete-book folder:

cd discrete-book

Compiling

If everything has been set up properly above, you can now execute the following commands to build the book. To create a PDF, you can enter:

pretext build pdf -w

To make the HTML version:

pretext build html -w -d

The -w and -d flags are only needed the first time you compile, to extract the WeBWorK exercises and create SVGs for the images. Use the flags again only if you edit these elements in the source.

Contributing

Any and all suggestions to improve the text are welcome. Thanks to those who have already pointed out typos/issues they have found. If you would like to make a more substantial contribution, please contact me so we can discuss how best to proceed.

Previous editions

The previous editions have branches, and also tags. Feel free to switch to those if you want to grab the source for those editions.

discrete-book's Issues

CSS refactoring issues

The changes I am making to the main CSS files have had some bad consequences
for the HTML of your book.

I use this page as an example:
http://discrete.openmathbooks.org/dmoi/sec_polyfit.html

1. The Greg's L (or at least the horizontal bottom segment) is visible in Investigate!s
   and the left border and padding was messed up. (See ** below.)

2. The Solution's inside the .posterior of examples are not being styled properly.

3. Part of the L near those Solutions is appearing where it shouldn't.

4. The Permalinks are too close to the section titles (I think that is because in new HTML the
   permalink is after, not inside the .heading. (See **)

5. In exercise 1 of 2.3 Exercises the Solution is too far down, but that is because
   there is an empty "p". Presumably that will go away when the HTML is rebuilt. (See **)

** In the following section, the Investigate styling is correct. It is not correct in Sec 2.3
because it is preceded by an empty "p", so the investigate is not the
first-child. If you rebuild the HTML, then all the items with (See **) will change,
so I suggest rebuilding before fiddling with custom CSS.

And before adjusting custom CSS, I suggest letting me know any issues, in case
I can make the main CSS compatible with your customizations. Also, I will continue
to overhaul the main CSS for at least the next week, so let's coordinate the work.
(Also, if you have a deadline substantially before the JMM, please let me know.)

Rework exercises for 0.4

The choice of which exercises have solutions in 0.4 can be improved. In particular, 3 or 4 should have solutions, and one of 7 or 8 should not (they would make nice homework problems). In general, a larger emphasis on functions to compare the cardinality of sets would be an improvement.

Induced subgraph

Currently there is a definition but it is not used again. It would be nice to add something about this here (parallels to subspace/subgroups/etc).

Misc conversion bugs

Each of the following are small and I can fix on my own, but I'm including them in case you wan to polish the conversion script.

1. Text in \begin{center} \end{center} did not get put into a paragraph. (sec_logical-equiv.mbx, line 7).
2. \subsubsection*{...} did not get any treatment at all. (sec_binom.mbx).
3. \tikz{...} does not get any treatement (but \begin{tikz}...\end{tikz} does).
4. No idea why, but the end of sec_matchings.mbx puts \begin{questions} etc into paragraphs instead of converting.

I'll add more as I find them.

Typo in 2.5

The sequence of T's and F's in the Stamps problem is off. Double check this. Thanks to Benny Lo for pointing this out.

MBX does not allow math mode in list labels

In GraphTheory.tex you have

\question Consider the following two graphs:
\begin{itemize}
\item[$G_1$:] $V_1={a,b,c,d,e,f,g}$

The $G_1$ label does not seem possible to translate to MBX, because the label
becomes an attribute, and attributes cannot contain tags.

Error in Exercise 1.5.4c

To fix, change the question to "How many solutions have each variable greater than or equal to -3.

Thanks to Victor Y. for the heads up.

Get solutions in knowls for exercises

I had fixed this in December, but the update for MathJax undid it somehow. Should be an easy fix.

Fix notation math mode problem

Currently, the notation list is messed up because of double math mode. Should be able to fix this by putting the contents of <usage>...</usage> outside of math mode.

margin on exercise-like

I think it looks better without the
margin-left: 1ex;
on article[id*="example"] from line 41 of custom-styles.css

Recent OS update corrupted fonts. Recompile?

Hi. After a recent update on my OS, the fonts don't get rendered properly anymore on several PDF viewers and in Chrome. I brought this up on their forum and they can confirm the corrupted fonts as well. One of the mods suggested a recompilation to see if it can fix the issue.

Here's a screenshot:

Misc Typos

The address on the copyright page is wrong (missing e in Greeley)

Typo in example 1.6.9

The last displayed equation has \langle[ ... \rangle], but should be \left[ ... \right]

Fix exercise 4.2.3

As written, there is something wrong. Thanks to Richard Grassl and Greg Bard for finding this.

discretebook-fall2015.pdf, page 71

Near the bottom of the page is the following sentence:

"Thus the answer to the original question is 13 choose 2 − 75 = 78 − 66 = 3.

The 66 should be 75

discretebook-fall2015.pdf, page 39, exercise 8

In bold:

A group of college students were asked about their TV watching habits. Of those
surveyed, 28 students watch Elementary, 19 watch Castle and 24 watch of The Mentalist.
Additionally, 16 watch Elementary and Castle, 14 watch elementary and The Mentalist
and 10 watch Castle and The Mentalist. There are 8 students who watch all three
shows. How many students surveyed watched at least one of the shows?

Add recursive functions to the functions chapter

Fix MBX warnings about introductions/conclusions for subsections

Not sure if this is changing anything in the output, but still.

Statements vs Predicates

There are times when "statement" is used, where it should be "predicate." In particular, when describing inductive proofs, you write "Let P(n) be the statement..." However P(n) is not a statement, since n is not fixed, so it should more precisely be "Let P(n) be the predicate..." Also, you use "predicate" in Exercise 0.2.9 without defining it until much later.

Defined macros not converting

In the file "macros-discrete.tex" I define a boatload of new LaTeX macros to speed up typing. For example: \def\N{\mathbb N} so I get a nice blackboard N for the natural numbers. These definitions do not get implemented correctly in the mbx at some point along the way.

Would \newcommand{\N}{\mathbb N} fix the problem? Or is this a mathjax issue?

Missing terms in 4.3

The terms "vertex coloring" and "chromatic number" are not tagged as such.

main latex file

Add a line to the readme giving instructions for compiling the book (in particular, indicating
the main LaTeX file)

discretebook-fall2015.pdf, page 76 typo

Near the bottom of the page:

Consider again the problem if giving cookies to kids

Restructure chapter 1

Here is a possible way to restructure chapter 1 to better motivate the material and improve the logical flow of the sections.

1. Binomial coefficients (maybe rename: Pascal's Triangle)
2. Additive and Multiplicative Principles (maybe Sum and Product Principles?)
3. Combinations and Permutations
4. Stars and Bars (Maybe call it: allowing repeats).
5. Advanced PIE

Introduce combinatorial proofs in section 1, and return to these in each section. Add material about bijection arguments, sprinkled throughout.

Advantages:

• The current sequence puts combinatorial proofs between combinations and permuations and stars and bars. This breaks up the flow.
• Leading out of 0.4 on Functions, it would be nice to illustrate the bijection principle immediately.
• Already in the sum/product principle section, we give combinatorial proofs. The new structure would allow us to highlight this.
• Starting with binomial coefficients without giving a method for calculating them sends the message that we can count things qualitatively without needing a numeric answer.
• We can use binomial coefficients in the sum/product section as examples.
• Makes adding bijection principle a reasonable goal without adding a section.
• More emphasis on Pascal's Triangle as a work of art, rather than cheatsheet.

Converting \defbox environments

As you probably noticed, I use a custom environment called \defbox to create the obligatory colored boxed definition/theorem/procedure. These are not really definitions, although that is probably the closest block currently available. Until we get a specific block for this environment, could we through these all into an unused block type, perhaps "convention"? And then the first argument should be the title. That is, for LaTeX:

\begin{defbox}{Box Title}

the MBX would be:

<convention> <title>Box Title</title>

Fix congruence is an equivalence relation box

In the number theory section.

Missing dot in exercise headings for html

After a rebuild, the dot between the chapter and section in the headings for exercises is gone.

fall 2015 p42 typo

in solution 1 to example 1 at bottom of page
text states (sans formatting)
You must simply choose 6 friends from a group of 14. This can be done in 14 choose 4 ways.

Should be 14 choose 6 ways

Implement cases in proofs as cases in ptx

Now that cases are possible as part of PreTeXt, I code them in as such.

labes and filenames for chapters and sections

It is good if the files containing chapters and sections had a meaningful name,
instead of something like "chapter4.(tex or mbx)".

A reasonable approach is to put a LaTeX label on every chapter and section,
and use a version of that label for the filename. See the mbx files for some examples.

terms, and a typo

In Section 1.3.3 (and probably elsewhere) you define a lot of terms. Those should
be wrapped in "term", not "em".

In the 3rd entry of the Set Theory Notation assemblage, extra s in the phrase
"2 is an elements of "

Error in graph example page 200

In Chapter 4 - Graph Theory Page 200 below the definition of graph you have an example of graph.
Here we have a graph with four vertices (the letters a, b, c, d) and four edges
(the pairs {a, b}, {a, c}, {b, c}, {b, d}, {c, d})).
it should be five edges

Accessibility: add descriptions to figures

All figures should have a machine readable description.

An additional task: make the tikz code better (styles as macros).

parts and part

Unless you have more MBX appropriate suggestion for particular cases,
I'm going to convert "parts" into "enumerate" and "part" into "item".

p.36 fall2015 version intersection in place of union

Near the bottom of the page:

|A ∩ B| = |A| + |B| − |A ∩ B|

It seems that should be a union?

|A ∪ B| = |A| + |B| − |A ∩ B|.

Induction typo in 2.5

On page 165 of the tablet version (Example 2.5.1), it should say "let P(n) be the statement 1 + 2 + 3 + ... + n = n(n+1)/2", not "n(n+2)/2".

Terms and glossary

To create a list of symbols for the book, I used the glossaries package. The definitions live inside "symbols.tex". For example, there I have the line

\newgsym{isom}{\cong}{isomorphic to}

which is short for

\newglossaryentry{isom}{type=symbols,name={\ensuremath{\cong}}, sort=isom, description={isomorphic to}}

In the text I can type \gls{isom} and this inserts $\cong$ (ensuring math mode) as well as puts the current page as a reference in the list of symbols.

One way or another, this needs to get implemented in the mbx source.

discretebook-fall2015.pdf, page 53, exercise 5d

Counting how many trapezoids can be made given the 2 rows of 7 dots.

Perhaps it would help to add whether you consider a parallelogram as a trapezoid or not. Before attempting this exercise I checked a few resources and there seems to be 2 camps. One camp states that a trapezoid has exactly 1 set of parallel lines which would exclude parallelograms. The other camp states that a trapezoid has at least 1 set of parallel lines and that a parallelogram is a trapezoid.

You could even make 2 questions out of it based on definition.

Anyways this is more of a sugesstion than an issue.

TikZ in mbx

According to the MBX author guide, there is support for TikZ images in MBX. The converted mbx files, however, insert an image with some long hash-like codename, and these do not show up in the html.

line feeds in proofs

How should the following be translated to MBX?

Do you think that your use of "backslash backslash" (which I translate to
but MBX does not
allow that any more) is primarily used in proofs? If so, then I can probably automate
the translation and you won't need to change your LaTeX.

\begin{proof}
Let $P(n)$ be the statement ``a tree graph $T_n$ with $n$ vertices has $n-1$ edges.
Base Case: Draw a tree with three vertices. Clearly you have only 2 edges (otherwise you would have a cycle).
Inductive Case: Assume $P(k)$ is true for some arbitrary $3<k<n$.
NTS: $P(k+1)$ is true. That is $T_{k+1}$ has $k$ edges.
Let $T_{k+1}$ be a tree graph with $k+1$ vertices. By part (b) we know that every tree with at least 3 vertices has a leaf, so cut that one leaf off of $T_{k+1}$. Then our tree graph has only $k$ vertices, and by our inductive case has $k-1$ edges. Well, if we let that leaf regrow we will add both one edge and one vertex, which means that we will have a tree graph with $k+1$ vertices and $k-1+1=k$ edges. TBTPOMI we have shown that $P(n)$ is true.

\end{proof}

Fix typo: exercise 4.1.4

In graph 1, the last edge should be {c,d} not {c,e} (or else the graphs are not isomorphic)

Bad grammar on page 30 of fall 2015 version

In the fall 2015 version on page 30 exercise 13:

At the end of the semester a teacher assigns letter grades to each of her students.
Is this a function? If so, what sets make up the domain and codomain, and is the
functions be injective, surjective, bijective, or neither?

Questionable text in bold.

Chapter 1 Pg 19 Example 7

1. (D ∩ C)∪ A ∩ B {1, 3, 5, 7, 8, 9}. The set contains all elements that are either
   in D but not in C or not in both A and B.
2. Note the copy/paste did not include the complement symbol *

Should it not also include 10 since the complement of A intersect B is {1,3,5,7,8,9,10}

If not how come?

Number Theory section needs work

The number theory section could use some attention. In particular:

1. Add coverage of the Chinese Remainder Theorem
2. Add more word problems about Diophantine Equations
3. Add more problems in general (including some without solutions).

Typo in example 1.3.5-2

The answer should be 2162160, not 2192190. Thanks to Mario B.

discretebook-fall2015.pdf, page 85 question 3

It seems to be missing information. There are no numbers in the question? How many regular ties and bow ties etc while in the solutions there are numbers.

Also for 3d:
(d) Once you have selected 2 regular and 3 bow ties, in how many orders could you
put the ties on, assuming you must have one of the three bow ties on top?

I don't see why the answer in the solutions is 5!, is this really the correct answer if you must have one of the 3 bow ties on top?

"Exercises" inside Activities

The questions inside the \begin{activity} ... \end{activity} environments should be just items in an ordered list, not given as exercises. I had \begin{questions}...\question ...\end{questions} for easy of copying to my in-class worksheet LaTeX template (although I could easily deal with having this in an enumerate environment).

I can go through my LaTeX and correct this easily enough, it is worth fixing in the conversion script.

discretebook-fall2015.pdf, page 257 solution 1.8.21c

There seems to be a miscalculation.

If there are 20 dollars and each student gets at least 1 dollar but no more than 7 should it not be:

20-7=13 dollars left
give 1 to remaining students:
13-4=9
9 dollars left to distribute to 5 students so 13 choose 4 and not 12 choose 4.

Or another way:
Give 1 dollar to each student 20-5 = 15 dollars left
give 1 student 6 more to reach 7 maximum 15-6=9
etc...

exercises with answers

The MBX for exercises with answers seems good to me, but when I convert to HTML several things go wrong:

"ol" lists in the exercise do not look like lists

The answers appear visibly, in addition to being in a knowl

I have no experience debugging MBX (I just try to convert to the expected markup) so I am not
sure what to do in this case. If the markup needs to be different, then I should be able to fix it.

Fix exercise 4.2.2

The solution claims that there is a graph with the given degree sequence. I think this only works if you allow multigraphs. Changing the degree sequence to 2, 2, 3, 3, 3, 5 would work. Or make it a more involved question and ask why there really isn't a graph like this.