# Applied Combinatorics

Mitchel T. Keller, Washington and Lee University

William T. Trotter, Georgia Institute of Technology

Copyright Year: 2017

ISBN 13: 9781973702719

Publisher: Mitchel T. Keller, William T. Trotter

Language: English

## Formats Available

## Conditions of Use

Attribution-ShareAlike

CC BY-SA

## Reviews

Overall, the scope and topics of the book were excellent. There are a few places where figures and other material are "to be added later." read more

Overall, the scope and topics of the book were excellent. There are a few places where figures and other material are "to be added later."

I read Ch 16 on Pólya’s Enumeration Theorem carefully and found no significant errors.

The mathematics of combinatorics will not need to be updated often, but I look forward to future revisions.

The writing of this textbook was approachable, appropriate to undergraduate readers and students approaching combinatorics without much mathematics background. The text is engaging and not patronizing.

The notation was appropriately consistent throughout.

The chapter arrangement (number and content) was well-chosen.

The overall organization was excellent. There is a clear gradual increase in complexity and depth with each passing chapter.

The figures were very nice.

The writing was clear and grammatically correct.

The text is not culturally insensitive or offensive in any way.

As an applied mathematical scientist with undergraduate students entering my lab from a variety of backgrounds, I greatly appreciate the level and scope of this text. It would be perfect as an introduction to combinatorics for students using these techniques for the first time. I've already made several students aware of the resource.

This is a book used at Georgia Tech for a junior level course targeted primarily at students pursuing a B.S. in Computer Science. The purpose of this course is to expose students to combinatorics using applications to emphasize the key concepts... read more

This is a book used at Georgia Tech for a junior level course targeted primarily at students pursuing a B.S. in Computer Science. The purpose of this course is to expose students to combinatorics using applications to emphasize the key concepts and methods. This course is also required for the student s getting a B.S. in Mathematics at Georgia Tech. In a typical semester, 250 Georgia Tech students would be enrolled in this course. As mentioned in the preface of the book, the authors want to show the students the beauty of combinatorics and how combinatorial problems arise naturally in computer science and other fields. The authors confess that in designing the Georgia Tech course, they needed a textbook that would go a bit deeper into combinatorics than the available textbooks.

The book contains almost all the topics I would usually cover in the first discrete mathematics course. Other than congruences (which appear as Exercise 2 in Section 6.10 on page 134), everything that I would teach in an introductory discrete mathematics course is covered: sets, counting, inclusion-exclusion, permutations, binomial coefficients, integers, divisibility, greatest common divisor, recurrence relations, graphs. In addition, there are several other interesting topics covered involving topics closer to the authors such as posets, generating functions, probability, probability and some its applications to combinatorics, graph algorithms, networks flows and applications, P\'{o}lya's enumeration theorem.

The authors are well respected and important researchers in the area of discrete mathematics. The book is correct and up to date with the latest research.

I really like the book and I think it should and will be used by many schools for introductory undergraduate discrete mathematics.

The book is very well written. The authors use a friendly and informal tone throughout the book and employ an interesting cast of characters: Alice, Bob, Carlos, Dave, Xing, Yolanda and Zori, who are all undergraduate students at Georgia Tech taking the 8.05am section of Math3012 Applied Combinatorics. The mathematics presented in the book is mixed with dialogues between these characters discussing the current topics of the course and their relevance in their lives, interests and future plans. I really liked this idea of incorporating student-like characters in the textbook and I would think this would go well with students studying the book on their own who will find their own questions and comments among the ones brought up by Alice, Bob, Carlos, Dave, Xing, Yolanda and Zori.

The tone used by the authors of the book is clear and consistent. The writing and the pictures are neat and tidy. I like the fact that the authors use SageMath throughout the book.

The modularity is very good. I think that individual chapters can be used separately if necessary.

