Credits: 3-1-0-10 ( 1 hour of tutorial every week)
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 principle, Ramsey's theorem
Equivalence relations, partitions, partial order, posets, chain/antichain.
Definitions, degree, paths, cycles, Hamiltonian path, Eulerian cycles.
cycles and acyclic graphs.
Trees, spanning trees, 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.
Application: RSA.
Z_p, the cyclic structure of Z_p^*.
Definition of the 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.
Rings
Applications Of Group Theory (Burnside lemma and generalization to Polya's theorem, use of group theory in combinatorics).
Other interesting applications.
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.