Combinatorial Reasoning (eBook)

An Introduction to the Art of Counting

Duane DeTemple, William Webb (Autoren)

eBook Download: PDF

2014 | 1. Auflage
488 Seiten
Wiley (Verlag)
978-1-118-83370-4 (ISBN)

Infos

Written by well-known scholars in the field, this book introduces combinatorics alongside modern techniques, showcases the interdisciplinary aspects of the topic, and illustrates how to problem solve with a multitude of exercises throughout. The authors' approach is very reader-friendly and avoids the 'scholarly tone' found in many books on this topic.

Combinatorial Reasoning: An Introduction to the Art of Counting:

• Focuses on enumeration and combinatorial thinking as a way to develop a variety of effective approaches to solving counting problems
• Includes brief summaries of basic concepts from probability, power series, and group theory to show how combinatorics interacts with other fields
• Provides abstract ideas that are grounded in familiar concrete settings and features plentiful diagrams throughout to further add in reader understanding
• Presents simple and helpful notations as needed, and simple cases are treated first before more general and/or advanced cases
• Contains over 700 exercise sets, ranging from the routine to the advanced, with either hints, short answers, or complete solutions for odd numbered problems.  An Instructor's Manual (available via request to the Publisher) provides complete solutions for all exercises

Autor

DUANE DETEMPLE, PHD, is Professor Emeritus in the Department of Mathematics at Washington State University (WSU). He is the recipient of the 2007 WSU Sahlin Faculty Excellence Award for Instruction as well as the Distinguished Teaching Award from the Pacific Northwest Section of the Mathematical Association of America. WILLIAM WEBB, PHD, is Professor in the Department of Mathematics at Washington State University and President of the Fibonacci Association. His research interests include the properties of recurrence sequences and binomial coefficients. He is the author of numerous research publications on combinatorics, number theory, fair division, and cryptography.

Inhalt

PREFACE ix

PART I THE BASICS OF ENUMERATIVE COMBINATORICS

1 Initial EnCOUNTers with Combinatorial Reasoning 3

1.1 Introduction 3

1.2 The Pigeonhole Principle 3

1.3 Tiling Chessboards with Dominoes 13

1.4 Figurate Numbers 18

1.5 Counting Tilings of Rectangles 24

1.6 Addition and Multiplication Principles 33

1.7 Summary and Additional Problems 46

References 50

2 Selections, Arrangements, and Distributions 51

2.1 Introduction 51

2.2 Permutations and Combinations 52

2.3 Combinatorial Models 64

2.4 Permutations and Combinations with Repetitions 77

2.5 Distributions to Distinct Recipients 86

2.6 Circular Permutations and Derangements 100

2.7 Summary and Additional Problems 109

Reference 112

3 Binomial Series and Generating Functions 113

3.1 Introduction 113

3.2 The Binomial and Multinomial Theorems 114

3.3 Newton's Binomial Series 122

3.4 Ordinary Generating Functions 131

3.5 Exponential Generating Functions 147

3.6 Summary and Additional Problems 163

References 166

4 Alternating Sums, Inclusion-Exclusion Principle, Rook Polynomials, and Fibonacci Nim 167

4.1 Introduction 167

4.2 Evaluating Alternating Sums with the DIE Method 168

4.3 The Principle of Inclusion-Exclusion (PIE) 179

4.4 Rook Polynomials 191

4.5 (Optional) Zeckendorf Representations and Fibonacci Nim 202

4.6 Summary and Additional Problems 207

References 210

5 Recurrence Relations 211

5.1 Introduction 211

5.2 The Fibonacci Recurrence Relation 212

5.3 Second-Order Recurrence Relations 222

5.4 Higher-Order Linear Homogeneous Recurrence Relations 233

5.5 Nonhomogeneous Recurrence Relations 247

5.6 Recurrence Relations and Generating Functions 257

5.7 Summary and Additional Problems 268

References 273

6 Special Numbers 275

6.1 Introduction 275

6.2 Stirling Numbers 275

6.3 Harmonic Numbers 296

6.4 Bernoulli Numbers 306

6.5 Eulerian Numbers 315

6.6 Partition Numbers 323

6.7 Catalan Numbers 335

6.8 Summary and Additional Problems 345

References 352

PART II TWO ADDITIONAL TOPICS IN ENUMERATION

7 Linear Spaces and Recurrence Sequences 355

7.1 Introduction 355

7.2 Vector Spaces of Sequences 356

7.3 Nonhomogeneous Recurrences and Systems of Recurrences 367

7.4 Identities for Recurrence Sequences 378

7.5 Summary and Additional Problems 390

8 Counting with Symmetries 393

8.1 Introduction 393

8.2 Algebraic Discoveries 394

8.3 Burnside's Lemma 407

8.4 The Cycle Index and Pólya's Method of Enumeration 417

8.5 Summary and Additional Problems 430

References 432

PART III NOTATIONS INDEX, APPENDICES, AND SOLUTIONS TO SELECTED ODD PROBLEMS

Index of Notations 435

Appendix A Mathematical Induction 439

A.1 Principle of Mathematical Induction 439

A.2 Principle of Strong Induction 441

A.3 Well Ordering Principle 442

Appendix B Searching the Online Encyclopedia of Integer Sequences (OEIS) 443

B.1 Searching a Sequence 443

B.2 Searching an Array 444

B.3 Other Searches 444

B.4 Beginnings of OEIS 444

Appendix C Generalized Vandermonde Determinants 445

Hints, Short Answers, and Complete Solutions to Selected Odd Problems 449

INDEX 467

Produkt-Details

• Erscheint lt. Verlag: 2.4.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• Schlagworte: Abstract • Applications • APPROACHES • ART • Aspects • Book • clear • combinatorial • combinatorics • Computer Science • Concepts • Discrete Mathematics • Diskrete Mathematik • Effective • Exercises • Ideas • Informatik • Interdisciplinary • Introduction • Kombinatorik • Mathematics • Mathematik • Modern • Multitude • presents • Problem • Problems • solve • two • variety
• ISBN-10: 1-118-83370-8 / 1118833708
• ISBN-13: 978-1-118-83370-4 / 9781118833704