Introduction to Combinatorics E-Book

Martin J. Erickson

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Sprache: Englisch

Seitenzahl: 375

Veröffentlichungsjahr: 2013

Beschreibung

Praise for the First Edition

“This excellent text should prove a useful accoutrement for any developing mathematics program . . . it’s short, it’s sweet, it’s beautifully written.” —The Mathematical Intelligencer

“Erickson has prepared an exemplary work . . . strongly recommended for inclusion in undergraduate-level library collections.” —Choice

Featuring a modern approach, Introduction to Combinatorics, Second Edition illustrates the applicability of combinatorial methods and discusses topics that are not typically addressed in literature, such as Alcuin’s sequence, Rook paths, and Leech’s lattice. The book also presents fundamental results, discusses interconnection and problem-solving techniques, and collects and disseminates open problems that raise questions and observations.

Many important combinatorial methods are revisited and repeated several times throughout the book in exercises, examples, theorems, and proofs alike, allowing readers to build confidence and reinforce their understanding of complex material. In addition, the author successfully guides readers step-by-step through three major achievements of combinatorics: Van der Waerden’s theorem on arithmetic progressions, Pólya’s graph enumeration formula, and Leech’s 24-dimensional lattice.  Along with updated tables and references that reflect recent advances in various areas, such as error-correcting codes and combinatorial designs, the Second Edition also features:

• Many new exercises to help readers understand and apply combinatorial techniques and ideas
• A deeper, investigative study of combinatorics through exercises requiring the use of computer programs
• Over fifty new examples, ranging in level from routine to advanced, that illustrate important combinatorial concepts
• Basic principles and theories in combinatorics as well as new and innovative results in the field

Introduction to Combinatorics, Second Edition is an ideal textbook for a one- or two-semester sequence in combinatorics, graph theory, and discrete mathematics at the upper-undergraduate level. The book is also an excellent reference for anyone interested in the various applications of elementary combinatorics.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Dedication

Preface

Chapter 1: Basic Counting Methods

1.1 The multiplication principle

1.2 Permutations

1.3 Combinations

1.4 Binomial coefficient identities

1.5 Distributions

1.6 The principle of inclusion and exclusion

1.7 Fibonacci numbers

1.8 Linear recurrence relations

1.9 Special recurrence relations

1.10 Counting and number theory

Notes

Chapter 2: Generating Functions

2.1 Rational generating functions

2.2 Special generating functions

2.3 Partition numbers

2.4 Labeled and unlabeled sets

2.5 Counting with symmetry

2.6 Cycle indexes

2.7 Pólya’s theorem

2.8 The number of graphs

2.9 Symmetries in domain and range

2.10 Asymmetric graphs

Notes

Chapter 3: The Pigeonhole Principle

3.1 The principle

3.2 The lattice point problem and SET®

3.3 Graphs

3.4 Colorings of the plane

3.5 Sequences and partial orders

3.6 Subsets

Notes

Chapter 4: Ramsey Theory

4.1 Ramsey’s theorem

4.2 Generalizations of Ramsey’s theorem

4.3 Ramsey numbers, bounds, and asymptotics

4.4 The probabilistic method

4.5 Schur’s theorem

4.6 Van der Waerden’s theorem

Notes

Chapter 5: Error-Correcting Codes

5.1 Binary codes

5.2 Perfect codes

5.3 Hamming codes

5.4 The Fano Configuration

Notes

Chapter 6: Combinatorial Designs

6.1 t-designs

6.2 Block designs

6.3 Projective planes

6.4 Latin squares

6.5 MOLS and OODs

6.6 Hadamard matrices

6.7 The Golay code and S(5, 8, 24)

6.8 Lattices and sphere packings

6.9 Leech’s lattice

Notes

Appendix A: Web Resources

Appendix B: Notation

Exercise Solutions

References

Index

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

