MA3034: Discrete Mathematics I, Fall 2026

• Instructor: Shen-Fu Tsai（parity@gmail.com）

• Office hour: by appointment

• Textbook: Richard A. Brualdi. Introductory Combinatorics, 5th edition. 滄海圖書出版

• References: Douglas B. West. Combinatorial mathematics. Cambridge University Press, 2021.

• Prerequisites:

  • logic, bijection, high school combinatorics, induction, calculus, linear algebra

Slides

basic counting and binomial coefficients

the inclusion-exclusion principle (PIE)

recurrence relations and generation functions

classical counting sequences

Schedule

1. Sep 08 basic counting and binomial coefficients permutations, r-subsets, combinations

   1. Sep 09 binomail coefficients, binomial theorem exercise

2. Sep 15 combinatorial arguments

   1. Sep 16 multinomial theorem, notations of permutations of [n], the inclusion-exclusion principle (PIE) exercise

3. Sep 22 Derangements

   1. Sep 23 exercise

4. Sep 29 Nonattacking rooks avoiding forbidden positions, rook polynomials, recurrence relations and generating functions, OGF, inversion of permutations of [n]

   1. Sep 30 OGF for inversion of permutations of [n], exercise

5. Oct 06 EGF, linearity of OGF and EGF, linear homogeneous recurrence relation

   1. Oct 07 Finding formula for the Fibonacci sequence in two ways

6. Oct 13 Test 1

   1. Oct 14 Solving linear homogeneous recurrence relation in two ways, exercise

7. Oct 20 When the characteristic equation has repeated roots

   1. Oct 21 Solving linear nonhomogeneous recurrence relation using OGF, exercise

8. Oct 27 classical counting sequences ballot list, triangulation of convex polygon

   1. Oct 28 Closed-form of Catalan numbers, binary tree, exercise

9. Nov 03

   1. Nov 04

10. Nov 10

    1. Nov 11 No class

11. Nov 17 Test 2

    1. Nov 18

12. Nov 24 the pigeonhole principle

    1. Nov 25

13. Dec 01 

    1. Dec 02 systems of distinct representatives (SDR)

14. Dec 08

    1. Dec 09

15. Dec 15

    1. Dec 16

16. Dec 22 Test 3

    1. Dec 23