Introduction to Combinatorics / Edition 1

Introduction to Combinatorics / Edition 1

ISBN-10:
1439806225
ISBN-13:
9781439806227
Pub. Date:
09/02/2010
Publisher:
Taylor & Francis

Hardcover

Current price is , Original price is $97.95. You
Select a Purchase Option (Older Edition)
  • purchase options

Overview

Introduction to Combinatorics / Edition 1

Introduction to Combinatorics presents approaches for solving counting and structural questions. It looks at how many ways a selection or arrangement can be chosen with a specific set of properties and determines if a selection or arrangement of objects exists that has a particular set of properties.

The authors first discuss several examples of typical combinatorial problems. They also provide basic information on sets, proof techniques, enumeration, and graph theory-topics that appear frequently throughout the book. The next few chapters explore enumerative ideas, including the pigeonhole principle and inclusion/exclusion. The text then covers enumerative functions and the relations between them. It describes generating functions and recurrences, important families of functions, and the theorems of Pólya and Redfield. The authors also present introductions to computer algebra and group theory, before considering structures of particular interest in combinatorics: graphs, codes, Latin squares, and experimental designs. The last chapter further illustrates the interaction between linear algebra and combinatorics.

Features

Covers key families of functions, including Catalan, Bell, and Stirling numbers

Explains graph theory, coding theory, and design theory

Illustrates traditional problems with modern examples, such as digital music tracks

Discusses Maple™, Mathematica®, and other technological tools where appropriate

Provides background material in the appendices on sets, induction, proof techniques, vectors, and matrices

This accessible text explores the different ways of arranging objects and selecting objects from a set. It clearly explains how to solve the various problems that arise in this branch of mathematics.

Product Details

ISBN-13: 9781439806227
Publisher: Taylor & Francis
Publication date: 09/02/2010
Series: Discrete Mathematics and Its Applications Series , #60
Edition description: Older Edition
Pages: 396
Product dimensions: 6.30(w) x 9.30(h) x 1.00(d)

About the Author

W.D. Wallis is Emeritus Professor of Mathematics at Southern Illinois University. His research interests include combinatorial designs, Latin squares, graph labeling, one-factorizations, and intelligent networks. Dr. Wallis is the author of Introduction to Combinatorial Designs, Second Edition (CRC Press, 2007).

J.C. George is an assistant professor of mathematics in the Division of Mathematics and Natural Sciences at Gordon College in Barnesville, Georgia. His research interests include one-factorizations, graph products, and the relationships of algebraic structures to combinatorial objects.

Table of Contents

List of Figures xiii

Preface xv

1 Introduction 1

1.1 Some Combinatorial Examples 1

1.2 Sets, Relations and Proof Techniques 13

1.3 Two Principles of Enumeration 15

1.4 Graphs 18

1.5 Systems of Distinct Representatives 20

Exercises 1A 22

Exercises 1B 23

Problems 25

2 Fundamentals of Enumeration 27

2.1 Permutations and Combinations 27

2.2 Applications of P (n,k) and $$$ 29

2.3 Permutations and Combinations of Multisets 32

2.4 Applications and Subtle Errors 36

2.5 Algorithms 39

Exercises 2A 41

Exercises 2B 43

Problems 44

3 The Pigeonhole Principle and Ramsey's Theorem 47

3.1 The Pigeonhole Principle 47

3.2 Applications of the Pigeonhole Principle 48

3.3 Ramsey's Theorem - the Graphical Case 51

3.4 Ramsey Multiplicity 54

3.5 Sum-Free Sets 56

3.6 Bounds on Ramsey Numbers 59

3.7 The General Form of Ramsey's Theorem 63

Exercises 3A 63

Exercises 3B 64

Problems 66

4 The Principle of Inclusion and Exclusion 69

4.1 Unions of Events 69

4.2 The Principle 71

4.3 Combinations with Limited Repetitions 75

4.4 Derangements 77

Exercises 4A 80

Exercises 4B 81

Problems 83

5 Generating Functions and Recurrence Relations 85

5.1 Generating Functions 85

5.2 Recurrence Relations 89

5.3 From Generating Function to Recurrence 94

5.4 Exponential Generating Functions 95

Exercises 5A 97

Exercises 5B 99

Problems 100

6 Catalan, Bell and Stirling Numbers 103

6.1 Introduction 103

6.2 Catalan Numbers 104

6.3 Stirling Numbers of the Second Kind 108

6.4 Bell Numbers 113

6.5 Stirling Numbers of the First Kind 114

6.6 Computer Algebra and Other Electronic Systems 117

Exercises 6A 119

Exercises 6B 121

Problems 122

7 Symmetries and the Pólya-Redfield Method 123

7.1 Introduction 123

7.2 Basics of Groups 124

7.3 Permutations and Colorings 130

7.4 An Important Counting Theorem 131

7.5 Pólya and Redfield's Theorem 134

Exercises 7A 138

Exercises 7B 139

Problems 140

8 Introduction to Graph Theory 143

8.1 Degrees 143

8.2 Paths and Cycles in Graphs 146

8.3 Maps and Graph Coloring 149

Exercises 8A 153

Exercises 8B 155

Problems 156

9 Further Graph Theory 159

9.1 Euler Walks and Circuits 159

9.2 Application of Euler Circuits to Mazes 164

9.3 Hamilton Cycles 166

9.4 Trees 170

9.5 Spanning Trees 174

Exercises 9A 180

Exercises 9B 184

Problems 187

10 Coding Theory 189

10.1 Errors; Noise 189

10.2 The Venn Diagram Code 190

10.3 Binary Codes; Weight; Distance 192

10.4 Linear Codes 195

10.5 Hamming Codes 198

10.6 Codes and the Hat Problem 200

10.7 Variable-Length Codes and Data Compression 201

Exercises 10A 203

Exercises 10B 204

Problems 205

11 Latin Squares 207

11.1 Introduction 207

11.2 Orthogonality 211

11.3 Idempotent Latin Squares 217

11.4 Partial Latin Squares and Subsquares 219

11.5 Applications 221

Exercises 11A 225

Exercises 11B 228

Problems 229

12 Balanced Incomplete Block Designs 231

12.1 Design Parameters 232

12.2 Fisher's Inequality 236

12.3 Symmetric Balanced Incomplete Block Designs 238

12.4 New Designs from Old 240

12.5 Difference Methods 242

Exercises 12A 245

Exercises 12B 247

Problems 248

13 Linear Algebra Methods in Combinatorics 251

13.1 Recurrences Revisited 251

13.2 State Graphs and the Transfer Matrix Method 253

13.3 Kasteleyn's Permanent Method 260

Exercises 13A 265

Exercises 13B 267

Problems 268

Appendix 1 Sets; Proof Techniques 271

A1.1 Sets and Basic Set Operations 271

A1.2 The Principle of Mathematical Induction 279

A1.3 Some Applications of Induction 281

A1.4 Binary Relations on Sets 283

Exercises A 285

Exercises B 286

Appendix 2 Matrices and Vectors 291

A2.1 Definitions 291

A2.2 Vector and Matrix Products 294

A2.3 Inverses 296

A2.4 Determinants 298

Exercises A 299

Exercises B 301

Appendix 3 Some Combinatorial People 305

Solutions to Set A Exercises 313

Hints for Problems 341

Solutions to Problems 347

References 367

Index 375

What People are Saying About This

From the Publisher

… thoughtfully written, contain[s] plenty of material and exercises … provides numerous fragments of Mathematica code and this is a nice touch. …
MAA Reviews, February 2011

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews