Combinatorics: First Steps

Description

The main goal of our book is to provide easy access to the basic principles and methods that combinatorial calculations are based upon. The rule of product, the identity principle, recurrence relations and inclusion-exclusion principle are the most important of the above. Significant parts of the book are devoted to classical combinatorial structures, such as: ordering (permutations), tuples, and subsets (combinations). A great deal of attention is paid to the properties of binomial coefficients, and in particular, to model proofs of combinatorial identities. Problems concerning some exact combinatorial configurations such as paths in a square, polygonal chains constructed with chords of a circle, trees (undirected graphs with no cycles) etc. are included too. All chapters contain a considerable number of exercises of various complexity, from easy training tasks to complex problems which require decent persistence and skill from the one who dares to solve them. If one aims to passively familiarize oneself with the subject, methods and the most necessary facts of combinatorics, then it may suffice to limit one's study to the main text omitting the exercise part of the book. However, for those who want to immerse themselves in combinatorial problems and to gain skills of active research in that field, the exercise section is rather important. The authors hope that the book will be helpful for several categories of readers. University teachers and professors of mathematics may find somewhat unusual coverage of certain matters and exercises which can be readily applied in their professional work. We believe that certain series of problems may serve as a base for serious creative works and essays. This especially refers to students at pedagogical universities and colleges who need to prepare themselves to the teaching of the basics of combinatorics, mainly building on arithmetic and geometry. Most of the exercises of the book are of this very origin. COMBINATORICSFIRST STEPS COMBINATORICSFIRST STEPS Contents Preface Introduction Chapter 1Elementary Enumerations ofCombinations 1. What is Combinatorics? Problems 2. Combinatorial Rule of Product Problems 3. Bijection. Combinatorial Bijection Principle Problems 4. Recurrence 4.1. Sequences 4.2. Definition of a Sequence by a Recurrence Relation 4.3. Relation between Recursive and Direct Formulas 4.4. Recurrence Relations in Combinatorial Problems Problems Chapter 2Basic Concepts of Set Theory 1. Sets 1.1. The Notion of a Set 1.2. Subsets 1.3. Intersection 1.4. Union 1.5. Difference 1.6. Complement 1.7. Cartesian Product 2. Correspondence 2.1. Mapping Problems Chapter 3Basic Combinatorial Structures 1. Order. Permutations 2. Tuples 3. Subsets 4. Numbers Ckn: Combinatorial and Computational Aspects Problems 5. Properties of Binomial Coefficients Ck Problems 6. Raising Binomials to Powers. Newton’s Binomial Formula Problems Chapter 4Paths in a Rectangle Problems Chapter 5Inclusion-Exclusion Principle Problems Chapter 6Trajectories Inside a Circle 1. Zigzags in a Circle without Self-Intersections 2. Trajectories in a Circle with Self-Intersections Problems Chapter 7Trees Problems AUTHORS’CONTACT INFORMATION INDEX Blank Page Blank Page