Win $250 in textbooks! Enter now >
Discrete and Combinatorial Mathematics : An Applied Introduction

Discrete and Combinatorial Mathematics : An Applied Introduction - 4th edition

ISBN13: 978-0201199123

Cover of Discrete and Combinatorial Mathematics : An Applied Introduction 4TH 99 (ISBN 978-0201199123)
ISBN13: 978-0201199123
ISBN10: 0201199122

Cover type: Hardback
Edition: 4TH 99
Copyright: 1999
Publisher: Addison-Wesley Longman, Inc.
Published: 1999
International: No

List price: $116.00

Discrete and Combinatorial Mathematics : An Applied Introduction - 4TH 99 edition

ISBN13: 978-0201199123

Ralph P. Grimaldi

ISBN13: 978-0201199123
ISBN10: 0201199122

Cover type: Hardback
Edition: 4TH 99
Copyright: 1999
Publisher: Addison-Wesley Longman, Inc.
Published: 1999
International: No

This fourth edition continues to improve on the features that have made it the market leader. The text offers a flexible organization, enabling instructors to adapt the book to their particular courses: discrete mathematics, graph theory, modern algebra, and/or combinatorics. More elementary problems were added, creating a greater variety of level in problem sets, which allows students to perfect skills as they practice. This new edition continues to feature numerous computer science applications--making this the ideal text for preparing students for advanced study.


  • This text has an enhanced mathematical approach, with carefully thought out examples, including many examples with computer sciences applications.
  • Historical reviews and biographies bring a human element to their assignments.
  • Chapter summaries allow students to review what they have learned.

Author Bio

Grimaldi, Ralph P. : Rose-Hulman Institute of Technology

Table of Contents

Chapter 1: Fundamentals of Discrete Mathematics

Fundamental Principles of Counting
The Rules of Sum and Product
The Binomial Theorem
Combinations with Repetition: Distributions
An Application in the Physical Sciences (Optional)
Catalan Numbers

Chapter 2: Fundamentals of Logic

Basic Connectives and Truth Tables
Logical Equivalence: The Laws of Logic
Logical Implication: Rules of Inference
The Use of Quantifiers
Quantifiers, Definitions, and the Proofs of Theorems

Chapter 3: Set Theory

Sets and Subsets
Set Operations and the Laws of Set Theory
Counting and Venn Diagrams
A Word on Probability

Chapter 4: Properties of the Integers: Mathematical Induction

The Well-Ordering Principle: Mathematical Induction
Recursive Definitions
The Division Algorithm: Prime Numbers
The Greatest Common Divisor: The Euclidean Algorithm
The Fundamental Theorem of Arithmetic

Chapter 5: Relations and Functions

Cartesian Products and Relations
Functions: Plain and One-to-One
Onto Functions: Stirling Numbers of the Second Kind
Special Functions
The Pigeonhole Principle
Function Composition and Inverse Functions
Computational Complexity
Analysis of Algorithms

Chapter 6: Languages: Finite State Machines

Language: The Set Theory of Strings
Finite State Machines: A First Encounter
Finite State Machines: A Second Encounter
Relations: The Second Time Around
Relations Revisited: Properties of Relations
Computer Recognition: Zero­One Matrices and Directed Graphs
Partial Orders: Hasse Diagrams
Equivalence Relations and Partitions
Finite State Machines: The Minimization Process

Chapter 7: Further Topics in Enumeration

The Principle of Inclusion and Exclusion
Generalizations of the Principle (Optional)
Derangements: Nothing Is in Its Right Place
Rook Polynomials
Arrangements with Forbidden Positions

Chapter 8: Generating Functions

Introductory Examples
Definition and Examples: Calculational Techniques
Partitions of Integers
Exponential Generating Functions
The Summation Operator

Chapter 9: Recurrence Relations

The First-Order Linear Recurrence Relation
The Second-Order Linear Recurrence Relation with Constant Coefficients
The Nonhomogeneous Recurrence Relation
The Method of Generating Functions
A Special Kind of Nonlinear Recurrence Relation (Optional)
Divide and Conquer Algorithms (Optional)

Chapter 10: Graph Theory and Applications

An Introduction to Graph Theory
Definitions and Examples
Subgraphs, Complements, and Graph Isomorphism
Vertex Degree: Euler Trails and Circuits
Planar Graphs
Hamilton Paths and Cycles
Graph Coloring and Chromatic Polynomials

Chapter 11: Trees

Definitions, Properties, and Examples
Rooted Trees
Trees and Sorting Algorithms
Weighted Trees and Prefix Codes
Biconnected Components and Articulation Points

Chapter 12: Optimization and Matching

Dijkstra's Shortest Path Algorithm
Minimal Spanning Trees
Transport Networks: The Max-Flow Min-Cut Theorem
Matching Theory

Chapter 13: Modern Applied Algebra

Rings and Modular Arithmetic
The Ring Structure: Definition and Examples
Ring Properties and Substructures
The Integers Modulo n
Ring Homomorphisms and Isomorphisms

Chapter 14: Boolean Algebra and Switching Functions

Switching Functions: Disjunctive and Conjunctive Normal Forms
Gating Networks: Minimal Sums of Products: Karnaugh Maps
Further Applications: Don't Care Conditions
The Structure of a Boolean Algebra (Optional)

Chapter 15: Groups, Coding Theory, and Polya's Method of Enumeration

Definition, Examples, and Elementary Properties
Homomorphisms, Isomorphisms, and Cyclic Groups
Cosets and Lagrange's Theorem
Elements of Coding Theory
The Hamming Metric
The Parity-Check and Generator trices
Group Codes: Decoding with Coset Leaders
Hamming Matrices Counting and Equivalence: Burnside's Theorem
The Cycle Index
The Pattern Inventory: Polya's Method of Enumeration

Chapter 16: Finite Fields and Combinatorial Designs

Polynomial Rings
Irreducible Polynomials: Finite Fields
Latin Squares
Finite Geometries and Affine Planes
Block Designs and Projective Planes

Exponential and Logarithmic Functions
Matrices, Matrix Operations, and Determinants
Countable and Uncountable Sets