Erickson Introduction to Combinatorics

2. Auflage 2014
ISBN: 978-1-118-64021-0
Verlag: John Wiley & Sons
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 244 Seiten, E-Book

Reihe: Wiley-Interscience Series in Discrete Mathematics and Optimization

Praise for the First Edition
"This excellent text should prove a useful accoutrementfor any developing mathematics program . . . it's short,it's sweet, it's beautifully written."--The Mathematical Intelligencer
"Erickson has prepared an exemplary work . . . stronglyrecommended for inclusion in undergraduate-level librarycollections." --Choice
Featuring a modern approach, Introduction to Combinatorics,Second Edition illustrates the applicability of combinatorialmethods and discusses topics that are not typically addressed inliterature, such as Alcuin's sequence, Rook paths, andLeech's lattice. The book also presents fundamentalresults, discusses interconnection and problem-solving techniques,and collects and disseminates open problems that raise questionsand observations.
Many important combinatorial methods are revisited and repeatedseveral times throughout the book in exercises, examples, theorems,and proofs alike, allowing readers to build confidence andreinforce their understanding of complex material. In addition, theauthor successfully guides readers step-by-step through three majorachievements of combinatorics: Van der Waerden's theorem onarithmetic progressions, Pólya's graph enumerationformula, and Leech's 24-dimensional lattice. Along withupdated tables and references that reflect recent advances invarious areas, such as error-correcting codes and combinatorialdesigns, the Second Edition also features:
* Many new exercises to help readers understand and applycombinatorial techniques and ideas
* A deeper, investigative study of combinatorics throughexercises requiring the use of computer programs
* Over fifty new examples, ranging in level from routine toadvanced, that illustrate important combinatorial concepts
* Basic principles and theories in combinatorics as well as newand innovative results in the field
Introduction to Combinatorics, Second Edition is an idealtextbook for a one- or two-semester sequence in combinatorics,graph theory, and discrete mathematics at the upper-undergraduatelevel. The book is also an excellent reference for anyoneinterested in the various applications of elementarycombinatorics.

Autoren/Hrsg.

Erickson, Martin J.

Inhaltsverzeichnis

Preface xi
1 Basic Counting Methods 1
1.1 The multiplication principle 1
1.2 Permutations 4
1.3 Combinations 6
1.4 Binomial coefficient identities 10
1.5 Distributions 19
1.6 The principle of inclusion and exclusion 23
1.7 Fibonacci numbers 31
1.8 Linear recurrence relations 33
1.9 Special recurrence relations 41
1.10 Counting and number theory 45
Notes 50
2 Generating Functions 53
2.1 Rational generating functions 53
2.2 Special generating functions 63
2.3 Partition numbers 76
2.4 Labeled and unlabeled sets 80
2.5 Counting with symmetry 86
2.6 Cycle indexes 93
2.7 Pólya's theorem 96
2.8 The number of graphs 98
2.9 Symmetries in domain and range 102
2.10 Asymmetric graphs 103
Notes 105
3 The Pigeonhole Principle 107
3.1 Simple examples 107
3.2 Lattice points, the Gitterpunktproblem, and SET®110
3.3 Graphs 115
3.4 Colorings of the plane 118
3.5 Sequences and partial orders 119
3.6 Subsets 124
Notes 126
4 Ramsey Theory 131
4.1 Ramsey's theorem 131
4.2 Generalizations of Ramsey's theorem 135
4.3 Ramsey numbers, bounds, and asymptotics 139
4.4 The probabilistic method 143
4.5 Sums 145
4.6 Van der Waerden's theorem 146
Notes 150
5 Codes 153
5.1 Binary codes 153
5.2 Perfect codes 156
5.3 Hamming codes 158
5.4 The Fano Configuration 162
Notes 168
6 Designs 171
6.1 t-designs 171
CONTENTS ix
6.2 Block designs 175
6.3 Projective planes 180
6.4 Latin squares 182
6.5 MOLS and OODs 185
6.6 Hadamard matrices 188
6.7 The Golay code and S(5, 8, 24) 194
6.8 Lattices and sphere packings 197
6.9 Leech's lattice 199
Notes 201
A Web Resources 205
B Notation 207
Exercise Solutions 211
References 225
Index 227

Über Autor(innen)

MARTIN J. ERICKSON, PhD, is Professor in the Departmentof Mathematics at Truman State University. The author of numerousbooks, including Mathematics for the Liberal Arts (Wiley),he is a member of the American Mathematical Society, MathematicalAssociation of America, and American Association of UniversityProfessors.