## Table of Contents

**PART 1. FUNDAMENTALS OF DISCRETE MATHEMATICS.**

**1. Fundamental Principles of Counting.**

The Rules of Sum and Product.

Permutations.

Combinations: The Binomial Theorem.

Combinations with Repetition.

The Catalan Numbers (Optional).

Summary and Historical Review.

**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.

Summary and Historical Review.

**3. Set Theory.**

Sets and Subsets.

Set Operations and the Laws of Set Theory.

Counting and Venn Diagrams.

A First Word on Probability.

The Axioms of Probability (Optional).

Conditional Probability: Independence (Optional).

Discrete Random Variables (Optional).

Summary and Historical Review.

**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.

Summary and Historical Review.

**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.

Summary and Historical Review.

**6. Languages: Finite State Machines.**

Language: The Set Theory of Strings.

Finite State Machines: A First Encounter.

Finite State Machines: A Second Encounter.

Summary and Historical Review.

**7. 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.

Summary and Historical Review.

**PART 2. FURTHER TOPICS IN ENUMERATION.**

**8. The Principle of Inclusion and Exclusion.**

The Principle of Inclusion and Exclusion.

Generalizations of the Principle.

Derangements: Nothing Is in Its Right Place.

Rook Polynomials.

Arrangements with Forbidden Positions.

Summary and Historical Review.

**9. Generating Functions.**

Introductory Examples.

Definition and Examples: Calculational Techniques.

Partitions of Integers.

The Exponential Generating Functions.

The Summation Operator.

Summary and Historical Review.

**10. Recurrence Relations.**

The First-Order Linear Recurrence Relation.

The Second-Order Linear Homogeneous 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.

Summary and Historical Review.

**PART 3. GRAPH THEORY AND APPLICATIONS.**

**11. 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.

Summary and Historical Review.

**12. Trees.**

Definitions, Properties, and Examples.

Rooted Trees.

Trees and Sorting.

Weighted Trees and Prefix Codes.

Biconnected Components and Articulation Points.

Summary and Historical Review.

**13. Optimization and Matching.**

Dijkstra's Shortest Path Algorithm.

Minimal Spanning Trees: The Algorithms of Kruskal and Prim.

Transport Networks: The Max-Flow Min-Cut Theorem.

Matching Theory.

Summary and Historical Review.

**PART 4. MODERN APPLIED ALGEBRA.**

**14. Rings and Modular Arithmetic.**

The Ring Structure: Definition and Examples.

Ring Properties and Substructures.

The Integers Modulo n. Cryptology.

Ring Homomorphisms and Isomorphisms: The Chinese Remainder Theorem.

Summary and Historical Review.

**15. 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).

Summary and Historical Review.

**16. Groups, Coding Theory, and Polya's Theory of Enumeration.**

Definition, Examples, and Elementary Properties.

Homomorphisms, Isomorphisms, and Cyclic Groups.

Cosets and Lagrange's Theorem.

The RSA Cipher (Optional).

Elements of Coding Theory.

The Hamming Metric.

The Parity-Check and Generator Matrices.

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.

Summary and Historical Review.

**17. Finite Fields and Combinatorial Designs.**

Polynomial Rings.

Irreducible Polynomials: Finite Fields.

Latin Squares.

Finite Geometries and Affine Planes.

Block Designs and Projective Planes.

Summary and Historical Review.

**Appendices.**

Exponential and Logarithmic Functions.

Matrices, Matrix Operations, and Determinants.

Countable and Uncountable Sets.

**Solutions.**

**Index.**