Combinatorial Reasoning
An Introduction to the Art of Counting Set
1st Edition
Will be published approx. on 4. November 2014
Book
Paperback/Softback
682 pages
978-1-118-83083-3 (ISBN)
Description
Combinatorial Reasoning: An Introduction to the Art of Counting and Solutions Manual
Written by two well-known scholars in the field, Combinatorial Reasoning: An Introduction to the Art of Counting presents a clear and comprehensive introduction to the concepts and methodology of beginning combinatorics. Focusing on modern techniques and applications, the book develops a variety of effective approaches to solving counting problems.
Balancing abstract ideas with specific topical coverage, the book utilizes real world examples with problems ranging from basic calculations that are designed to develop fundamental concepts to more challenging exercises that allow for a deeper exploration of complex combinatorial situations. Simple cases are treated first before moving on to general and more advanced cases. Additional features of the book include:
* Approximately 700 carefully structured problems designed for readers at multiple levels, many with hints and/or short answers
* Numerous examples that illustrate problem solving using both combinatorial reasoning and sophisticated algorithmic methods
* A novel approach to the study of recurrence sequences, which simplifies many proofs and calculations
* Concrete examples and diagrams interspersed throughout to further aid comprehension of abstract concepts
* A chapter-by-chapter review to clarify the most crucial concepts covered
Combinatorial Reasoning: An Introduction to the Art of Counting is an excellent textbook for upper-undergraduate and beginning graduate-level courses on introductory combinatorics and discrete mathematics
Solutions manual to accompany Combinatorial Reasoning: An Introduction to the Art of Counting
Written by well-known scholars in the field, Combinatorial Reasoning: An Introduction to the Art of Counting 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.
Written by two well-known scholars in the field, Combinatorial Reasoning: An Introduction to the Art of Counting presents a clear and comprehensive introduction to the concepts and methodology of beginning combinatorics. Focusing on modern techniques and applications, the book develops a variety of effective approaches to solving counting problems.
Balancing abstract ideas with specific topical coverage, the book utilizes real world examples with problems ranging from basic calculations that are designed to develop fundamental concepts to more challenging exercises that allow for a deeper exploration of complex combinatorial situations. Simple cases are treated first before moving on to general and more advanced cases. Additional features of the book include:
* Approximately 700 carefully structured problems designed for readers at multiple levels, many with hints and/or short answers
* Numerous examples that illustrate problem solving using both combinatorial reasoning and sophisticated algorithmic methods
* A novel approach to the study of recurrence sequences, which simplifies many proofs and calculations
* Concrete examples and diagrams interspersed throughout to further aid comprehension of abstract concepts
* A chapter-by-chapter review to clarify the most crucial concepts covered
Combinatorial Reasoning: An Introduction to the Art of Counting is an excellent textbook for upper-undergraduate and beginning graduate-level courses on introductory combinatorics and discrete mathematics
Solutions manual to accompany Combinatorial Reasoning: An Introduction to the Art of Counting
Written by well-known scholars in the field, Combinatorial Reasoning: An Introduction to the Art of Counting 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.
More details
Language
English
Place of publication
New York
United States
Target group
College/higher education
Primary & secondary/elementary & high school
Dimensions
Height: 241 mm
Width: 163 mm
Thickness: 43 mm
Weight
1111 gr
ISBN-13
978-1-118-83083-3 (9781118830833)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Person
Duane DeTemple is the author of Combinatorial Reasoning: An Introduction to the Art of Counting Set, published by Wiley.
Content
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 Polya'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
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 Polya'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