eBook ISBN:  9781614446071 
Product Code:  TEXT/17.E 
List Price:  $69.00 
MAA Member Price:  $51.75 
AMS Member Price:  $51.75 
eBook ISBN:  9781614446071 
Product Code:  TEXT/17.E 
List Price:  $69.00 
MAA Member Price:  $51.75 
AMS Member Price:  $51.75 

Book DetailsAMS/MAA TextbooksVolume: 17; 2010; 391 pp
Reprinted edition available: TEXT/55
Combinatorics is mathematics of enumeration, existence, construction, and optimization questions concerning finite sets. This text focuses on the first three types of questions and covers basic counting and existence principles, distributions, generating functions, recurrence relations, Pólya theory, combinatorial designs, error correcting codes, partially ordered sets, and selected applications to graph theory including the enumeration of trees, the chromatic polynomial, and introductory Ramsey theory. The only prerequisites are singlevariable calculus and familiarity with sets and basic proof techniques.
The text emphasizes the brands of thinking that are characteristic of combinatorics: bijective and combinatorial proofs, recursive analysis, and counting problem classification. It is flexible enough to be used for undergraduate courses in combinatorics, second courses in discrete mathematics, introductory graduate courses in applied mathematics programs, as well as for independent study or reading courses. What makes this text a guided tour are the approximately 350 reading questions spread throughout its eight chapters. These questions provide checkpoints for learning and prepare the reader for the endofsection exercises of which there are over 470. Most sections conclude with Travel Notes that add color to the material of the section via anecdotes, open problems, suggestions for further reading, and biographical information about mathematicians involved in the discoveries.

Table of Contents

cover

copyright page

title page

Preface

Before you go

1 Principles of Combinatorics

1.1 Typical counting questions and the product principle

1.2 Counting, overcounting, and the sum principle

1.3 Functions and the bijection principle

1.4 Relations and the equivalence principle

1.5 Existence and the pigeonhole principle

2 Distributions and Combinatorial Proofs

2.1 Counting functions

2.2 Counting subsets and multisets

2.3 Counting set partitions

2.4 Counting integer partitions

3 Algebraic Tools

3.1 Inclusionexclusion

3.2 Mathematical induction

3.3 Using generating functions, part I

3.4 Using generating functions, part II

3.5 Techniques for solving recurrence relations

3.6 Solving linear recurrence relations

4 Famous Number Families

4.1 Binomial and multinomial coefficients

4.2 Fibonacci and Lucas numbers

4.3 Stirling numbers

4.4 Integer partition numbers

5 Counting Under Equivalence

5.1 Two examples

5.2 Permutation groups

5.3 Orbits and fixed point sets

5.4 Using the CFB theorem

5.5 Proving the CFB theorem

5.6 The cycle index and Pólya’s theorem

6 Combinatorics on Graphs

6.1 Basic graph theory

6.2 Counting trees

6.3 Coloring and the chromatic polynomial

6.4 Ramsey theory

7 Designs and Codes

7.1 Construction methods for designs

7.2 The incidence matrix and symmetric designs

7.3 Fisher’s inequality and Steiner systems

7.4 Perfect binary codes

7.5 Codes from designs, designs from codes

8 Partially Ordered Sets

8.1 Poset examples and vocabulary

8.2 Isomorphism and Sperner’s theorem

8.3 Dilworth’s theorem

8.4 Dimension

8.5 Möbius inversion, part I

8.6 Möbius inversion, part II

Bibliography

Hints and Answers to Selected Exercises

Section 1.1

Section 1.2

Section 1.3

Section 1.4

Section 1.5

Section 2.1

Section 2.2

Section 2.3

Section 2.4

Section 3.1

Section 3.2

Section 3.3

Section 3.4

Section 3.5

Section 3.6

Section 4.1

Section 4.2

Section 4.3

Section 4.4

Section 5.2

Section 5.3

Section 5.4

Section 5.6

Section 6.1

Section 6.2

Section 6.3

Section 6.4

Section 7.1

Section 7.2

Section 7.3

Section 7.4

Section 7.5

Section 8.1

Section 8.2

Section 8.3

Section 8.4

Section 8.5

Section 8.6

List of Notation

Index

About the Author


Additional Material

Reviews

This is a wellwritten, readerfriendly, and selfcontained undergraduate course on combinatorics, focusing on enumeration. The book includes plenty of exercises, and about half of them come with hints.
M. Bona, Choice Magazine 
... The delineation of the topics is first rate—better than I have ever seen in any other book. ... CAGT has both good breadth and great presentation; it is in fact a new standard in presentation for combinatorics, essential as a resource for any instructor, including those teaching out of a different text. For the student: If you are just starting to build a library in combinatorics, this should be your first book.
The UMAP Journal 
... [This book] is an excellent candidate for a special topics course for mathematics majors; with the broad spectrum of applications that course can simultaneously be an advanced and a capstone course. This book would be an excellent selection for the textbook of such a course. ... This book is the best candidate for a textbook in combinatorics that I have encountered.
Charles Ashbacher


