You are previewing Discrete Mathematics and Combinatorics.
O'Reilly logo
Discrete Mathematics and Combinatorics

Book Description

Discrete Mathematics and Combinatorics provides a concise and practical introduction to the core components of discrete mathematics, featuring a balanced mix of basic theories and applications.

Table of Contents

  1. Cover
  2. Title Page
  3. Contents
  4. About the Author
  5. Dedication
  6. Preface
  7. Foreword
  8. Chapter 1 Equations, Inequalities and Basic Logic
    1. 1.1 Equations and Their Solutions
    2. 1.2 Logical Implications and Equivalences
    3. 1.3 Solving Linear Inequalities
    4. 1.4 Ranges for Linear Expression
    5. 1.5 Quadratic Inequalities
    6. 1.6 Ranges for Quadratic Expression
    7. Summary
    8. Problems
  9. Chapter 2 Sets, Functions and Relations
    1. 2.1 Set Theory
    2. 2.2 Relations
    3. 2.3 Partitions
    4. 2.4 Functions
    5. 2.5 Functions with Special Properties
    6. 2.6 Images and Inverse Images
    7. 2.7 Some Basic Functions and Their Properties
    8. 2.8 Increasing and Decreasing Functions
    9. 2.9 Sets and Their Cardinality
    10. Summary
    11. Problems
  10. Chapter 3 Logic
    1. 3.1 New Statements out of Old
    2. 3.2 Logical Equivalences and Implications
    3. 3.3 Tautologies and Contradictions
    4. 3.4 Normal Forms
    5. 3.5 Proof Techniques
    6. 3.6 Automatic Theorem Proving
    7. 3.7 Predicate Calculus
    8. 3.8 Inference Theory for Predicate Calculus
    9. Summary
    10. Problems
  11. Chapter 4 Counting Principles
    1. 4.1 A Fundamental Counting Principle
    2. 4.2 Permutations and Combinations
    3. 4.3 Applications of Permutations and Combinations
    4. Summary
    5. Problems
  12. Chapter 5 Mathematical Induction, Principle of Inclusion and Exclusion, and Pigeon-Hole Principle
    1. 5.1 Mathematical Induction
    2. 5.2 Principle of Inclusion and Exclusion
    3. 5.3 Pigeon-Hole Principle
    4. Summary
    5. Problems
  13. Chapter 6 Recurrence Relations
    1. 6.1 Introduction
    2. 6.2 Motivation
    3. 6.3 First Order Recurrence Relation
    4. 6.4 Homogeneous Recurrence Relation of Second Order
    5. 6.5 Non-homogeneous Recurrence Relation
    6. 6.6 Generating Functions
    7. Summary
    8. Problems
  14. Chapter 7 Number Theory
    1. 7.1 Introduction and Motivation
    2. 7.2 LCM and HCF
    3. 7.3 Primes
    4. 7.4 Congruence
    5. 7.5 Fermat's Theorem
    6. 7.6 Application of Number Theory in Cryptography
    7. Summary
    8. Problems
  15. Chapter 8 Groups, Rings and Fields
    1. 8.1 Introduction
    2. 8.2 Motivation
    3. 8.3 Binary Operations
    4. 8.4 Associativity
    5. 8.5 Identity Elements
    6. 8.6 Inverse Elements
    7. 8.7 Groups
    8. 8.8 Fundamental Results in Group Theory
    9. 8.9 Homomorphism and Isomorphism of Groups
    10. 8.10 Subgroups
    11. 8.11 Normal Subgroups
    12. 8.12 Rings
    13. 8.13 Fields
    14. Summary
    15. Problems
  16. Chapter 9 Graph Theory
    1. 9.1 Introduction and Motivation
    2. 9.2 Paths
    3. 9.3 Matrix Representation of Graphs
    4. 9.4 Cut Vertices and Connectivity
    5. 9.5 Trees
    6. 9.6 Euler Paths
    7. Summary
    8. Problems
  17. Chapter 10 Posets, Lattices and Boolean Algebras
    1. 10.1 Introduction and Motivation
    2. 10.2 Posets
    3. 10.3 Lattices
    4. 10.4 Boolean Algebra
    5. Summary
    6. Problems
  18. Chapter 11 Formal Languages and Language Acceptors
    1. 11.1 Alphabet, Strings and Languages
    2. 11.2 Finite Automata and Regular Languages
    3. 11.3 Pushdown Automata and Context-Free Languages
    4. 11.4 Turing Machines
    5. 11.5 Linear Bounded Automata and Context-Sensitive Languages
    6. 11.6 Turing Machines and Recursively Enumerable Languages
    7. 11.7 Formal Languages and Grammar
    8. Summary
    9. Problems
  19. Chapter 12 Turing Machines and Computable Functions
    1. 12.1 Recursive and Primitive Recursive Functions
    2. 12.2 Turing Machines and Computable Functions
    3. Summary
    4. Problems
  20. Chapter 13 Coding Theory
    1. 13.1 Introduction and Preliminaries
    2. 13.2 Error Detection
    3. 13.3 Decoding
    4. Summary
    5. Problems
  21. Chapter 14 Discrete Probability
    1. 14.1 Sample Space
    2. 14.2 Events
    3. 14.3 Random Variable
    4. 14.4 Basic Probability
    5. 14.5 Conditional Probability and Bayes Theorem
    6. 14.6 Random Variables, their Means and Probability Mass Functions
    7. 14.7 Variance, Standard Deviation and Moments
    8. 14.8 Binomial Distribution
    9. 14.9 Geometric Random Variable
    10. 14.10 Negative Binomial Distribution
    11. 14.11 Poisson Distribution
    12. Summary
    13. Problems
  22. Appendix-A Mathematical Preliminaries for Special Distributions
  23. Appendix-B Trigonometry
  24. Appendix-C Matrices
  25. Notes
  26. List of Symbols
  27. Acknowledgements
  28. Copyright
  29. Back Cover