Discrete Mathematics and Combinatorics
摘要
This chapter develops the essential machinery of discrete mathematics—sets, relations, functions, propositional and predicate logic, combinatorial counting, generating functions, recurrence relations, elementary number theory, and graph theory—through a computational lens. Each concept is introduced with formal definitions and proof techniques (induction, contradiction, pigeonhole), then translated into idiomatic Python using itertools, sympy, and networkx. Counting problems are solved via explicit enumeration and analytic combinatorics, while recurrence relations are automated with linear-operator methods and closed-form solutions verified symbolically. Modular arithmetic and primitive roots lay a foundation for cryptographic primitives such as RSA, and graph algorithms (connectivity, Eulerian and Hamiltonian paths, planar embeddings) are implemented and empirically analysed. Throughout, rigorous mathematical reasoning is coupled with executable code, demonstrating how discrete structures underpin algorithm design and complexity analysis in modern scientific computing.