SoftcoverISBN:  9781470470630 
Product Code:  DISCMAT.S 
List Price:  $69.00 
MAA Member Price:  $62.10 
AMS Member Price:  $55.20 
eBookISBN:  9781470411381 
Product Code:  DISCMAT.E 
List Price:  $65.00 
MAA Member Price:  $58.50 
AMS Member Price:  $52.00 
SoftcoverISBN:  9781470470630 
eBookISBN:  9781470411381 
Product Code:  DISCMAT.S.B 
List Price:  $134.00$101.50 
MAA Member Price:  $120.60$91.35 
AMS Member Price:  $107.20$81.20 
Softcover ISBN:  9781470470630 
Product Code:  DISCMAT.S 
List Price:  $69.00 
MAA Member Price:  $62.10 
AMS Member Price:  $55.20 
eBook ISBN:  9781470411381 
Product Code:  DISCMAT.E 
List Price:  $65.00 
MAA Member Price:  $58.50 
AMS Member Price:  $52.00 
Softcover ISBN:  9781470470630 
eBookISBN:  9781470411381 
Product Code:  DISCMAT.S.B 
List Price:  $134.00$101.50 
MAA Member Price:  $120.60$91.35 
AMS Member Price:  $107.20$81.20 

Book Details2007; 388 ppMSC: Primary 05; 06; 11; 90; 94;
The advent of fast computers and the search for efficient algorithms revolutionized combinatorics and brought about the field of discrete mathematics. This book is an introduction to the main ideas and results of discrete mathematics, and with its emphasis on algorithms it should be interesting to mathematicians and computer scientists alike. The book is organized into three parts: enumeration, graphs and algorithms, and algebraic systems. There are 600 exercises with hints and solutions to about half of them. The only prerequisites for understanding everything in the book are linear algebra and calculus at the undergraduate level.
Praise for the German edition…
This book is a wellwritten introduction to discrete mathematics and is highly recommended to every student of mathematics and computer science as well as to teachers of these topics.
—Konrad Engel for MathSciNet
Martin Aigner is a professor of mathematics at the Free University of Berlin. He received his PhD at the University of Vienna and has held a number of positions in the USA and Germany before moving to Berlin. He is the author of several books on discrete mathematics, graph theory, and the theory of search. The Monthly article Turan's graph theorem earned him a 1995 Lester R. Ford Prize of the MAA for expository writing, and his book Proofs from the BOOK with Günter M. Ziegler has been an international success with translations into 12 languages.ReadershipUndergraduates and graduate students interested in discrete mathematics, algorithms, and combinatorics.

Table of Contents

Cover

Title

Copyright

Contents

Prefaces

Part 1. Counting

Chapter 1. Fundamentals

§1.1. Elementary Counting Principles

§1.2. The Fundamental Counting Coefficients

§1.3. Permutations

§1.4. Recurrence Equations

§1.5. Discrete Probability

§1.6. Existence Theorems

Exercises for Chapter 1

Chapter 2. Summation

§2.1. Direct Methods

§2.2. The Calculus of Finite Differences

§2.3. Inversion

§2.4. InclusionExclusion

Exercises for Chapter 2

Chapter 3. Generating Functions

§3.1. Definitions and Examples

§3.2. Solving Recurrences

§3.3. Generating Functions of Exponential Type

Exercises for Chapter 3

Chapter 4. Counting Patterns

§4.1. Symmetries

§4.2. Statement of the Problem

§4.3. Patterns and the Cycle Indicator

§4.4. Polya's Theorem

Exercises for Chapter 4

Chapter 5. Asymptotic Analysis

§5.1. The Growth of Functions

§5.2. Order of Magnitude of Recurrence Relations

§5.3. Running Times of Algorithms

Exercises for Chapter 5

Bibliography for Part 1

Bibliography for Part 1

Part 2.Graphs and Algorithms

Chapter 6. Graphs

§6.1. Definitions and Examples

§6.2. Representation of Graphs

§6.3. Paths and Circuits

§6.4. Directed Graphs

