An Invitation to Combinatorics

Book Preface

Combinatorics is a fun, difficult, broad, and very active area of mathematics. Counting, deciding whether certain configurations exist, and elementary graph theory are where the subject begins. There are a myriad of connections to other areas of mathematics and computer science, and, in fact, combinatorial problems can be found almost everywhere. To learn combinatorics is partly to become familiar with combinatorial topics, problems, and techniques, and partly to develop a can-do attitude toward discrete problem solving. This textbook is meant for a student who has completed an introductory college calculus sequence (a few sections require some knowledge of linear algebra but you can get quite a bit out of this text without a thorough understanding of linear algebra), has some familiarity with proofs, and desires to not only become acquainted with the main topics of introductory combinatorics but also to become a better problem solver.

Key Features

Conversational Style. This text is written for students and is meant to be read. Reading mathematics is difficult, but being able to decipher complicated technical writing is an incredibly useful and transferable skill. The discussions in between the usual theorems, proofs, and examples are meant to facilitate the reader’s (ad)venture into reading a mathematics textbook.

Problem-Solving Emphasis. One advantage of combinatorics is that many of its topics can be introduced without too much jargon. In fact, you can turn to almost any chapter in this book and find problem statements that are understandable regardless of your background. Initially, you may not know how to do a problem or even where to begin, but gaining experience in passing that hurdle is at the heart of becoming a better problem solver. For this to happen, you, the reader, have to get actively involved, and learn by solving problems. Getting the right answer is not really the objective. Rather, it is only by trying to solve a problem that you will really understand what the problem is asking and what subtle issues need to be considered. It is only after you have given the problem a try that you will appreciate the solution. This text gives you ample opportunity to get actively involved. In addition to over 1200 problems, we highlight the following features.

– Collaborative Mini-projects. The mini-projects – there are 10 of these scattered through-out the text – are meant to be projects for groups of three or four students to collaboratively explore. They are organized akin to a science lab. A few preliminary problems are to be done individually. The collaborative part of the project is meant to take up the good part of an afternoon, and it is envisioned that a project report – really a short mathematics paper – will be the result. The mini-projects are of two types. In one type (Mini-projects 1, 6, 7, 8, 9, and 10), the project explores new material that is not covered elsewhere in the text. The second type (Mini-projects 2, 3, 4, and 5) are meant to be done by the students before the relevant topic is covered in class. (This should explain their curious placement in the text.) It has been my experience that much learning happens if the students first work on a topic, in a guided and purposeful manner, on their own, followed by class discussion/lecture.

– Guided Discovery through Scaffolded Projects. In addition to collaborative mini-projects, quite a number of other topics are organized as a sequence of manageable smaller problems. I often assign these problems in consecutive assignments, so that I can provide solutions, and allow time for discussion before proceeding to subsequent steps. In some other problems, students are guided toward a solution through an explicit sequence of steps. Some of the proofs are presented in this format with the hope that an engaged reader, with a paper and pencil at hand, will fill in the details. As such, these problems are aimed at training the reader in the art of reading terse mathematical proofs.
– Warm-Up Problems and Opening Chapter Problems. Nearly every section starts with a warm-up problem. These are relatively straightforward problems, and I use them for in-class group work as a prelude to the discussion of a topic. In contrast, every chapter starts with a more subtle opening problem. My guess is that, for the most part, you, the student, will not be able to do these opening problems before working through the chapter. The purpose is to give you a glimpse of what we are going to do in the chapter, and motivate you to make it through the material. Each opening chapter problem is solved somewhere in the chapter, and all of the warm-up problems have a short answer in Appendix A.
– Selected Hints, Short Answers, Complete Solutions. The appendices have hints, short answers, and complete solutions for selected problems. A problem number in italics –there are 142 of these – indicates that the problem has a complete solution in Appendix
D. Try a problem first without looking at the solution, but when you are stuck –and hopefully you will get stuck often and learn to cherish the experience – then first look at the hint section, then later at the short answer section, and finally at the complete solutions section. The complete solutions serve two purposes. They provide further examples of how to do problems, and they model how to write mathematics in paragraph style. By contrast, the short answers are not particularly helpful in telling you how to do a problem. Instead, after you are done with a problem, the short answer can either reassure you or send you back to the drawing board.

