Discrete Mathematics with Combinatorics (2nd Edition) [Hardcover]

James A. Anderson (Author)

Book Description

Publication Date: August 29, 2003 | ISBN-10: 0130457914 | ISBN-13: 978-0130457912 | Edition: 2

For one-/two- semester, freshman courses in Discrete Mathematics. This carefully organized, very readable text covers every essential topic in discrete mathematics in a logical fashion. Placing each topic in context, it covers concepts associated with discrete mathematical systems that have applications in computer science, engineering, and mathematics. The author introduces more basic concepts at the freshman level than are found in other texts, in a simple, accessible form. Introductory material is balanced with extensive coverage of graphs, trees, recursion, algebra, theory of computing, and combinatorics. Extensive examples throughout the text reinforce concepts.

Editorial Reviews

From the Inside Flap

Preface

While there are many discrete mathematics books on the market, none of the available books covers the desired range and depth of topics in discrete mathematics in this book and also works in a theme on how to do proofs. Proofs are introduced in the first chapter and continued throughout the book. Most students taking discrete mathematics are mathematics and computer science majors. While the necessity of learning to do proofs is obvious for mathematics majors, it is also critical for computer science students to think logically. Essentially a logical bug-free computer program is equivalent to a logical proof. Also it is assumed in this book that it is easier to use (or at least not misuse) an application if one understands why it works. With few exceptions, the book is self-contained. Concepts are developed mathematically before they are seen in an applied context.

Calculus is not required for any of the material in this book. College algebra is adequate for the basic chapters. However, although this book is self-contained, some of the remaining chapters require more mathematical maturity than the basic chapters.

This book is intended for either a one- or two-term course in discrete mathematics. The first eight chapters of this book provide a solid foundation in discrete mathematics and would be appropriate for a first-level course at the freshman or sophomore level. These chapters are essentially independent so that the instructor can pick the material he wishes to cover. The remainder of the book contains appropriate material for a second course in discrete mathematics. These chapters expand concepts introduced earlier and introduce numerous advanced topics. Topics are explored from different points of view to show how they may be used in different settings. The range of topics includes

Logic—Including truth tables, propositional logic, predicate calculus, circuits, induction, and proofs.

Set Theory—Including cardinality of sets, relations, partially ordered sets, congruence relations, graphs, directed graphs and functions.

Algorithms—Including complexity of algorithms, search and sort algorithms, the Euclidean algorithm, Huffman's algorithm, Prim's algorithms, Warshall's algorithm, the Ford-Fulkerson algorithm, the Floyd-Warshall algorithm, and Dijkstra's algorithms.

Graph Theory—Including directed graphs, Euler cycles and paths, Hamiltonian cycles and paths, planar graphs, and weighted graphs.

Tree—Including binary search trees, weighted trees, tree transversal, Huffman's codes, and spanning trees.

Combinatorics—Including permutations, combinations, inclusion-exclusion, partitions, generating functions, Catalan numbers, Sterling numbers, Rook polynomials, derangements, and enumeration of colors.

Algebra—Including semigroups, groups, lattices, semilattices, Boolean algebras, rings, fields, integral domains, polynomials, and matrices.

There is extensive number theory and algebra in this book. I feel that this is a strength of this text, but realize that others may not want to cover these subjects. The chapters in these areas are completely independent of the remainder of the book and can be covered or not as the instructor desires. This book also contains probability, finite differences, and other topics not usually found in a discrete mathematics text. ORGANIZATION

The first three chapters cover logic and set theory. It is assumed in this book that an understanding of proofs is necessary for the logical construction of advanced computer programs.

The basic concepts of a proof are given and illustrated with numerous examples. In Chapter 2, the student is given the opportunity to prove some elementary concepts of set theory. In Chapter 3, the concept of an axiom system for number theory is introduced. The student is given the opportunity to prove theorems in a familiar environment. Proofs using induction are also introduced in this chapter. Throughout the remainder of the book, many proofs are presented and many of the problems are devoted to proofs. Problems, including proofs, begin at the elementary level and continually become more advanced throughout the book.

Relations and graphs are introduced in Chapter 2. Relations lead naturally into functions, which are introduced in Chapter 4. However, the development of functions in Chapter 4 is independent of the material in Chapter 2. Similarly the development of graphs in Chapter 6 does not depend on their development as relations in Chapter 2.

