Counting: The Art of Enumerative CombinatoricsCounting: 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 | |
2 | |
3 | |
4 | |
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 |
247 | |
Other editions - View all
Common terms and phrases
a₁ adjacent answer arrange basis step 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 exactly example faces Figure flags function girls given graph G group G hamilton cycle Homework II(r induction step integer solutions isomorphic least letters m-color matching mathematical induction Ménage Problem nonnegative integer notation number of elements number of H's pairs 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 vertices white balls words σρ