Combinatorics: A Problem Based Approach

This text provides a theoretical background for several topics in combinatorial mathematics, such as enumerative combinatorics (including partitions and Burnside's lemma), magic and Latin squares, graph theory, extremal combinatorics, mathematical games and elementary probability. A number of examples are given with explanations while the book also provides more than 300 exercises of different levels of difficulty that are arranged at the end of each chapter, and more than 130 additional challenging problems, including problems from mathematical olympiads. Solutions or hints to all exercises and problems are included. The book can be used by secondary school students preparing for mathematical competitions, by their instructors, and by undergraduate students. The book may also be useful for graduate students and for researchers that apply combinatorial methods in different areas. Preface Contents 1 Introduction 1.1 Sets, Functions, and Relations 1.2 Basic Combinatorial Rules 1.3 On the Subject of Combinatorics Exercises 2 Arrangements, Permutations, and Combinations 2.1 Arrangements 2.2 Arrangements Without Repetitions 2.3 Permutations 2.4 Combinations 2.5 Arrangements of a Given Type 2.6 Combinations with Repetitions Allowed 2.7 Some More Examples 2.8 A Geometric Method of Counting Arrangements 2.9 Combinatorial Identities Exercises 3 Binomial and Multinomial Theorems 3.1 The Binomial Theorem 3.2 Properties of Binomial Coefficients 3.3 The Multinomial Theorem Exercises 4 Inclusion-Exclusion Principle 4.1 The Basic Formula 4.2 The Special Case 4.3 Some More Examples 4.4 Generalized Inclusion-Exclusion Principle Exercises 5 Generating Functions 5.1 Definition and Examples 5.2 Operations with Generating Functions 5.3 The Fibonacci Sequence 5.4 The Recursive Equations 5.5 The Catalan Numbers 5.6 Exponential Generating Functions Exercises 6 Partitions 6.1 Partitions of Positive Integers 6.2 Ordered Partitions of Positive Integers 6.3 Graphical Representation of Partitions 6.4 Partitions of Sets Exercises 7 Burnside's Lemma 7.1 Introduction 7.2 On Permutations 7.3 Orbits and Cycles 7.4 Permutation Groups 7.5 Burnside's Lemma Exercises 8 Graph Theory: Part 1 8.1 The Königsberg Bridge Problem 8.2 Basic Notions 8.3 Complement Graphs and Subgraphs 8.4 Paths and Connected Graphs 8.5 Isomorphic Graphs 8.6 Euler's Graphs 8.7 Hamiltonian Graphs 8.8 Regular Graphs 8.9 Bipartite Graphs Exercises 9 Graph Theory: Part 2 9.1 Trees and Forests 9.2 Planar Graphs 9.3 Euler's Theorem 9.4 Dual Graphs 9.5 Graph Coloring Exercises 10 Existence of Combinatorial Configurations 10.1 Magic Squares 10.2 Latin Squares 10.3 System of Distinct Representatives 10.4 The Pigeonhole Principle 10.5 Ramsey's Theorem 10.6 Arrow's Theorem Exercises 11 Mathematical Games 11.1 The Nim Game 11.2 Golden Ratio in a Mathematical Game 11.3 Game of Fifteen 11.4 Conway's Game of Reaching a Level 11.5 Two More Games Exercises 12 Elementary Probability 12.1 Discrete Probability Space 12.2 Conditional Probability and Independence 12.3 Discrete Random Variables 12.4 Mathematical Expectation 12.5 Law of Large Numbers Exercises 13 Additional Problems 13.1 Basic Combinatorial Configurations 13.2 Square Tables 13.3 Combinatorics on a Chessboard 13.4 The Counterfeit Coin Problem 13.5 Extremal Problems on Finite Sets 13.6 Combinatorics at Mathematical Olympiads 13.7 Elementary Probability 14 Solutions 14.1 Solutions for Chapter 1 14.2 Solutions for Chapter 2 14.3 Solutions for Chapter 3 14.4 Solutions for Chapter 4 14.5 Solutions for Chapter 5 14.6 Solutions for Chapter 6 14.7 Solutions for Chapter 7 14.8 Solutions for Chapter 8 14.9 Solutions for Chapter 9 14.10 Solutions for Chapter 10 14.11 Solutions for Chapter 11 14.12 Solutions for Chapter 12 14.13 Solutions for Chapter 13 Bibliography Index