Combinatorics


an upper-level introductory course in enumeration, graph theory, and design theory

by Joy Morris


 


This free undergraduate text book provides an introduction to enumeration, graph theory, and design theory. It is aimed at upper-level undergraduate students and the exercises expect some mathematical sophistication, including a reasonable ability to construct proofs. The text is designed to be used in an undergraduate course, but could be suitable for independent study by a student with some mathematical background and understanding of proofs. It does not assume any background knowledge of combinatorics.

The book is being released online with a Creative Commons license (Attribution-NonCommercial-ShareAlike 2.0). It has already been used as a textbook for several semesters by 2 different instructors at the University of Lethbridge, as well as at a number of other universities. Version 2.1 (July 2022) includes the updates of 2.0 (several optional new sections, a web-based format, an appendix on complex numbers and an appendix containing biographies of mathematicians whose work is referenced) as well as some additional biographies and other edits.

Click here for the web-based format of the July 2022 version (produced using PreTeXt). Click here for a pdf file of the July 2022 version (approximately 350 pages and 1.5 MB)
The LaTeX source files are available by request. E-mail the author to request these.

 

Table of Contents

1. What is Combinatorics?

Part I. Enumeration
2. Basic Counting Techniques
3. Permutations, Combinations, and the Binomial Theorem
4. Bijections and Combinatorial Proofs
5. Counting with Repetitions
6. Induction and Recursion
7. Generating Functions
8. Generating Functions and Recursion
9. Some Important Recursively-Defined Sequences
10. Other Basic Counting Techniques

Part II. Graph Theory
11. Basics of Graph Theory
12. Moving Through Graphs
13. Euler and Hamilton
14. Graph Colouring
15. Planar Graphs

Part III. Design Theory
16. Latin Squares
17. Designs
18. More Designs
19. Designs and Codes

Appendix A: Complex Numbers
Appendix B: Biographical Briefs
Appendix C: Solutions to Selected Exercises
   List of Notation
   Index