You are here

A Short Course in Discrete Mathematics

Edward A. Bender and S. Gill Williamson
Dover Publications
Publication Date: 
Number of Pages: 
[Reviewed by
Warren Johnson
, on

This is a real rarity, a Dover book being published for the first time. It is a set of lecture notes that has been used in a sophomore-level Discrete Mathematics course at the University of California at San Diego. They are on the quarter system there, and this course is the first of a two-quarter sequence.  The second quarter, Mathematics for Algorithm and Systems Analysis , also has a set of notes by the same authors that has recently been published by Dover, as they continue to improve their catalog in combinatorics and discrete mathematics.  The back cover describes these as "the university's two most basic courses," leaving me wondering what first-year students are taking at UCSD.

I think the book could be used for a semester-long course, but you might finish it before the end of a semester.  There is an optional section on infinite series at the end; most students would presumably have seen this material somewhere else, but it wouldn't hurt to see it again here.  The book would fit the Discrete Math course at my current institution quite well except for the lack of graph theory, which is in Bender and Williamson's other book.

The book comprises six largely independent units.  Unit BF is on Boolean Functions and Computer Arithmetic, and Unit Lo is on logic. Unit NT is on Number Theory and Cryptography, and Unit SF on Sets and Functions.  (The discussion of cryptography on the internet on pages 72–76 is one of the highlights of the book.)  Unit EO is on Equivalence and Order, and Unit IS on Induction, Sequences and Series.  A typical entry in the index is "Stirling number S(n,k) SF-24"; the index does not say explicitly that this means page 112.  A few things are in more than one unit. For example, Definition 1 on page 1 is the same as Definition 3 on page 95, and Definition 1 on page 54 is also part of Definition 5 on page 39.  Also, the word "injection" is used on page 65, but defined only on page 98.  "Characteristic function" is defined on page 90, but a footnote on page 40 begins "If you remember the definition of characteristic function,...."

The book is generally well-written, although perhaps a bit more terse than some other Discrete Math books.  Occasionally it lapses into a style reminiscent of "See Dick run.  Dick runs fast.  Go Dick go...", for example at the beginning of the section on  modular arithmetic on page 58, or at the beginning of the section on cryptography on page 65.  (I won't speculate on which author wrote what, but one of them writes very well.)  There are a few misspellings, but not many, and a few too many missing words or items of punctuation.

Like a lot of discrete mathematics books, this one often uses C(n,k) for the binomial coefficient n choose k.  I suppose I'm being irrational, but this really annoys me.  On page 104 the authors warn the reader not to confuse the Stirling number (of the second kind, the ones that count subsets; the first kind, that count permutations, are never mentioned) S(n,k) with the binomial coefficient C(n,k).  It would be easier not to if they would use the right notation.  (Incidentally, on the subject of Stirling numbers and notation see Donald Knuth's wonderful "Two Notes on Notation," American Mathematical Monthly , volume 99 (1992), pages 403–422.)  The binomial theorem is misprinted on page 54 (summation index should start at 0, not 1), but at least the notation there is good, and the next display is correct.

Euler's birth year is wrong on pages 39 and 43, but correct in the table of contents.  Also on page 43 is a curious juxtaposition:  the authors describe Gauss's work on straightedge and compass constructions, and then write "It should be noted that, although only 18, Gauss worked very hard at math."  In the next paragraph they discuss Mersenne primes (spelling Mersenne correctly 85.7% of the time), and point out that the 25th and 26th Mersenne primes "were discovered in 1978 by two high school students, Laura Nickel and Curt Noll."  This is a very nice bit of information, but it does make me wonder about the authors' opinion of Nickel's and Noll's work habits.

The mathematical level is higher than in some discrete mathematics books.  The treatment of infinite sequences includes ε and N, the concepts of isomorphism and direct product occur in the discussion of posets, and the student is supposed to know the definition of matrix multiplication in (the starred) Example 23 on page 138.  Although the book is short, it has plenty of good problems, all of them with solutions.  It could do with a bit more polishing, but I like this book.  If you are willing to take a little graph theory from another source, I think it would make an excellent (and inexpensive) basis for a discrete mathematics course in one semester.

Warren Johnson ( is visiting assistant professor of mathematics at Connecticut College.

Boolean Functions and Computer Arithmetic
Number Theory and Cryptography
Sets and Functions
Equivalence and Order
Induction, Sequences and Series
Notation Index
Subject Index
Solutions to Problems