Discrete and Combinatorial Mathematics

Ralph Grimaldi

• 9780201199123

Samenvatting:

*Appropriate for four different courses: Discrete Mathematics; Combinatorics; Graph Theory; Modern Applied Algebra. *Flexible, modular organization. *This text has an enhanced mathematical approach, with carefully thought out examples, including many examples with computer sciences applications. *Carefully thought-out examples, including examples with computer science applications. Students can learn by reading the text. *The Fourth Edition has added more elementary problems, creating a larger variety of level within the problem sets which allows students to establish skills as they practice. *Chapter summaries allow the student to review what they have learned, while historical reviews and biographies bring a human element to their assignments. 1. Fundamentals of Discrete Mathematics. Fundamental Principles of Counting. The Rules of Sum and Product. Permutations. Combinations:. The Binomial Theorem. Combinations with Repetition: Distributions. An Application in the Physical Sciences (Optional). 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. 3. Set Theory. Sets and Subsets. Set Operations and the Laws of Set Theory. Counting and Venn Diagrams. A Word on Probability. 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. 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. 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. 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. 8. Generating Functions. Introductory Examples. Definition and Examples: Calculational Techniques. Partitions of Integers. Exponential Generating Functions. The Summation Operator. 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