Wiley | 2014 | 484 páginas | rar - pdf | 3,1 Mb
link (password: matav)
With a focus on beginning combinatorics, this book features complete exposition of the discussed topics and over 700 exercises that illustrate the presented concepts and methodology. The book covers fundamental topics in enumeration, all of which are explored in great depth. The authors' approach is very reader-friendly and avoids the "scholarly tone" found in many other related books. Abstract ideas are grounded in familiar concrete settings, and there are far more diagrams within the book than are found in most other related texts. In addition, simple cases are treated first before general and advanced cases, and the notations are kept simple and helpful. To help readers learn how combinatorics interacts with other subjects as a tool or as an application, the book provides brief summaries of basic concepts from probability, power series, and group theory. Each chapter begins with an introduction to the topics covered within the chapter, followed by sections that are each accompanied by a large number of exercises that range from basic calculations to more challenging problems. The exercises are carefully structured to range from the routine to the more advanced. The beginning level problems are designed to confirm and develop students' understanding of the fundamental concepts and calculations, where a calculation is most often based on combinatorial reasoning rather than algebraic manipulation. More advanced exercises allow students to explore and more deeply understand the topics in the chapter and apply the techniques to more complex combinatorial situations. Each chapter also contains a brief summary of the most important concepts covered. Finally, each chapter ends with a few additional problems that further synthesize the ideas that were presented in the chapter. Chapter coverage includes: Initial EnCOUNTers with Combinatorial Reasoning; Arrangements, Selections, and Distributions; Binomial Series and Generating Functions; Alternating Sums, Inclusion-Exclusion, and Rook Polynomials; Recurrence Relations; Special Numbers; Linear Spaces and Recurrences Sequences; and Counting Symmetric Arrangements
CONTENTS
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´olya’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
Sem comentários:
Enviar um comentário