Combinatorics Through Guided Discovery (Bogart)

This book is an introduction to combinatorial mathematics, also known as combinatorics. The book focuses especially, but not exclusively on the part of combinatorics that mathematicians refer to as “counting.” The book consists almost entirely of problems. Some of the problems are designed to lead you to think about a concept, others are designed to help you figure out a concept and state a theorem about it, while still others ask you to prove the theorem. Other problems give you a chance to use a theorem you have proved.

These notes are based on the philosophy that you learn the most about a subject when you are figuring it out directly for yourself, and learn the least when you are trying to figure out what someone else is saying about it. On the other hand, there is a subject called combinatorial mathematics, and that is what we are going to be studying, so we will have to tell you some basic facts. What we are going to try to do is to give you a chance to discover many of the interesting examples that usually appear as textbook examples and discover the principles that appear as textbook theorems. Your main activity will be solving problems designed to lead you to discover the basic principles of combinatorial mathematics. Some of the problems lead you through a new idea, some give you a chance to describe what you have learned in a sequence of problems, and some are quite challenging. When you find a problem challenging, don’t give up on it, but don’t let it stop you from going on with other problems. Frequently you will find an idea in a later problem that you can take back to the one you skipped over or only partly finished in order to finish it off. With that in mind, let’s get started. In the problems that follow, you will see some problems marked on the left with various symbols. The preface gives a full explanation of these symbols and discusses in greater detail why the book is organized as it is! Table 1.1.1, which is repeated from the preface, summarizes the meaning of the symbols.

You may have noticed some standard mathematical words and phrases such as set, ordered pair, function and so on creeping into the problems. One of our goals in these notes is to show how most counting problems can be recognized as counting all or some of the elements of a set of standard mathematical objects. For example, Problem 4 is meant to suggest that the question we asked in Problem 3 was really a problem of counting all the ordered pairs consisting of a bread choice and a filling choice. We use to stand for the set of all ordered pairs whose first element is in and whose second element is in and we call the Cartesian product of and . Thus you can think of Problem 4 as asking you for the size of the Cartesian product of and , that is, asking you to count the number of elements of this Cartesian product.