Sets, relations, functions, countable and uncountable sets.
Proofs; Proofs by deduction, contrapositive and contradiction (diagonalization).
Proofs by induction
* All these proof techniques can be covered through examples. The rigorous notion of proof will be covered in CS 202 and can be skipped here.
Selection/combination, arrangements/permutation, rule of sum, rule of product.
Binomial coefficients, identities, multinomial coefficients.
Selection with repetition/distributions of objects into cells, distinguishable/indistinguishable objects.
Combinatorial problems with restrictions
Recurrence relations to solve combinatorial problems.
Generating functions to solve recurrence.
Inclusion-exclusion, Pigeonhole principal, Ramsey's theorem
Equivalence relations, partitions, partial order, posets, chain/anti chain.
Definitions, degree, paths, cycles, Hamiltonian path, Eulerian cycles.
cycles and acyclic graphs.
Trees, spanning tree, networks.
Divisibility, primes, division theorem, Euclid's gcd/extended Euclid's algorithm, Unique factorization domain.
Modular arithmetic, sums and products, Chinese remaindering, Mobius inversion.
Fermat's little theorem, Euler's theorem.
Z_p, cyclic structure of Z_p^*.
Definition of field as a generalization to F_p.
Application: Polynomials over F_p, error correction.
Definitions, examples (Z_n and Z_n^*)
cyclic and dihedral group, abelian groups.
Subgroups, cosets, partition
permutation group, transpositions, cycle representation
symmetries as a group.
Burnside lemma and generalization to Polya's theorem (use of group theory in combinatorics).
Other interesting applications if time permits.
1) Kenneth Rosen, Discrete mathematics and its applications.
2) Norman Biggs, Discrete mathematics.
3) Chung Liu, Introduction to combinatorial mathematics.
4) David Burton, Elementary number theory.