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). Although not in final form, it has already been used as a textbook for several semesters by 2 different instructors at the University of Lethbridge.

Click here for a pdf file of the June 2017 version (approximately 250 pages and 1.2 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

   Index
   List of Notation
Appendix A: Solutions to Selected Exercises