Counting: The Art of Enumerative CombinatoricsCounting is hard. "Counting" is short for "Enumerative Combinatorics," which certainly doesn't sound easy. This book provides an introduction to discrete mathematics that addresses questions that begin, How many ways are there to... . At the end of the book the reader should be able to answer such nontrivial counting questions as, 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? There are no prerequisites for this course beyond mathematical maturity. The book can be used for a semester course at the sophomore level as introduction to discrete mathematics for mathematics, computer science, and statistics students. The first five chapters can also serve as a basis for a graduate course for in-service teachers. |
Contents
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
7 The Round Table | 7 |
8 The Birthday Problem | 10 |
9 n Choser 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 ConesThe 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 |
24 An Algebraic Excursion to Rx | 45 |
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 |
| 247 | |
Other editions - View all
Common terms and phrases
a₁ adjacent algebra answer arrange basis step begin binary operation boys Burnside's Lemma calculate Cayley table checkerboard chip coefficient collectively know color combinatorics compute consider Corollary cosets count the number cube cycle index cycle type cyclic group degree sequence denote desired sequence diagram dice distinguishable balls distinguishable boxes dodecahedron edges equation equivalence relation euler circuit Euler's Formula exactly example faces factors Figure flags function girls given graph G group G hamilton cycle Homework induction step integer solutions isomorphic least letters m-color matching mathematical induction Ménage Problem nonnegative integer notation number of elements number of T's pairs partition path pattern inventory permutation persons pick planar graph plane positive integer problem proof prove recurrence relation red balls rotation round table sequences of length simple graph square subgroup subset suppose symmetries Theorem vertex white balls words σρ