Discrete and combinatorial mathematics
Subtitle: an applied introduction
By: Ralph P. Grimaldi.
Edition: 4th ed.
Publisher: Addison-Wesley Longman
Published: 1999
Place of publication: Reading, Mass
Language: eng
Number of pages: 791
Subjects: Mathematics.; Computer science -- Mathematics.; Combinatorial analysis.
Notes: Includes index.
Table of contents: label: Part 1
title: Fundamentals of Discrete Mathematics
pagenum: 1; label: 1
title: Fundamental Principles of Counting
pagenum: 3; label: 1.1
title: The Rules of Sum and Product
pagenum: 3; label: 1.2
title: Permutations
pagenum: 6; label: 1.3
title: Combinations: The Binomial Theorem
pagenum: 15; label: 1.4
title: Combinations with Repetition
pagenum: 27; label: 1.5
title: An Application in the Physical Sciences (Optional)
pagenum: 36; label: 1.6
title: The Catalan Numbers (Optional)
pagenum: 36; label: 1.7
title: Summary and Historical Review
pagenum: 41; label: 2
title: Fundamentals of Logic
pagenum: 47; label: 2.1
title: Basic Connectives and Truth Tables
pagenum: 47; label: 2.2
title: Logical Equivalence: The Laws of Logic
pagenum: 56; label: 2.3
title: Logical Implication: Rules of Inference
pagenum: 68; label: 2.4
title: The Use of Quantifiers
pagenum: 89; label: 2.5
title: Quantifiers, Definitions, and the Proofs of Theorems
pagenum: 107; label: 2.6
title: Summary and Historical Review
pagenum: 123; label: 3
title: Set Theory
pagenum: 127; label: 3.1
title: Sets and Subsets
pagenum: 127; label: 3.2
title: Set Operations and the Laws of Set Theory
pagenum: 139; label: 3.3
title: Counting and Venn Diagrams
pagenum: 151; label: 3.4
title: A Word on Probability
pagenum: 154; label: 3.5
title: Summary and Historical Review
pagenum: 157; label: 4
title: Properties of the Integers: Mathematical Induction
pagenum: 163; label: 4.1
title: The Well-Ordering Principle: Mathematical Induction
pagenum: 163; label: 4.2
title: Recursive Definitions
pagenum: 178; label: 4.3
title: The Division Algorithm: Prime Numbers
pagenum: 189; label: 4.4
title: The Greatest Common Divisor: The Euclidean Algorithm
pagenum: 200; label: 4.5
title: The Fundamental Theorem of Arithmetic
pagenum: 207; label: 4.6
title: Summary and Historical Review
pagenum: 212; label: 5
title: Relations and Functions
pagenum: 217; label: 5.1
title: Cartesian Products and Relations
pagenum: 218; label: 5.2
title: Functions: Plain and One-to-One
pagenum: 222; label: 5.3
title: Onto Functions: Stirling Numbers of the Second Kind
pagenum: 230; label: 5.4
title: Special Functions
pagenum: 238; label: 5.5
title: The Pigeonhole Principle
pagenum: 244; label: 5.6
title: Function Composition and Inverse Functions
pagenum: 249; label: 5.7
title: Computational Complexity
pagenum: 261; label: 5.8
title: Analysis of Algorithms
pagenum: 266; label: 5.9
title: Summary and Historical Review
pagenum: 273; label: 6
title: Languages: Finite State Machines
pagenum: 281; label: 6.1
title: Language: The Set Theory of Strings
pagenum: 282; label: 6.2
title: Finite State Machines: A First Encounter
pagenum: 292; label: 6.3
title: Finite State Machines: A Second Encounter
pagenum: 299; label: 6.4
title: Summary and Historical Review
pagenum: 306; label: 7
title: Relations: The Second Time Around
pagenum: 311; label: 7.1
title: Relations Revisited: Properties of Relations
pagenum: 311; label: 7.2
title: Computer Recognition: Zero-One Matrices and Directed Graphs
pagenum: 319; label: 7.3
title: Partial Orders: Hasse Diagrams
pagenum: 331; label: 7.4
title: Equivalence Relations and Partitions
pagenum: 341; label: 7.5
title: Finite State Machines: The Minimization Process
pagenum: 346; label: 7.6
title: Summary and Historical Review
pagenum: 352; label: Part 2
title: Further Topics in Enumeration
pagenum: 359; label: 8
title: The Principle of Inclusion and Exclusion
pagenum: 361; label: 8.1
title: The Principle of Inclusion and Exclusion
pagenum: 361; label: 8.2
title: Generalizations of the Principle
pagenum: 369; label: 8.3
title: Derangements: Nothing Is in Its Right Place
pagenum: 374; label: 8.4
title: Rook Polynomials
pagenum: 376; label: 8.5
title: Arrangements with Forbidden Positions
pagenum: 379; label: 8.6
title: Summary and Historical Review
pagenum: 383; label: 9
title: Generating Functions
pagenum: 387; label: 9.1
title: Introductory Examples
pagenum: 387; label: 9.2
title: Definition and Examples: Calculational Techniques
pagenum: 390; label: 9.3
title: Partitions of Integers
pagenum: 400; label: 9.4
title: The Exponential Generating Function
pagenum: 403; label: 9.5
title: The Summation Operator
pagenum: 408; label: 9.6
title: Summary and Historical Review
pagenum: 409; label: 10
title: Recurrence Relations
pagenum: 415; label: 10.1
title: The First-Order Linear Recurrence Relation
pagenum: 415; label: 10.2
title: The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients
pagenum: 424; label: 10.3
title: The Nonhomogeneous Recurrence Relation
pagenum: 434; label: 10.4
title: The Method of Generating Functions
pagenum: 445; label: 10.5
title: A Special Kind of Nonlinear Recurrence Relation (Optional)
pagenum: 450; label: 10.6
title: Divide-and-Conquer Algorithms (Optional)
pagenum: 460; label: 10.7
title: Summary and Historical Review
pagenum: 469; label: Part 3
title: Graph Theory and Applications
pagenum: 475; label: 11
title: An Introduction to Graph Theory
pagenum: 477; label: 11.1
title: Definitions and Examples
pagenum: 477; label: 11.2
title: Subgraphs, Complements, and Graph Isomorphism
pagenum: 485; label: 11.3
title: Vertex Degree: Euler Trails and Circuits
pagenum: 495; label: 11.4
title: Planar Graphs
pagenum: 505; label: 11.5
title: Hamilton Paths and Cycles
pagenum: 523; label: 11.6
title: Graph Coloring and Chromatic Polynomials
pagenum: 532; label: 11.7
title: Summary and Historical Review
pagenum: 540; label: 12
title: Trees
pagenum: 547; label: 12.1
title: Definitions, Properties, and Examples
pagenum: 547; label: 12.2
title: Rooted Trees
pagenum: 553; label: 12.3
title: Trees and Sorting
pagenum: 570; label: 12.4
title: Weighted Trees and Prefix Codes
pagenum: 575; label: 12.5
title: Biconnected Components and Articulation Points
pagenum: 580; label: 12.6
title: Summary and Historical Review
pagenum: 585; label: 13
title: Optimization and Matching
pagenum: 591; label: 13.1
title: Dijkstra's Shortest-Path Algorithm
pagenum: 591; label: 13.2
title: Minimal Spanning Trees: The Algorithms of Kruskal and Prim
pagenum: 599; label: 13.3
title: Transport Networks: The Max-Flow Min-Cut Theorem
pagenum: 605; label: 13.4
title: Matching Theory
pagenum: 616; label: 13.5
title: Summary and Historical Review
pagenum: 625; label: Part 4
title: Modern Applied Algebra
pagenum: 631; label: 14
title: Rings and Modular Arithmetic
pagenum: 633; label: 14.1
title: The Ring Structure: Definition and Examples
pagenum: 633; label: 14.2
title: Ring Properties and Substructures
pagenum: 639; label: 14.3
title: The Integers Modulo n
pagenum: 646; label: 14.4
title: Ring Homomorphisms and Isomorphisms
pagenum: 652; label: 14.5
title: Summary and Historical Review
pagenum: 657; label: 15
title: Boolean Algebra and Switching Functions
pagenum: 663; label: 15.1
title: Switching Functions: Disjunctive and Conjunctive Normal Forms
pagenum: 663; label: 15.2
title: Gating Networks: Minimal Sums of Products: Karnaugh Maps
pagenum: 672; label: 15.3
title: Further Applications: Don't-Care Conditions
pagenum: 682; label: 15.4
title: The Structure of a Boolean Algebra (Optional)
pagenum: 687; label: 15.5
title: Summary and Historical Review
pagenum: 696; label: 16
title: Groups, Coding Theory, and Polya's Method of Enumeration
pagenum: 701; label: 16.1
title: Definition, Examples, and Elementary Properties
pagenum: 701; label: 16.2
title: Homomorphisms, Isomorphisms, and Cyclic Groups
pagenum: 708; label: 16.3
title: Cosets and Lagrange's Theorem
pagenum: 713; label: 16.4
title: Elements of Coding Theory
pagenum: 715; label: 16.5
title: The Hamming Metric
pagenum: 720; label: 16.6
title: The Parity-Check and Generator Matrices
pagenum: 722; label: 16.7
title: Group Codes: Decoding with Coset Leaders
pagenum: 727; label: 16.8
title: Hamming Matrices
pagenum: 731; label: 16.9
title: Counting and Equivalence: Burnside's Theorem
pagenum: 733; label: 16.10
title: The Cycle Index
pagenum: 740; label: 16.11
title: The Pattern Inventory: Polya's Method of Enumeration
pagenum: 744; label: 16.12
title: Summary and Historical Review
pagenum: 749; label: 17
title: Finite Fields and Combinatorial Designs
pagenum: 755; label: 17.1
title: Polynomial Rings
pagenum: 755; label: 17.2
title: Irreducible Polynomials: Finite Fields
pagenum: 763; label: 17.3
title: Latin Squares
pagenum: 772; label: 17.4
title: Finite Geometries and Affine Planes
pagenum: 778; label: 17.5
title: Block Designs and Projective Planes
pagenum: 783; label: 17.6
title: Summary and Historical Review
pagenum: 788; label: Appendix 1
title: Exponential and Logarithmic Functions
pagenum: A-1; label: Appendix 2
title: Matrices, Matrix Operations, and Determinants
pagenum: A-11; label: Appendix 3
title: Countable and Uncountable Sets
pagenum: A-25; title: Solutions
pagenum: S-1; title: Index
pagenum: 1-1