Combinatorics: A Problem-Based Approach (Problem Books in Mathematics)

✍ Scribed by Pavle Mladenović

• Publisher: Springer
• Year: 2019
• Tongue: English
• Leaves: 372
• Series: Problem Books in Mathematics
• Edition: 1st ed. 2019
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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