– Open Problems and Conjectures. A number of the chapters end with a section highlight-ing a few easily stated open problems and conjectures. Some of these are important unsolved problems, while others are mere curiosities. This is not meant to be a guide to current cutting-edge research problems. Rather, the modest aim is to whet the reader’s appetite by convincing her that even some seemingly innocent-looking problems remain unsolved, and that combinatorics is an active area of research.
– Historical Asides. I am not a historian and the historical comments and footnotes barely scratch the surface. Even so, combinatorial problems and solutions are a wonderful example of the international nature of mathematics. In addition, mathematics is created by humans who are affected by, participate in, and sometimes, for good or bad, help shape the communities and societies that they are a part of. I will declare success even if just a few of you become curious and further investigate the historical context of the mathematics. I have also chosen to highlight the international nature of combinatorics by naming some well-known mathematical objects differently. See the discussion later in this preface for a bit more context.

Coverage and Organization

The text has more than enough material for a one-semester course in combinatorics at the sophomore or junior level at an American university. The sections of the book that I do not cover in my classes, and that I consider optional, are marked by a ?. Induction proofs and recurrence relations will be used throughout the book and are the subject of Chapter 1. Counting problems – so-called enumerative combinatorics – take up more than half of the book, and are the subject of Chapters 3 through 9.InChapter 3, we introduce a slew of “balls and boxes” problems that serve as an organizing principle for our counting problems. Chapters 3, 4, and 5 cover the basics of permutations and combinations as well as a good dose of exploration of binomial coefficients. Chapters 6 and 7 are on Stirling numbers and integer partitions. Two substantial chapters on the inclusion–exclusion principle and generating functions conclude our treatment of enumerative combinatorics. Graph theory is about one-third of the book and is covered in Chapters 2 and 10. The basic vocabulary of graphs is introduced early in Section 2.2, but, for the most part, the material on graph theory is independent of the other chapters. I start the course with Ramsey theory since I want to make sure that all students are seeing something new, and that they are not lulled into thinking that the class is going to be only about permutations and combinations. But Ramsey theory is difficult and could be postponed to much later. Alternatively, you could start with Chapter 10, and do graph theory first. Finally, Chapter 11 brings together material on partially ordered sets, a favorite of mine. Matchings in bipartite graphs is also covered in this chapter, since I wanted to bring out the close connection between the two frameworks.

The instructor may want to augment the usual fare of introductory combinatorics with one or two more substantial results. Among the topics offered here are the Chung–Feller theorem, Euler’s pentagonal number theorem, Cayley’s theorem on labeled trees, Stanley’s theorem on acyclic orientations, Thomassen’s five-color theorem, Pick’s formula, the Erd˝os–Ko–Rado theorem, Ramsey’s theorem for hypergraphs, and Möbius inversion.

The Global Roots of Combinatorics and the Naming of Mathematical Objects

Most “new” mathematical ideas and concepts have antecedents and precursors in older ones, and, as a result, the search for the “first” appearance of this or that mathematics is never-ending and often futile. As such the naming of mathematical objects and results sometimes –possibly always – is a bit arbitrary.1 However, when you look at the totality of the common names of mathematical objects in combinatorics – Pascal’s triangle, Vandermonde’s identity, Catalan numbers, Stirling numbers, Bell numbers, or Fibonacci numbers – a remarkable and seemingly non-random pattern emerges. All the names chosen are from the European tradition. Undoubtedly, European mathematicians contributed significantly – and, in many subareas of mathematics, decisively – to the development of mathematics. However, this constellation of names conveys to the beginning student that combinatorial ideas and investigations were limited to Europe. In the case of combinatorics, nothing could be further from the truth. Mathematicians from China, Japan, India, Iran, northern Africa, the wider Islamic world, and the Hebrew tradition, to mention a few, have very much worked on these topics. (For some of this history, see Wilson and Watkins 2013.) Certainly, the later European scholars have taken some topics further, but this does not take away from the international character of mathematics in general and combinatorics in particular. For this reason, we have tried to use a more inclusive set of names for at least some of the familiar objects. It is completely understandable to want to be familiar with the more common – often universally accepted – names for various objects, and those are pointed out in the text as well. The author does not claim expertise in the history of combinatorics, and it is quite possible that very good historical arguments can be made in support of other attributions or against the ones suggested here. If such a discussion ensues, we will all be better for it.
1 “It takes a thousand men to invent a telegraph or a steam engine, or a phonograph, or a telephone, or any other