Introductory Combinatorics

by Brualdi, Richard A.

• ISBN13: 9780136020400
• ISBN10: 0136020402
• Edition: 5th
• Format: Hardcover
• Copyright: 2008-12-28
• Publisher: Pearson

Summary

This trusted best-seller emphasizes combinatorial ideasincluding the pigeon-hole principle, counting techniques, permutations and combinations, Poacute;lya counting, binomial coefficients, inclusion-exclusion principle, generating functions and recurrence relations, combinatortial structures (matchings, designs, graphs), and flows in networks. The Fifth Edition clarifies the exposition throughout and adds a wealth of new exercises.Appropriate for one- or two-semester, junior- to senior-level combinatorics courses.

Author Biography

Richard A. Brualdi is Bascom Professor of Mathematics, Emeritus at the University of Wisconsin-Madison. He served as Chair of the Department of Mathematics from 1993-1999. His research interests lie in matrix theory and combinatorics/graph theory. Professor Brualdi is the author or co-author of six books, and has published extensively. He is one of the editors-in-chief of the journal "Linear Algebra and its Applications" and of the journal "Electronic Journal of Combinatorics." He is a member of the American Mathematical Society, the Mathematical Association of America, the International Linear Algebra Society, and the Institute for Combinatorics and its Applications. He is also a Fellow of the Society for Industrial and Applied Mathematics.

Table of Contents

What is Combinatorics?

Example: Perfect Covers of Chessboards

Example: Magic Squares

Example: The Four-Color Problem

Example: The Problem of the 36 Officers

Example: Shortest-Route Problem

Example: Mutually Overlapping Circles

Example: The Game of Nim

The Pigeonhole Principle

Pigeonhole Principle: Simple Form

Pigeonhole Principle: Strong Form

A Theorem of Ramsay

Permutations and Combinations

Four Basic Counting Principles

Permutations of Sets

Combinations of Sets

Permutations of Multisets

Combinations of Multisets

Finite Probability

Generating Permutations and Combinations

Generating Permutations

Inversions in Permutations

Generating Combinations

Generating r-Combinations

Partial Orders and Equivalence Relations

The Binomial Coefficients

Pascal's Formula

The Binomial Theorem

Unimodality of Binomial Coefficients

The Multinomial Theorem

Newton's Binomial Theorem

More on Partially Ordered Sets

The Inclusion-Exclusion Principle and Applications

The Inclusion-Exclusion Principle

Combinations with Repetition

Derangements

Permutations with Forbidden Positions

Another Forbidden Position Problem

Möbius Inversion

Recurrence Relations and Generating Functions

Some Number Sequences

Generating Functions

Exponential Generating Functions

Solving Linear Homogeneous Recurrence Relations

Nonhomogeneous Recurrence Relations

A Geometry Example

Special Counting Sequences

Catalan Numbers

Difference Sequences and Stirling Numbers

Partition Numbers

A Geometric Problem

Lattice Paths and Schröder Numbers

Systems of Distinct Representatives

General Problem Formulation

Existence of SDRs

Stable Marriages

Combinatorial Designs

Modular Arithmetic

Block Designs

Steiner Triple Systems

Latin Squares

Introduction to Graph Theory

Basic Properties

Eulerian Trails

Hamilton Paths and Cycles

Bipartite Multigraphs

Trees

The Shannon Switching Game

More on Trees

More on Graph Theory

Chromatic Number

Plane and Planar Graphs

A 5-color Theorem

Independence Number and Clique Number

Matching Number

Connectivity

Digraphs and Networks

Digraphs

Networks

Matching in Bipartite Graphs Revisited

Pólya Counting

Permutation and Symmetry Groups

Burnside's Theorem

Pólya's Counting formula

Table of Contents provided by Publisher. All Rights Reserved.