everything.study
MATH 3855

Discrete Structures and Applications (Honours)

0.5 credit · Undergraduate

Enumeration: inclusion and exclusion, recurrence relations, generating functions and applications. Graph theory: connectivity, planarity, Hamilton paths and Euler trails. Error-correcting codes. Designs and finite geometries. Symmetry and counting.

2022

Topics

  • 6.2; 6.4; Introduction, Pigeonhole and
  • 10.3 -10.6 Euler’s function
  • 11.1-11.4 binomial numbers; unordered selections
  • 11.5-11.7; sieve principal; designs and t-designs
  • 12.3- 12. 4; Multinomial numbers
  • 25.1 - 25.3 power series and properties
  • 25.4 - 25.6 Generating functions; homogenous and
  • Nov. 4 26.1-26.2 partitions and diagrams; conjugate
  • 15.1-15.6 Graphs; isomorphism; valency
  • Course notes; Planar graphs; Euler’s theorem
  • 24.1 -24.2 words, codes and errors; Linear codes
  • Dec. 1 24.3 - 24.4 construction and error correction
  • 27.1-6 Symmetry and counting; course review

Readings

  • “Discrete Mathematics” by Norman L. Biggs (Oxford Science Publications, 2nd edition).

Prerequisites & course information

Also listed as COMP 3805 . Precludes additional credit for MATH 3805 (no longer offered) and MATH 3825 . Prerequisite(s): MATH 2100 with a grade of C- or higher; or ( MATH 2108 or MATH 3101 ) with a grade of B or higher. Lectures three hours a week, tutorial one hour a week.

Sources