Foundations of Combinatorics with Applications

Edward A. Bender, S. Gill Williamson

• Publisher: Dover Publications
• Year: 2013
• Print ISBN: 9780486446035
• eBook ISBN: 9780486151502
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

This introduction to combinatorics, the foundation of the interaction between computer science and mathematics, is suitable for upper-level undergraduates and graduate students in engineering, science, and mathematics.
The four-part treatment begins with a section on counting and listing that covers basic counting, functions, decision trees, and sieving methods. The following section addresses fundamental concepts in graph theory and a sampler of graph topics. The third part examines a variety of applications relevant to computer science and mathematics, including induction and recursion, sorting theory, and rooted plane trees. The final section, on generating functions, offers students a powerful tool for studying counting problems. Numerous exercises appear throughout the text, along with notes and references. The text concludes with solutions to odd-numbered exercises and to all appendix exercises.

PART I

Counting and Listing

Enumerative combinatorics deals with listing and counting the elements in finite sets. Why is this of interest? Determining the number of elements in a finite set is the fundamental tool in the analysis of the running times and space demands of computer algorithms. It is also of importance in various areas of science, most notably statistical mechanics and structural chemistry, and in some areas of mathematics. Listing elements plays a role in the design of algorithms and in structural chemistry as well as other areas. In addition, the questions may be interesting in themselves; that is, some people find questions of the form “How many structures are there such that ... ?” interesting.

In this part we’ll study some fundamental counting and listing techniques. These tools are useful throughout combinatorics and many of them are essential for other topics that are covered later in the text. In particular, the Rules of Sum and Product form the basis of practically all of our counting calculations. The set theoretic notation and terminology that we introduce in the first two chapters is also important for the remainder of the text.

Here are some examples of the types of problems that our tools will enable us to solve systematically.

Example 1 Birthdays There are 30 students in a classroom. What is the probability that all of them have different birthdays? Let’s assume that people are equally likely to be born on each day of the year and that a year has 365 days. (Neither assumption is quite correct.) Suppose we could determine the number of possible ways birthdays could be assigned to 30 people, say N, and the number of ways this could be done so that all the birthdays are different, say D. Our answer would be D/N.

Example 2 Names In a certain land on a planet in a galaxy far away the alphabet contains only 5 letters which we will transliterate as A, I, L, S and T in that order. All names are 6 letters long, begin and end with consonants and contain two vowels which are not adjacent to each other. Adjacent consonants must be different. How many possible names are there? Devise a systematic method for listing them in dictionary order. The list begins with LALALS, LALALT, LALASL, LALAST, LALATL, LALATS, LALILS and ends with TSITAT, TSITIL, TSITIS, TSITIT.

Example 3 Data storage An ecologist plans to simulate on a computer the growth of a biological community containing 6 competing species. He plans to try numerous variations in the environment. After each simulation, he’ll order the species from most abundant to least abundant. He wants to keep track of how often each ordering occurs and, after his simulations are over, manipulate the collection of counts in various ways. How can he index his storage in a compact manner?

Example 4 Arrangements We have 32 identical dominoes with no marks on them and a chessboard. Each domino will exactly cover two squares of the chessboard. How many ways can we arrange the dominoes so that they cover the entire board?

Example 5 Symmetries We have a cube, some red paint and some green paint. How many different ways can we paint the cube so that each face is either all red or all green? Obtain a list of all the different ways. A first approach to this problem might be to consider coloring the first face red or green, then the second red or green and so on until we have a list of all the possibilities. This ignores an important fact about the problem: a cube looks the same from many points of view; i.e., it has symmetries. For example, there is only one way to color a cube so that it has one red face and five green ones.

In the next four chapters, we’ll study some fundamental techniques for counting and listing structures. What do we mean by “structures?” It is simply a general term for w...

Table of contents

• Title Page
• Copyright Page
• Table of Contents
• Preface
• PART I - Counting and Listing
• PART II - Graphs
• PART III - Recursion
• PART IV - Generating Functions
• APPENDIX A - Induction
• APPENDIX B - Rates of Growth and Analysis of Algorithms
• APPENDIX C - Basic Probability
• APPENDIX D - Partial Fractions
• Solutions to Odd Exercises
• Subject Index