Matrices, permutations, and sequences are introduced in Chapter 4 as special types of functions. Further properties of functions and matrices follow in Chapter 6. Algorithms for matrices are introduced and further properties of matrices are developed, which will be used in later chapters on algebra, counting, and theory of codes.

Permutations are used for counting in Chapter 8 and also for applications in algebra and combinatorics in later chapters. Again the material in Chapter 8, while related to Chapter 4, can be studied independently.

Chapter 5 is independent of the previous chapters except for the matrices in the previous chapter. Algorithms are developed including sorting algorithms. The complexity of algorithms is also developed in this chapter. Prefix and suffix notation are introduced here. They are again discussed in Chapter 15 with regard to traversing binary trees. Binary and hexadecimal numbers are also introduced in this chapter.

Many elementary concepts of graphs, directed graphs, and trees are covered in Chapter 6. These concepts are covered in more depth in Chapters 14-16. Chapter 6 is independent of the previous chapters.

In Chapters 7 and 9 the basics of number theory are developed. These chapters are necessary for applications of number theory in Chapter 23 but are otherwise completely independent of the other chapters and may be omitted if desired.

Chapter 8 is the beginning of extensive coverage of combinatorics. This is continued in many of the chapters including Chapters 12, 13, and 17. Chapter 8 also covers probability, which is not common in most other discrete mathematics books.

Chapters 9 and 20 cover the basic concepts of algebra including semigroups, groups rings, semilattices, lattices, rings, integral domains, and fields. These chapters use Sections 3.6 and 4.3 for examples of groups and rings. Chapter 9 is necessary for the applications in Chapters 17-21.

In many ways Chapters 11, 12, and 13 form a package. Recursion is continued in Chapter 11. In addition to the standard linear recurrence relations normally covered in a discrete mathematics text, the theory of finite difference is also covered. Chapter 6 should be covered before this chapter unless the student already has some knowledge of recursion. Chapter 12 continues the counting introduced in Chapter 8. It covers topics introduced in Chapter 8 such as occupancy problems and inclusion-exclusion. It also introduces derangements and rook polynomials. It is closely related to Chapter 11. Many of the same topics are covered from different points of view. One example of this is Stirling numbers. However neither chapter is dependent on the other.

Chapters 11 and 12 are tied together in Chapter 13, where generating functions are used to continue the material in both chapters. In particular, generating functions provide a powerful tool for the solution of occupancy problems.

Chapters 14-16 continue the study of trees and graphs begun in Chapter 6. They obviously depend on the material in Chapter 6, but are virtually independent of most of the preceding chapters. One exception is the use of matrices in some of the algorithms. Many of the standard topics of Graphs and Trees are covered including planar graphs, Hamiltonian cycles, binary trees, spanning trees, minimal spanning trees, weighted trees, shortest path algorithms, and network flows.

Chapters 17-23 form another cluster consisting of number theory, algebra, combinatorics and their application. The theory of computation is introduced in Chapter 17. This includes codes, regular languages, automata, grammars and their relationship. This chapter uses semigroups from Section 9.2. Chapter 18 introduces special codes such as error detecting codes and error correcting codes. This chapter requires knowledge of group theory, found in Section 9.4 and a knowledge of matrices, found in Chapters 4 and 5. Codes are explored from yet another direction in Chapter 23 where cryptography is introduced. This chapter is dependent on the previous chapters on number theory.

In Chapter 19, algebra and combinatorics are combined for the development of Burnside's Theorem and Polya's Theorem for the enumeration of colors. It primarily depends on a knowledge of permutations found in Section 9.4

Chapter 21 is a simple application of groups and semigroups and their mapping onto the complex plane. The prerequisites for this chapter are Sections 9.2 and 9.4.

Chapter 22 gives three important applications of number theory. The study of Hashing functions and cryptography is particularly relevant to computer science.

When teaching a beginning course, I normally cover Chapters 1-5 in their entirety, Sections 8.1-8.3 and try to cover the first three sections of Chapter 6. As mentioned previously, the material in the first eight chapters is arranged for maximal flexibility. SUPPLEMENTS

A solutions manual is available from the publisher with complete solutions to all problems. A website is available at prenhall/janderson. This website includes links to other interesting sites in discrete mathematics, quizzes, and additional problems. ACKNOWLEDGMENTS

