MAT 481 -- Discrete Mathematics  
Course Information

Professor: D. Bradley

Office: 322 Neville Hall 
Hours: 11:00-11:50 a.m. MWF^* 
Phone: (207) 581-3920

Website: http://www.math.umaine.edu/faculty/bradley/index.html

Text:

Ivan Morton Niven, Mathematics of Choice: How to Count Without Counting, Mathematical Association of America, New Mathematical Library #15R, 1965. ISBN: 978-0-88385-615-4

This enjoyable book, written by an established research mathematician, provides a non-technical, leisurely introduction to enumerative combinatorics. Answers to all the exercises are given at the back, which is helpful for self-study. Originally published by Random House, New York, Mathematics of Choice is now available from the MAA for $24.95 (discounted to $19.95 for MAA members). It can also be purchased from Amazon.com for $24.95 new or $19.99 used.

Lectures:

Although the chosen text is good as far as it goes, it is somewhat limited in depth of coverage. Also, in light of its readability, it would be unnecessarily confining to reserve class periods for the sole purpose of discussing material in the text. My intent therefore is to treat the text more as a point of departure than as a road map that must be religiously followed. This means that I'll likely expand on the list of topics somewhat, and cover some of the topics discussed in the text in greater depth.

Syllabus:

• Permutations and Combinations
• Binomial Coefficients
• Lagrange Inversion
• q-Calculus
• Fibonacci Numbers
• Linear Equations with Unit Coefficients
• Inclusion-Exclusion Principle
• Derangements
• Permanents
• Integer and Set Partitions
• Change for a Dollar
• Generating Functions
• Mathematical Induction
• Analysis of Algorithms, Asymptotics
• Graph Theory
• Trees, Flows and Networks
• Gray codes, Hamilton cycles, Euler tours
• The Assignment Problem, Perfect Matchings
• Chromatic Polynomials

Assessment:

Grades will be assigned primarily on the basis of in-class participation and successful completion of written homework assignments. Instructor reserves the right to either give or dispense with, a final exam.

Reference Texts:

• Ronald Lewis Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics 2nd edition, Addison-Wesley, 1994. ISBN: 0-201-55802-5.

  I used this book as a text when I taught this course back in 2002. It is gives a decent introduction to the topics of recursion, summation, binomial coefficients, and the special number sequences of Stirling, Bernoulli and Euler. The second edition includes material about the revolutionary Gosper-Zeilberger algorithm for mechanical summation. Complete answers are provided for more than 500 exercises. A list of errata can be obtained at Knuth's website, where he offers $2.56 for corrections of previously unnoticed errors.

• Herbert S. Wilf, Generatingfunctionology 2nd edition, Academic Press, 1994. ISBN: 0-12-751956-4.

  This second edition is downloadable for free at the author's website: download Generatingfunctionology, 2nd ed. A third edition, published by AK Peters in 2005 (ISBN: 978-1-56881-279-3) can be ordered here: order Generatingfunctionology, 3rd ed.

  Wilf's book is an excellent resource for learning to work with generating functions. Among other things, he shows how some of the binomial coefficient summations handled somewhat clumsily by Graham, Knuth and Patashnik in Concrete Mathematics can be easily dispensed with by interchanging the order of summation.

• Victor Kac and Pokman cheung, Quantum Calculus, Springer 2002. ISBN: 0-387-95341-8. errata

  Quantum calculus is calculus without limits. The subject begins with Euler, who used q-series generating functions to count partitions of integers. Later, Gauss introduced a q-analog of the binomial coefficients, which were subsequently found to count vector spaces over finite fields, among other things. But it was F. H. Jackson, who in a productive mathematical life spanning the latter part of the nineteenth century and the first half of the twentieth century first developed a systematic theory of q-analogues, including the operations of q-differentiation and q-integration. Thus, Jackson is largely responsible for the creation of the q-calculus. The 112-page book by Kac and Cheung is based on lectures given at MIT, and could equally well be used as a text for the discrete mathematics course here at UMaine.

  University of California Riverside physicist John Baez has written a nice online review of this book as number 183 in his ongoing series This Week's Finds in Mathematical Physics (Week 183).

  A published review, authored by mathematical historian Ranjan Roy, appears in the American Mathematical Monthly, Vol. 110 (Aug.-Sept. 2003), no. 7, 652--657.

• Those who enjoy extracting the combinatorial meaning behind identities of various sorts may like to peruse the award winning book, Proofs that Really Count: The Art of Combinatorial Proof, by mathematics professor and professional magician Arthur T. Benjamin and his co-author Jennifer J. Quinn. Click to read a review of Proofs that Really Count.

  See also Richard Stanley's list of Bijective Proof Problems.

• You can preview the book from which I learned enumerative combinatorics as an undergrad at books.google.com: Combinatorial Enumeration by Ian P. Goulden and David M. Jackson, Dover 2004.
• Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel, 1974 (ISBN: 9027704414) is a charming book, packed with delightful examples and exercises. Get the revised and enlarged edition, translated from French by J. W. Nienhuys.
• Those interested in this history of enumeration may wish to have a look at Combinatorial Enumeration of Groups, Graphs and Chemical Compounds by George Polya and Ronald C. Read, Springer 1987, a translation of Polya's seminal 1937 paper on how to count the ways to color an object possessing rotational or other symmetries, with applications to chemistry. This book also contains a 40-page supplement by the second co-author on the legacy of Polya's paper. The book is reviewed by Russell Merris in The American Mathematical Monthly, vol. 96 (Mar. 1989), no. 3, 269--272.
• Serious students of combinatorics will want to thoroughly acquaint themselves with Richard Stanley's two volumes, Enumerative Combinatorics, Volume 1 and Enumerative Combinatorics Volume, 2. Click for further information, errata, supplemental problems etc.

Reference Articles:

• George E. Andrews, Applications of basic hypergeometric functions, SIAM Review, vol. 16 (Oct. 1974), no. 4, 441--484. Click here for full text of the article.

• Arthur T. Benjamin and Jennifer J. Quinn, An alternate approach to alternating sums: a method to DIE for, The College Mathematics Journal, vol. 39 (May 2008), no. 3, 191--201.

• Donatella Merlini, Renzo Sprugnoli, and Maria Cecilia Verri, The method of coefficients, American Mathematical Monthly, vol. 114 (Jan. 2007), no. 1, 40--57.

• Ranjan Roy, Binomial identities and hypergeometric series, American Mathematical Monthly, vol. 94 (Jan. 1987), no. 1, 36--46.