The structure is different from what I am used to seeing in a introduction to discrete mathematics, but I really like it. As mentioned in the preface, the authors confess that they wrote their book to use it in an introductory undergraduate course to discrete mathematics aimed mostly at computer science and mathematics majors. I think they did a great job

Everything is very neat and it seems like the authors have spent a lot of time polishing this material.

The grammar and language are fine.

The text is not offensive in any way.

I really liked the book and I hope to use it at my university soon. It is much better than many expensive books used in introductory undergraduate courses and I hope it will be adopted by more departments and instructors.

## Table of Contents

- 1. An Introduction to Combinatorics
- 2. Strings, Sets and Binomial Coefficients
- 3. Induction
- 4. Combinatorial Basics
- 5. Graph Theory
- 6. Partially Ordered Sets
- 7. Inclusion-Exclusion
- 8. Generating Functions
- 9. Recurrence Equations
- 10. Probability
- 11. Applying Probability to Combinatorics
- 12. Graph Algorithms
- 13. Network Flows
- 14. Combinatorial Applications of Network Flows
- 15. Polya's Enumeration Theorem
- 16. The Many Faces of Combinatorics
- A. Epilogue
- B. Background Material for Combinatorics
- C. List of Notation

## Ancillary Material

## About the Book

*Applied Combinatorics *is an open-source textbook for a course covering the fundamental enumeration techniques (permutations, combinations, subsets, pigeon hole principle), recursion and mathematical induction, more advanced enumeration techniques (inclusion-exclusion, generating functions, recurrence relations, Polyá theory), discrete structures (graphs, digraphs, posets, interval orders), and discrete optimization (minimum weight spanning trees, shortest paths, network flows). There are also chapters introducing discrete probability, Ramsey theory, combinatorial applications of network flows, and a few other nuggets of discrete mathematics.

*Applied Combinatorics* began its life as a set of course notes we developed when Mitch was a TA for a larger than usual section of Tom's MATH 3012: Applied Combinatorics course at Georgia Tech in Spring Semester 2006. Since then, the material has been greatly expanded and exercises have been added. The text has been in use for most MATH 3012 sections at Georgia Tech for several years now. Since the text has been available online for free, it has also been adopted at a number of other institutions for a wide variety of courses. In August 2016, we made the first release of Applied Combinatorics in HTML format, thanks to a conversion of the book's source from LaTeX to MathBook XML. An inexpensive print-on-demand version is also available for purchase. Find out all about ways to get the book.

Since Fall 2016, *Applied Combinatorics* has been on the list of approved open textbooks from the American Institute of Mathematics.

Applied Combinatorics is open source and licensed under the Creative Commons Attribution-ShareAlike 4.0 International License (CC-BY-SA).

## About the Contributors

### Authors

**Mitchel T. Keller** is an assistant professor in the Department of Mathematics at Washington and Lee University, a small liberal arts college in Lexington, Virginia. He holds a B.S. in mathematics from North Dakota State University and a Ph.D. in mathematics from the Georgia Institute of Technology. (His Ph.D. advisor is now his co-author on this book.) Mitch’s research interests are in the combinatorics of partially ordered sets, online algorithms, and combinatorial approaches to Stanley depth of monomial ideals. He likes to travel, bake, and take photographs. (The cover image for the 2016 Edition of Applied Combinatorics is of work his honors thesis student Matthew R. Kiser did on the board in Mitch’s office.) Mitch is also the Managing Director of the Mathematics Genealogy Project.

**William T. Trotter** is a professor in the School of Mathematics at the Georgia Institute of Technology in Atlanta. In a career spanning more than four decades, Tom has been a faculty member and administrator at the University of South Carolina, Arizona State University, and Georgia Tech. He has published extensively on the combinatorics of partially ordered sets, graph theory, Ramsey theory, and extremal combinatorics. His monograph on dimension theory for partially ordered sets has been in print for nearly 25 years. Tom is an avid movie buff, fan of the New York Yankees, and golfer.