BARTHÉLEMY AND GUÉNOCHE • 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: Vizing’s Theorem and Goldberg’s 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, [phone], fax [phone], 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, [phone], fax [phone], 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 [phone], outside the United States at [phone] or fax [phone].

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 Journal of Combinatorial Theory Series A and Series B; Journal of Graph Theory; Discrete Mathematics; Discrete Applied Mathematics; Annals of Discrete Mathematics; Annals of Combinatorics; Topics in Discrete Mathematics; SIAM Journal on Discrete Mathematics; Graphs and Combinatorics; Combinatorica; Ars Combinatoria; European Journal of Combinatorics A and B; Journal of Algebraic Combinatorics; Journal of Combinatorial Designs; Designs, Codes, and Cryptography; Journal of Combinatorial Mathematics and Combinatorial Computing; Combinatorics, Probability & Computing; Journal of Combinatorics, Information & System Sciences; Algorithms and Combinatorics; Random Structures & Algorithms; Bulletin of the Institute of Combinatorics and Its Applications; Journal of Integer Sequences; Geombinatorics; Online Journal of Analytic Combinatorics; and The Electronic Journal of Combinatorics. These journal titles indicate the connections between discrete mathematics and computing, information theory and codes, and probability. Indeed, it is now desirable for all mathematicians, statisticians, and computer scientists to be acquainted with the basic principles of discrete mathematics.

The format of this book is designed to gradually and systematically introduce the main concepts of combinatorics. In this way, the reader is brought step-by-step from first principles to major accomplishments, always pausing to note mathematical points of interest along the way. I have made it a point to discuss some topics that don’t receive much treatment in other books on combinatorics, such as Alcuin’s sequence, Rook walks, and Leech’s lattice. In order to illustrate the applicability of combinatorial methods, I have paid careful attention to the selection of exercises at the end of each section. The reader should definitely attempt the exercises, as a good deal of the subject is revealed there. The problems range in difficulty from very easy to very challenging. Solutions to selected exercises are provided in the back of the book.

I wish to thank the people who have kindly made suggestions concerning this book: Mansur Boase, Robert Cacioppo, Duane DeTemple, Shalom Eliahou, Robert Dobrow, Suren Fernando, Joe Hemmeter, Daniel Jordan, Elizabeth Oliver, Ken Price, Adrienne Stanley, and Khang Tran.

I also gratefully acknowledge the Wiley staff for their assistance in publishing this book: Liz Belmont, Kellsee Chu, Sari Friedman, Danielle LaCourciere, Jacqueline Palmieri, Susanne Steitz-Filler, and Stephen Quigley.

CHAPTER 1

BASIC COUNTING METHODS

We begin our tour of combinatorics by investigating elementary methods for counting finite sets. How many ways are there to choose a subset of a set? How many permutations of a set are there? We will explore these and other such questions.

1.1 The multiplication principle

We start with the simplest counting problems. Many of these problems are concerned with the number of ways in which certain choices can occur.

Here is a useful counting principle: If one choice can be made in x ways and another choice in y ways, and the two choices are independent, then the two choices together can be made in xy ways. This rule is called the “multiplication principle.”

EXAMPLE 1.1

Suppose that you have three hats and four scarves. How many different hat and scarf outfits can you choose?

EXAMPLE 1.2

At the French restaurant Chacun à Son Got, there are three choices for the appetizer, four choices for the entrée, and five choices for the dessert. How many different dinner orders (consisting of appetizer, entrée, and dessert) can we make?

EXAMPLE 1.3

A variable name in a certain computer programming language consists of a letter (A through Z), a letter followed by another letter, or a letter followed by a digit (0 through 9). How many different variable names are possible?

Solution: There are 26 variable names consisting of a single letter, 262 variable names consisting of two letters, and 26 · 10 variable names consisting of a letter followed by a digit. Altogether, there are

variable names.

EXAMPLE 1.4 Number of binary strings

How many binary strings of length n are there?

Solution: There are two choices (0 or 1) for each element in the string. Hence, there are 2n possible strings.

EXAMPLE 1.5 Number of subsets of a set

Let S be a set of n elements. How many subsets does S have?

Solution: There are two choices for each element of S; it can be in the subset or not in the subset. This means that there are 2 subsets altogether.