RequestsReview Copy – for publishers of book reviewsDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a courseAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
Reprinted edition available: TEXT/55
Combinatorics is mathematics of enumeration, existence, construction, and optimization questions concerning finite sets. This text focuses on the first three types of questions and covers basic counting and existence principles, distributions, generating functions, recurrence relations, Pólya theory, combinatorial designs, error correcting codes, partially ordered sets, and selected applications to graph theory including the enumeration of trees, the chromatic polynomial, and introductory Ramsey theory. The only prerequisites are singlevariable calculus and familiarity with sets and basic proof techniques.
The text emphasizes the brands of thinking that are characteristic of combinatorics: bijective and combinatorial proofs, recursive analysis, and counting problem classification. It is flexible enough to be used for undergraduate courses in combinatorics, second courses in discrete mathematics, introductory graduate courses in applied mathematics programs, as well as for independent study or reading courses. What makes this text a guided tour are the approximately 350 reading questions spread throughout its eight chapters. These questions provide checkpoints for learning and prepare the reader for the endofsection exercises of which there are over 470. Most sections conclude with Travel Notes that add color to the material of the section via anecdotes, open problems, suggestions for further reading, and biographical information about mathematicians involved in the discoveries.

cover

copyright page

title page

Preface

Before you go

1 Principles of Combinatorics

1.1 Typical counting questions and the product principle

1.2 Counting, overcounting, and the sum principle

1.3 Functions and the bijection principle

1.4 Relations and the equivalence principle

1.5 Existence and the pigeonhole principle

2 Distributions and Combinatorial Proofs

2.1 Counting functions

2.2 Counting subsets and multisets

2.3 Counting set partitions

2.4 Counting integer partitions

3 Algebraic Tools

3.1 Inclusionexclusion

3.2 Mathematical induction

3.3 Using generating functions, part I

3.4 Using generating functions, part II

3.5 Techniques for solving recurrence relations

3.6 Solving linear recurrence relations

4 Famous Number Families

4.1 Binomial and multinomial coefficients

4.2 Fibonacci and Lucas numbers

4.3 Stirling numbers

4.4 Integer partition numbers

5 Counting Under Equivalence

5.1 Two examples

5.2 Permutation groups

5.3 Orbits and fixed point sets

5.4 Using the CFB theorem

5.5 Proving the CFB theorem

5.6 The cycle index and Pólya’s theorem

6 Combinatorics on Graphs

6.1 Basic graph theory

6.2 Counting trees

6.3 Coloring and the chromatic polynomial

6.4 Ramsey theory

7 Designs and Codes

7.1 Construction methods for designs

7.2 The incidence matrix and symmetric designs

7.3 Fisher’s inequality and Steiner systems

7.4 Perfect binary codes

7.5 Codes from designs, designs from codes

8 Partially Ordered Sets

8.1 Poset examples and vocabulary

8.2 Isomorphism and Sperner’s theorem

8.3 Dilworth’s theorem

8.4 Dimension

8.5 Möbius inversion, part I

8.6 Möbius inversion, part II

Bibliography

Hints and Answers to Selected Exercises

Section 1.1

Section 1.2

Section 1.3

Section 1.4

Section 1.5

Section 2.1

Section 2.2

Section 2.3

Section 2.4

Section 3.1

Section 3.2

Section 3.3

Section 3.4

Section 3.5

Section 3.6

Section 4.1

Section 4.2

Section 4.3

Section 4.4

Section 5.2

Section 5.3

Section 5.4

Section 5.6

Section 6.1

Section 6.2

Section 6.3

Section 6.4

Section 7.1

Section 7.2

Section 7.3

Section 7.4

Section 7.5

Section 8.1

Section 8.2

Section 8.3

Section 8.4

Section 8.5

Section 8.6

List of Notation

Index

About the Author

This is a wellwritten, readerfriendly, and selfcontained undergraduate course on combinatorics, focusing on enumeration. The book includes plenty of exercises, and about half of them come with hints.
M. Bona, Choice Magazine 
... The delineation of the topics is first rate—better than I have ever seen in any other book. ... CAGT has both good breadth and great presentation; it is in fact a new standard in presentation for combinatorics, essential as a resource for any instructor, including those teaching out of a different text. For the student: If you are just starting to build a library in combinatorics, this should be your first book.
The UMAP Journal 
... [This book] is an excellent candidate for a special topics course for mathematics majors; with the broad spectrum of applications that course can simultaneously be an advanced and a capstone course. This book would be an excellent selection for the textbook of such a course. ... This book is the best candidate for a textbook in combinatorics that I have encountered.
Charles Ashbacher