Exercises for Chapter 6

Chapter 7. Trees

§7.1. What Is a Tree?

§7.2. Breadth First and DepthFirst Search

§7.3. Minimal Spanning Trees

§7.4. The Shortest Path in a Graph

Exercises for Chapter 7

Chapter 8. Matchings and Networks

§8.1. Matchings in Bipartite Graphs

§8.2. Construction of Optimal Matchings

§8.3. Flows in Networks

§8.4. Eulerian Graphs and the Traveling Salesman Problem

§8.5. The Complexity Classes P and NP

Exercises for Chapter 8

Chapter 9. Searching and Sorting

§9.1. Search Problems and Decision Trees

§9.2. The Fundamental Theorem of Search Theory

§9.3. Sorting Lists

§9.4. Binary Search Trees

Exercises for Chapter 9

Chapter 10. General Optimization Methods

§10.1. Backtracking

§10.2. Dynamic Programming

§10.3. The Greedy Algorithm

Exercises for Chapter 10

Bibliography for Part 2

Bibliography for Part 2

Part 3. Algebraic Systems

Chapter 11. Boolean Algebras

§11.1. Definition and Properties

§11.2. Propositional Logic and Boolean Functions

§11.3. Logical Nets

§11.4. Boolean Lattices, Orders, and Hypergraphs

Exercises for Chapter 11

Chapter 12. Modular Arithmetic

§12.1. Calculating with Congruences

§12.2. Finite Fields

§12.3. Latin Squares

§12.4. Combinatorial Designs

Exercises for Chapter 12

Chapter 13. Coding

§13.1. Statement of the Problem

§13.2. Source Encoding

§13.3. Error Detection and Correction

§13.4. Linear Codes

§13.5. Cyclic Codes

Exercises for Chapter 13

Chapter 14. Cryptography

§14.1. Cryptosystems

§14.2. Linear Shift Registers

§14.3. Public Key Cryptosystems

§14.4. ZeroKnowledge Protocols

Exercises for Chapter 14

Chapter 15. Linear Optimization

§15.1. Examples and Definitions

§15.2. Duality

§15.3. The Fundamental Theorem of Linear Optimization

§15.4. Admissible Solutions and Optimal Solutions

§15.5. The Simplex Algorithm

§15.6. Integer Linear Optimization

Exercises for Chapter 15

Bibliography for Part 3

Solutions to Selected Exercises

Index

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Back Cover


Additional Material

Reviews

Aigner offers a very enjoyable review of discrete mathematics at the graduate level.
Choice Reviews 
This book gives a leisurely and clear exposition of the main topics of discrete mathematics.
Allen Stenger for MAA Reviews


RequestsReview Copy – for reviewers who would like to review an AMS bookDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a coursePermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
The advent of fast computers and the search for efficient algorithms revolutionized combinatorics and brought about the field of discrete mathematics. This book is an introduction to the main ideas and results of discrete mathematics, and with its emphasis on algorithms it should be interesting to mathematicians and computer scientists alike. The book is organized into three parts: enumeration, graphs and algorithms, and algebraic systems. There are 600 exercises with hints and solutions to about half of them. The only prerequisites for understanding everything in the book are linear algebra and calculus at the undergraduate level.
Praise for the German edition…
This book is a wellwritten introduction to discrete mathematics and is highly recommended to every student of mathematics and computer science as well as to teachers of these topics.
—Konrad Engel for MathSciNet
Martin Aigner is a professor of mathematics at the Free University of Berlin. He received his PhD at the University of Vienna and has held a number of positions in the USA and Germany before moving to Berlin. He is the author of several books on discrete mathematics, graph theory, and the theory of search. The Monthly article Turan's graph theorem earned him a 1995 Lester R. Ford Prize of the MAA for expository writing, and his book Proofs from the BOOK with Günter M. Ziegler has been an international success with translations into 12 languages.
Undergraduates and graduate students interested in discrete mathematics, algorithms, and combinatorics.

Cover

Title

Copyright

Contents

