Combinatorial Mathematics (MATH365)

Number and counting; odometer principle, principle of induction, order of magnitude, handshaking lemma, set notation. Subsets, partitions, permutations; subset, subset of fixed size, the binomial theorem, pascal's triangle, Lucas' theorem, permutations, estimates for factorials, Cayley's theorem on trees, Bell numbers, generating combinatorial objects. Recurrence relations and generating functions; Fibonacci numbers, linear recurrence relations with constant coefficients, derangements and involutions, Catalan and Bell numbers. The principle of inclusion and exclusion; PIE and its generalization, Stirling numbers and exponentials, even add odd permutations. System of distinct representatives; Hall's theorem. Extremal set theory; intersecting families, Erdos-Ko-Rado theorem, Sperner's theorem, the de Brujin-Erdos theorem. Graphs; trees and forests, Cayley's theorem, minimal spanning tree, Eulerian graphs, Hamiltonian graphs, Ore's theorem, gray codes, the traveling salesman, digraphs, networks, max-flow min-cut theorem , integrity theorem, Menger's theorem, Könsg's theorem, Hall's theorem, diameter and girth. Ramsey's theoremlthe pigeonhole principle, bounds for Ramsey's theorem, Applications, infinite version.

Related Programs