Introductory Combinatorics

✍ Scribed by Kenneth P. Bogart

• Publisher: Cengage Learning
• Year: 2000
• Tongue: English
• Leaves: 673
• Edition: 3
• Category: Library

✦ Synopsis

This work is designed for introductory courses in combinatorics, or more generally, discrete mathematics. The author has chosen core material of value to students in a wide variety of disciplines: mathematics, computer science, operations research, physical sciences, and behavioural sciences. 1.

✦ Table of Contents

Cover
Title
Preface
Contents
1 An Introduction to Enumeration
Section 1 Elementary Counting Principles
Section 2 Functions and the Pigeonhole Principle
Section 3 Subsets
Section 4 Using Binomial Coefficients
Section 5 Mathematical Induction
Suggested Reading for Chapter 1
2 Equivalence Relations, Partitions, and Multisets
Section 1 Equivalence Relations
Section 2 Distributions and Multisets
Section 3 Partitions and Stirling Numbers
Section 4 Partitions of Integers
Suggested Reading for Chapter 2
3 Algebraic Counting Techniques
Section 1 The Principle of Inclusion and Exclusion
Section 2 The Concept of a Generating Function
Section
Section 4 Recurrence Relations and Generating Functions
Section 5 Exponential Generating Functions
Suggested Reading for Chapter 3
4 Graph Theory
Section 1 Eulerian Walks and the Idea of Graphs
Section 2 Trees
Section 3 Shortest Paths and Search Trees
Section 4 Isomorphism and Planarity
Section 5 Digraphs
Section 6 Coloring
Section 7 Graphs and Matrices
5 Matching and Optimization
Section 1 Matching Theory
Section 2 The Greedy Algorithm
Section 3 Network Flows
Section 4 Flows, Connectivity, and Matching
Suggested Reading for Chapter 5
6 Combinatorial Designs
Section 1 Latin Squares and Graeco—Latin Squares
Section 2 Block Designs
Section 3 Construction and Resolvability of Designs
Section 4 Affine and Projective Planes
Section 5 Codes and Designs
Suggested Reading for Chapter 6
7 Ordered Sets
Section 1 Partial Orderings
Section 2 Linear Extensions and Chains
Section 3 Lattices
Section 4 Boolean Algebras
Section 5 Mobius Functions
Section 6 Products of Orderings
Suggested Reading for Chapter 7
Enumeration under Group Action
Section 1 Permutation Groups
Section 2 Groups Acting on Sets
Section 3 Polya's Enumeration Theorem
Suggested Reading for Chapter 8
Answers to Exercises
Index