Combinatorics

MTH1401 Linear Algebra 1

3 hours One requisite

MTH1201 Foundation of Mathematics

3 hours No requisites

1 Some revisions for basic concepts from foundation mathematics: Algorithms, integers, relations, logic and sets

2 Counting methods: / The basic rules of counting: / Sum rule / Product rule / Subtraction rule / Division rule / Pigeonhole rule / Permutation and Combinations / Binomial Coefficients and Identities / Generalized Permutations and Combinations / - Generating Permutations and Combinations. / Apply the rules to find the number of functions between two finite sets, the number of injective functions between two sets, number of onto functions between two sets and the number of bijection functions between two sets

3 Advanced Counting Techniques: Applications of Recurrence Relations, Solving Linear Recurrence Relations, Divide-and-Conquer Algorithms and Recurrence Relations, Generating Functions, Inclusion–Exclusion principal and its generalizations. Burnside Counting Argument. Poly methods for counting’s

4 Boolean Algebra and representing Boolean functions: / Boolean Expressions and Boolean Functions. Identities of Boolean Algebra and representing Boolean Functions and logic Gates

5 Others: Revision and activities, Exam, quizzes

1.1 Mapped to: K1

Understand the basic principles of mathematical induction and some proof techniques, and apply them to relevant cases.

1.2 Mapped to: K1, K2

To understand and apply counting techniques (the pigeonhole principle, the inclusion exclusion principle, the binomial coefficients, permutations and combinations) to solve counting problems.

Teaching Strategy Lectures