Martin J. Erickson - Introduction to Combinatorics

Introduction to Combinatorics

WILEY SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION

AARTS AND KORST Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing

AARTS AND LENSTRA Local Search in Combinatorial Optimization

ALON AND SPENCER The Probabilistic Method, Third Edition

ANDERSON AND NASH Linear Programming in Infinite-Dimensional Spaces: Theory and Application

ARLINGHAUS, ARLINGHAUS, AND HARARY Graph Theory and Geography: An Interactive View E-Book

AZENCOTT Simulated Annealing: Parallelization Techniques

BARTHLEMY AND GUNOCHE Trees and Proximity Representations

BAZARRA, JARVIS, AND SHERALI Linear Programming and Network Flows

BRUEN AND FORCINITO Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century

CHANDRU AND HOOKER Optimization Methods for Logical Inference

CHONG AND ZAK An Introduction to Optimization, Fourth Edition

COFFMAN AND LUEKER Probabilistic Analysis of Packing and Partitioning Algorithms

COOK, CUNNINGHAM, PULLEYBLANK, AND SCHRIJVER Combinatorial Optimization

DASKIN Network and Discrete Location: Modes, Algorithms and Applications

DINITZ AND STINSON Contemporary Design Theory: A Collection of Surveys

DU AND KO Theory of Computational Complexity

ERICKSON Introduction to Combinatorics, Second Edition

GLOVER, KLINGHAM, AND PHILLIPS Network Models in Optimization and Their Practical Problems

GOLSHTEIN AND TRETYAKOV Modified Lagrangians and Monotone Maps in Optimization

GONDRAN AND MINOUX Graphs and Algorithms (Translated by S. Vajd)

GRAHAM, ROTHSCHILD, AND SPENCER Ramsey Theory, Second Edition

GROSS AND TUCKER Topological Graph Theory

HALL Combinatorial Theory, Second Edition

HOOKER Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction

IMRICH AND KLAVAR Product Graphs: Structure and Recognition

JANSON, LUCZAK, AND RUCINSKI Random Graphs

JENSEN AND TOFT Graph Coloring Problems

KAPLAN Maxima and Minima with Applications: Practical Optimization and Duality

LAWLER, LENSTRA, RINNOOY KAN, AND SHMOYS, Editors The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization

LAYWINE AND MULLEN Discrete Mathematics Using Latin Squares

LEVITIN Perturbation Theory in Mathematical Programming Applications

MAHMOUD Evolution of Random Search Trees

MAHMOUD Sorting: A Distribution Theory

MARTELLI Introduction to Discrete Dynamical Systems and Chaos

MARTELLO AND TOTH Knapsack Problems: Algorithms and Computer Implementations

McALOON AND TRETKOFF Optimization and Computational Logic

MERRIS Combinatorics, Second Edition

MERRIS Graph Theory

MINC Nonnegative Matrices

MINOUX Mathematical Programming: Theory and Algorithms (Translated by S. Vajd)

MIRCHANDANI AND FRANCIS, Editors Discrete Location Theory

NEMHAUSER AND WOLSEY Integer and Combinatorial Optimization

NEMIROVSKY AND YUDIN Problem Complexity and Method Efficiency in Optimization (Translated by E. R. Dawson)

PACH AND AGARWAL Combinatorial Geometry

PLESS Introduction to the Theory of Error-Correcting Codes, Third Edition

ROOS AND VIAL Ph. Theory and Algorithms for Linear Optimization: An Interior Point Approach

SCHEINERMAN AND ULLMAN Fractional Graph Theory: A Rational Approach to the Theory of Graphs

SCHIFF Cellular Automata: A Discrete View of the World

SCHRIJVER Theory of Linear and Integer Programming

SPALL Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control

STIEBITZ, SCHEIDE, TOFT, AND FAVRHOLDT Graph Edge Coloring: Vizings Theorem and Goldbergs Conjecture

SZPANKOWSKI Average Case Analysis of Algorithms on Sequences

TOMESCU Problems in Combinatorics and Graph Theory (Translated by R. A. Melter)

TUCKER Applied Combinatorics, Second Edition

WOLSEY Integer Programming

YE Interior Point Algorithms: Theory and Analysis

Copyright 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com . Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission .

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com .

Library of Congress Cataloging-in-Publication Data is now available.

ISBN 978-1-118-63753-1

To my parents, Robert and Lorene

PREFACE

This book is an update and revision of my earlier textbook of the same title. The most important change is an increase in the number of worked examples and solved exercises. Also, several new topics have been introduced. But the overall plan of the book is the same as in the first edition: to introduce the reader to the basic elements of combinatorics, along with many examples and exercises.

Combinatorics may be described as the study of how discrete structures can be counted, arranged, and constructed. Accordingly, this book is an introduction to the three main branches of combinatorics: enumeration, existence, and construction. There are two chapters devoted to each of these three areas.

Combinatorics plays a central role in mathematics. One has only to look at the numerous journal titles in combinatorics and discrete mathematics to see that this area is huge! Some of the journal titles are