Counting: The Art of Enumerative Combinatorics

Front Cover
Springer Science & Business Media, Mar 9, 2013 - Mathematics - 252 pages
Counting: The Art of Enumerative Combinatorics provides an introduction to discrete mathematics that addresses questions that begin, How many ways are there to...For example, ¿How many ways are there to order a collection of 12 ice cream cones if 8 flavors are available?¿ At the end of the book the reader should be able to answer such nontrivial counting questions as, ¿How many ways are there to color the faces of a cube if ¿k¿ colors are available with each face having exactly one color?¿ or ¿How many ways are there to stack ¿n¿ poker chips, each of which can be red, white, blue, or green, such that each red chip is adjacent to at least 1 green chip?¿ Since there are no prerequisites, this book can be used for college courses in combinatorics at the sophomore level for either computer science or mathematics students. The first five chapters have served as the basis for a graduate course for in-service teachers. Chapter 8 introduces graph theory.
 

Contents

1 Counting Is Hard
1
2 Conventions
2
3 Permutations
3
4 A Discussion Question
4
6 n Chose r by Way of MISSISSIPPI
5
7 The Round Table
7
8 The Birthday Problem
10
9 n Chose r with Repetition
11
31 Symmetry Groups
67
32 Legendres Theorem
71
33 Permutation Groups
74
34 Generators
77
35 Cyclic Groups
80
36 Equivalence and Isomorphism
82
37 The Definition
85
38 Burnsides Lemma
88

10 Ice Cream Cones The Double Dip
17
11 Block Walking
18
12 Quickies and Knights
19
13 The Binomial Theorem
22
14 Homework for a Week
23
15 Three Hour Exams
24
The Principle of Inclusion and Exclusion 16 Introduction to PIE
27
17 Proof of PIE
30
18 Derangements
32
19 Partitions
34
20 Balls into Boxes
35
21 A Plethora of Problems
38
22 Eating Out
39
23 What Is x?
44
25 Introducing Generating Functions
46
26 Clotheslines
47
27 Examples and Homework
52
28 Computations
57
29 Exponential Generating Functions
59
30 Comprehensive Exams
64
39 Applications of Burnsides Lemma
94
40 Pólyas Pattern Inventory
100
41 Necklaces
108
42 Examples of Recurrence Relations
113
43 The Fibonacci Numbers
117
44 A Dozen Recurrence Problems
121
45 Solving Recurrence Relations
122
46 The Catalan Numbers
125
47 Nonhomogeneous Recurrence Relations
133
48 The Principle of Mathematical Induction
137
49 The Strong Form of Mathematical Induction
142
50 Halls Marriage Theorem
146
51 The Vocabulary of Graph Theory 153
152
52 Walks Trails Circuits Paths and Cycles
160
53 Trees
168
54 Degree Sequences
175
55 Eulers Formula
177
The Back of the Book
183
Index
247
Copyright

Other editions - View all

Common terms and phrases

About the author (2013)

From the reviews:

"Much of Martin’s charming and accessible text could be used with bright school students. ... The book is rounded off by a section called ‘The back of the book’ which includes solutions and discussion of many exercises. George E. Martin is a remarkable writer who brings combinatorics alive. He has written a splendid introduction that requires very few prerequisites, yet soon delivers the reader into some highly effective methods of counting. The book is highly recommended." (S. C. Russen, The Mathematical Gazette, Vol. 88 (551), 2004)

"This truly is an undergraduate mathematics text; parts of it could be the text for a high school combinatorics course. The author has made a successful effort to illuminate and teach the elementary parts of combinatorics. He uses examples and problems to teach; there are 245 problems in Chapter 1! ... If I were not retired and had been asked to teach an undergraduate course in combinatorics, I would have liked to use this book." (W. Moser, Mathematical Reviews, Issue 2002 g)

"This book is a nice textbook on enumerative combinatorics to undergraduates. It introduces the most important ideas ... . A lot of ‘easy’ applications are given and homework is listed (with hints). The book also touches some elementary graph enumeration problems. The text is clear and easy to follow. It is even suitable to learn it alone, which is also aided by nice exam problems." (Péter L. Erdös, Zentralblatt MATH, Vol. 968, 2001)

"The teaching of topics in discrete mathematics is becoming increasingly popular and this text contains chapters on a number of pertinent areas for exposure at an elementary level. ... The author uses non-worked discovery-type examples to lead into observations about the material. ... There are many interesting exercises for the student to attempt. These are spread throughout the various chapters and are effective in developing interest in the topics. The book contains a ‘Back of the Book’ section rather than an Answers section." (M. J. Williams, The Australian Mathematical Society Gazette, Vol. 29 (1), 2002)

Bibliographic information