First I would like to thank George Lobell for his leadership in the development of this book and Barbara Mack for coordinating our efforts. I would like to thank Kristin and Philip Musik for their excellent artwork. I am especially grateful to James Bell for the tremendous amount of work that he has contributed. I am sorry that he was unable to co-author this book with me. I miss having him as a partner. I would also like to thank my colleagues Dan Cooke, Ed Wilde, Rick Chow, M. B. Ulmer, and Jerome Lewis for their help. I would like to thank Soledad Sugai for the errors she found while a student in my course. I would also like to thank students Jody Dean, Jessica Dones, Grace Ellison, Vinny Chin Fai Ip, Priscilla Lapierre, Esther Ly, Badral Madani, Julie Norris, Tracy Quin and Robert Wiegert, who survived the first voyage through this material.

Please feel free to e-mail me with comments and suggestions for future improvements.

James A. Anderson
[e-mail] --This text refers to an out of print or unavailable edition of this title.

From the Back Cover

This carefully organized, very readable book covers every essential topic in discrete mathematics in a logical fashion. Placing each topic in context, it covers concepts associated with discrete mathematical systems that have applications in computer science, engineering, and mathematics. The author introduces more basic concepts at the freshman level than are found in other books, in a simple, accessible form. Introductory material is balanced with extensive coverage of graphs, trees, recursion, algebra, theory of computing, and combinatorics. Extensive examples throughout the text reinforce concepts. More combinatorics/algebraic structures than in most books. Detailed discussion of and strong emphasis on proofs. Extensive, in-depth presentation of topics. Large selection of applied and computational problems, ranging from the elementary to the more advanced. More topics in probability and more statistical interpretations than other texts. Comprehensive discussion of topics such as finite state machines, automata, and languages. Earlier introduction of matrices and relations, Boolean algebras and circuits than most texts. Includes algorithms for many constructive tasks that occur in discrete systems. --This text refers to an out of print or unavailable edition of this title.

See all Editorial Reviews

Product Details

• Hardcover: 928 pages
• Publisher: Prentice Hall; 2 edition (August 29, 2003)
• Language: English
• ISBN-10: 0130457914
• ISBN-13: 978-0130457912
• Product Dimensions: 10.1 x 8.3 x 1.3 inches
• Shipping Weight: 4.2 pounds
• Average Customer Review: 4.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #871,169 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

5.0 out of 5 stars It is high on my list of potential textbooks for a course in discrete math, July 29, 2008

By 

Charles Ashbacher (Marion, Iowa United States) - See all my reviews
(TOP 500 REVIEWER)    (VINE VOICE)    (HALL OF FAME REVIEWER)   

This review is from: Discrete Mathematics with Combinatorics (2nd Edition) (Hardcover)

I occasionally teach discrete mathematics at the college level and so I am always trolling in a search for a better textbook. That is the context within which I examined this book. The coverage of the basic topics is exactly the way I prefer in both order and content. The initial chapters are:

*) Truth tables, logic and proofs
*) Set theory
*) Logic, integers and proofs
*) Functions and matrices

I would never use a book that did not cover logic, set theory, relations and functions in that order.
The remaining topics in the order they appear are:

*) Algorithms and recursion
*) Graphs, directed graphs and trees
*) Number theory
*) Counting and probability
*) Algebraic structures
*) Number theory revisited
*) Recursion revisited
*) Counting continued
*) Generating functions
*) Graphs revisited
*) Trees
*) Networks
*) Theory of computation
*) Theory of codes
*) Enumeration of colors
*) Rings, integral domains and fields
*) Group and semigroup characters
*) Applications of number theory

As can be seen from this list, there is much more material here than can be covered in a one-semester course. However, the sections are independent enough that selection can be done. For example, the "revisited" chapters could be skipped. This revisiting means that the depth of coverage is there if you have need of it. A large number of exercises are included at the end of the chapters and solutions to many of them are included.
I do not know if and when I will teach discrete math again. If that situation does arise again, I will give this book strong consideration as the choice of text.

3 of 6 people found the following review helpful:

3.0 out of 5 stars A pretty good book, November 9, 2000

By 

"goatsrue" (Goodwell, OK) - See all my reviews

This review is from: Discrete Mathematics with Combinatorics (Hardcover)

While the table of contents is very good, too much time is wasted in developing preliminaries. The text should quickly move into the core of the subject, but instead spends 220 pages developing the elementary material. A good reference for teachers of discrete mathematics with emphasis in combinatorics and not in computer science.