Prefaces

Part 1. Counting

Chapter 1. Fundamentals

§1.1. Elementary Counting Principles

§1.2. The Fundamental Counting Coefficients

§1.3. Permutations

§1.4. Recurrence Equations

§1.5. Discrete Probability

§1.6. Existence Theorems

Exercises for Chapter 1

Chapter 2. Summation

§2.1. Direct Methods

§2.2. The Calculus of Finite Differences

§2.3. Inversion

§2.4. InclusionExclusion

Exercises for Chapter 2

Chapter 3. Generating Functions

§3.1. Definitions and Examples

§3.2. Solving Recurrences

§3.3. Generating Functions of Exponential Type

Exercises for Chapter 3

Chapter 4. Counting Patterns

§4.1. Symmetries

§4.2. Statement of the Problem

§4.3. Patterns and the Cycle Indicator

§4.4. Polya's Theorem

Exercises for Chapter 4

Chapter 5. Asymptotic Analysis

§5.1. The Growth of Functions

§5.2. Order of Magnitude of Recurrence Relations

§5.3. Running Times of Algorithms

Exercises for Chapter 5

Bibliography for Part 1

Bibliography for Part 1

Part 2.Graphs and Algorithms

Chapter 6. Graphs

§6.1. Definitions and Examples

§6.2. Representation of Graphs

§6.3. Paths and Circuits

§6.4. Directed Graphs

Exercises for Chapter 6

Chapter 7. Trees

§7.1. What Is a Tree?

§7.2. Breadth First and DepthFirst Search

§7.3. Minimal Spanning Trees

§7.4. The Shortest Path in a Graph

Exercises for Chapter 7

Chapter 8. Matchings and Networks

§8.1. Matchings in Bipartite Graphs

§8.2. Construction of Optimal Matchings

§8.3. Flows in Networks

§8.4. Eulerian Graphs and the Traveling Salesman Problem

§8.5. The Complexity Classes P and NP

Exercises for Chapter 8

Chapter 9. Searching and Sorting

§9.1. Search Problems and Decision Trees

§9.2. The Fundamental Theorem of Search Theory

§9.3. Sorting Lists

§9.4. Binary Search Trees

Exercises for Chapter 9

Chapter 10. General Optimization Methods

§10.1. Backtracking

§10.2. Dynamic Programming

§10.3. The Greedy Algorithm

Exercises for Chapter 10

Bibliography for Part 2

Bibliography for Part 2

Part 3. Algebraic Systems

Chapter 11. Boolean Algebras

§11.1. Definition and Properties

§11.2. Propositional Logic and Boolean Functions

§11.3. Logical Nets

§11.4. Boolean Lattices, Orders, and Hypergraphs

Exercises for Chapter 11

Chapter 12. Modular Arithmetic

§12.1. Calculating with Congruences

§12.2. Finite Fields

§12.3. Latin Squares

§12.4. Combinatorial Designs

Exercises for Chapter 12

Chapter 13. Coding

§13.1. Statement of the Problem

§13.2. Source Encoding

§13.3. Error Detection and Correction

§13.4. Linear Codes

§13.5. Cyclic Codes

Exercises for Chapter 13

Chapter 14. Cryptography

§14.1. Cryptosystems

§14.2. Linear Shift Registers

§14.3. Public Key Cryptosystems

§14.4. ZeroKnowledge Protocols

Exercises for Chapter 14

Chapter 15. Linear Optimization

§15.1. Examples and Definitions

§15.2. Duality

§15.3. The Fundamental Theorem of Linear Optimization

§15.4. Admissible Solutions and Optimal Solutions

§15.5. The Simplex Algorithm

§15.6. Integer Linear Optimization

Exercises for Chapter 15

Bibliography for Part 3

Solutions to Selected Exercises

Index

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Back Cover

Aigner offers a very enjoyable review of discrete mathematics at the graduate level.
Choice Reviews 
This book gives a leisurely and clear exposition of the main topics of discrete mathematics.
Allen Stenger for MAA Reviews