This book is an introduction to combinatorial mathematics, also known as combinatorics. The book focuses especially but not exclusively on the part of combinatorics that mathematicians refer to as “counting.” The book consist almost entirely of problems. Some of the problems are designed to lead you to think about a concept, others are designed to help you figure out a concept and state a theorem about it, while still others ask you to prove the theorem. Other problems give you a chance to use a theorem you have proved. From time to time there is a discussion that pulls together some of the things you have learned or introduces a new idea for you to work with. Many of the problems are designed to build up your intuition for how combinatorial mathematics works. Above all, this book is dedicated to the principle that doing mathematics is fun. As long as you know that some of the problems are going to require more than one attempt before you hit on the main idea, you can relax and enjoy your successes, knowing that as you work more and more problems and share more and more ideas, problems that seemed intractable at first become a source of satisfaction later on. This book is released under an open source licence and is available in electronic form for free at http://bogart.openmathbooks.org/.
Author(s): Kenneth P. Bogart, Mitchel T. Keller (editor), Oscar Levin (editor), Kent E. Morrison (editor)
Edition: First PreTeXt Edition
Publisher: CreateSpace Independent Publishing Platform
Year: 2017
Language: English
Commentary: https://bogart.openmathbooks.org/
Pages: 220
Tags: Combinatorics; Combinatorial Mathematics; Counting; Graph Theory; Distribution; Relations; Mathematical Induction
About the Author
Preface
Preface to PreTeXt edition
What is Combinatorics?
About These Notes
Basic Counting Principles
The sum and product principles
Functions and directed graphs
The bijection principle
Counting subsets of a set
Pascal's Triangle
The quotient principle
Some Applications of the Basic Principles
Lattice paths and Catalan Numbers
The Binomial Theorem
The pigeonhole principle
Ramsey Numbers
Supplementary Chapter Problems
Applications of Induction and Recursion in Combinatorics and Graph Theory
Some Examples of Mathematical Induction
Mathematical induction
Binomial Coefficients and the Binomial Theorem
Inductive definition
Proving the general product principle (Optional)
Double Induction and Ramsey Numbers
A bit of asymptotic combinatorics
Recurrence Relations
Examples of recurrence relations
Arithmetic Series (optional)
First order linear recurrences
Geometric Series
Graphs and Trees
Undirected graphs
Walks and paths in graphs
Counting vertices, edges, and paths in trees
Spanning trees
Minimum cost spanning trees
The deletion/contraction recurrence for spanning trees
Shortest paths in graphs
Supplementary Problems
Distribution Problems
The idea of a distribution
The twentyfold way
Ordered functions
Multisets
Compositions of integers
Broken permutations and Lah numbers
Partitions and Stirling Numbers
Stirling Numbers of the second kind
Stirling Numbers and onto functions
Stirling Numbers and bases for polynomials
Partitions of Integers
The number of partitions of k into n parts
Representations of partitions
Ferrers and Young Diagrams and the conjugate of a partition
Partitions into distinct parts
Supplementary Problems
Generating Functions
The Idea of Generating Functions
Visualizing Counting with Pictures
Picture functions
Generating functions
Power series
Product principle for generating functions
The extended binomial theorem and multisets
Generating functions for integer partitions
Generating Functions and Recurrence Relations
How generating functions are relevant
Fibonacci numbers
Second order linear recurrence relations
Partial fractions
Catalan Numbers
Supplementary Problems
The Principle of Inclusion and Exclusion
The size of a union of sets
Unions of two or three sets
Unions of an arbitrary number of sets
The Principle of Inclusion and Exclusion
Application of Inclusion and Exclusion
Multisets with restricted numbers of elements
The Menage Problem
Counting onto functions
The chromatic polynomial of a graph
Deletion-Contraction and the Chromatic Polynomial
Supplementary Problems
Groups acting on sets
Permutation Groups
The rotations of a square
Groups of Permutations
The symmetric group
The dihedral group
Group tables (Optional)
Subgroups
The cycle structure of a permutation
Groups Acting on Sets
Groups acting on colorings of sets
Orbits
The Cauchy-Frobenius-Burnside Theorem
Pólya-Redfield Enumeration Theory
The Orbit-Fixed Point Theorem
The Pólya-Redfield Theorem
Supplementary Problems
Relations
Relations as sets of Ordered Pairs
The relation of a function
Directed graphs
Digraphs of Functions
Equivalence relations
Mathematical Induction
The Principle of Mathematical Induction
The ideas behind mathematical induction
Mathematical induction
Proving algebraic statements by induction
Strong Induction
Exponential Generating Functions
Indicator Functions
Exponential Generating Functions
Applications to recurrences.
Using calculus with exponential generating functions
The Product Principle for EGFs
The Exponential Formula
Supplementary Problems
Hints to Selected Problems
GNU Free Documentation License
Index
