Discrete and Combinatorial Mathematics

Fundamental principles of counting, including rules of sums and product, permutations and combinations. Fundamentals of logic and integers, including mathematical induction, recursive definitions, prime numbers, greatest common divisor, Cartesian products and relations, pigeonhole principle, partial orders, equivalence relations and partitions. The principle of inclusion and exclusion. Sums and recurrence relations: first and second order linear recurrence relations, finite and infinite calculus, infinite sums. Integer functions including floor and ceiling applications and recurrences, and the modulo operation. Generating functions including the method of generating functions for solving recurrences and exponential generating functions. Introduction to graph theory including graph isomorphism, Euler tours, Hamiltonian paths and cycles, planar graphs, and graph coloring.