Combinatorics

A mathematical gem-freshly cleaned and polished

This book is intended to be used as the text for a first course in combinatorics. the text has been shaped by two goals, namely, to make complex mathematics accessible to students with a wide range of abilities, interests, and motivations; and to create a pedagogical tool, useful to the broad spectrum of instructors who bring a variety of perspectives and expectations to such a course.

Features retained from the first edition:

• Lively and engaging writing style
• Timely and appropriate examples
• Numerous well-chosen exercises
• Flexible modular format
• Optional sections and appendices

Highlights of Second Edition enhancements:

• Smoothed and polished exposition, with a sharpened focus on key ideas
• Expanded discussion of linear codes
• New optional section on algorithms
• Greatly expanded hints and answers section
• Many new exercises and examples

Contents

• The Mathematics of Choice
  • The Fundamental Counting Principle
  • Pascal's Triangle
  • Elementary Probability
  • Error-Correcting Codes
  • Combinatorial Identities
  • Four Ways to Choose
  • The Binomial and Multinomial Theorems
  • Partitions
  • Elementary Symmetric Functions
  • Combinatorial Algorithms
• The Combinatorics of Finite Functions
  • Stirling Numbers of the Second Kind
  • Bells, Balls, and Urns
  • The Principle of Inclusion and Exclusion
  • Disjoint Cycles
  • Stirling Numbers of the First Kind
• Pólya's Theory of Enumeration
  • Function Composition
  • Permutation Groups
  • Burnside's Lemma
  • Symmetry Groups
  • Color Patterns
  • Pólya's Theorem
  • The Cycle Index Polynomial
• Generating Functions
  • Difference Sequences
  • Ordinary Generating Functions
  • Applications of Generating Functions
  • Exponential Generating Functions
  • Recursive Techniques
• Enumeration in Graphs
  • The Pigeonhole Principle
  • Edge Colorings and Ramsey Theory
  • Chromatic Polynomials
  • Planar Graphs
  • Matching Polynomials
  • Oriented Graphs
  • Graphic Partitions
• Codes and Designs
  • Linear Codes
  • Decoding Algorithms
  • Latin Squares
  • Balanced Incomplete Block Designs
• Appendices
• Bibliography
• Hints and Answers to Selected Odd-Numbered Exercises
• Index of Notation
• Index