Lectures
Monday, Wednesday and Fridays 1:00pm-1:50pm CB 341.
Literature
A First Course in Discrete Mathematics. Ian Anderson.
Course Contents
This course is a basic course in the theory of counting and graph theory. Counting. Subsets and binomial coefficients.
Partitions and Stirling numbers. Permutations and permutation statistics. Fibonacci and Catalan numbers.
The inclusion-exclusion principle.
Recurrences. Generating functions. Graphs. Eulerian and Hamiltonian cycles. Graph colouring. Matrix tree theorem. Some additional topics.
Most of chapters 1 to 6 from Anderson's book.
Examination and Grading
Tests (30%)
There will be 2 tests. These will be announced at least one week in advance.
Final (30%)
There will be a comprehensive final to be worth 30%.
Homework (40%)
There will be a set of problems to be handed in at the end of every week. To work on the homework problems is
crucial for your understanding of the material presented in class. Be sure to separate enough time each week
to think and write your solutions.
It is recommended that you think and attempt every problem on your own before
seeking any help. You are encouraged to discuss the material of the course with your classmates, however you must
write your own solutions using your own words. There can be unannounced quizzes that will count towards your homework grade.
Any of these quizzes will occur on the Wednesday session.
Suggested problems
There will be some additional suggested problems. These problems will be assigned after some of the
classes and also posted in the web page of the course.
Grading Scale
| >=90% | A |
| >=80% | B |
| >=70% | C |
| >=60% | D |
| <60% | E |
Syllabus
This is an approximate schedule of the course containing the syllabus:
| Wed 08/26 | Introduction. What is combinatorics? |
| Fri 08/28 | Review of mathematical proofs. |
| Mon 08/31 | Basic Principles of counting. Permutations and factorials |
| Wed 09/02 | Combinations and selections |
| Fri 09/04 | Binomial coefficients and Pascal's triangle |
| Mon 09/07 | ACADEMIC HOLIDAY. LABOR DAY |
| Wed 09/09 | Selections with repetitions, Compositions |
| Fri 09/11 | A useful matrix inversion |
| Mon 09/14 | Recurrences |
| Wed 09/16 | Auxiliary equation method |
| Fri 09/18 | Generating functions |
| Mon 09/21 | Generating functions |
| Wed 09/23 | Derangements. Sorting algorithms |
| Fri 09/25 | Catalan numbers |
| Mon 09/28 | More generating functions |
| Wed 09/30 | Test 1 Review |
| Fri 10/02 | Test 1 |
| Mon 10/05 | Graphs |
| Wed 10/07 | Paths and Trees |
| Fri 10/09 | Spanning trees. |
| Mon 10/12 | Bipartite graphs. Planarity |
| Wed 10/14 | Chords of a circle. Polyhedra |
| Fri 10/16 | Hamiltonian Graphs |
| Mon 10/19 | The travelling salesman problem |
| Wed 10/21 | Eulerian graphs |
| Fri 10/23 | Partitions |
| Mon 10/26 | Partitions |
| Wed 10/28 | Graph colouring |
| Fri 10/30 | Chromatic polynomial |
| Mon 11/02 | Chromatic polynomial |
| Wed 11/04 | Test 2 Review |
| Fri 11/06 | Test 2 |
| Mon 11/09 | The inclusion-exclusion principle |
| Wed 11/11 | Applications of the IEP |
| Fri 11/13 | Applications of the IEP |
| Mon 11/16 | Graphs and linear algebra |
| Wed 11/18 | Graphs and linear algebra |
| Fri 11/20 | The matrix tree theorem |
| Mon 11/23 | Permutation statistics |
| Wed 11/25 | THANKSGIVING HOLIDAY |
| Fri 11/27 | THANKSGIVING HOLIDAY |
| Mon 11/30 | Permutation statistics |
| Wed 12/02 | Additional topics |
| Fri 12/04 | Additional topics |
| Mon 12/07 | Additional topics |
| Wed 12/09 | Additional topics |
| Fri 12/11 | Review Final |
Calculators Policy
Calculators are not allowed in quizzes, tests or the final exam.
Code of Conduct
Students should consult the students rights and responsibilities outlined in the
Student Code of Conduct.
Any offense to the Code of Conduct will result in a grade of "E" for the course and a referral to
the Dean of Students.
Excused Absences
University Senate Rule 5.2.4.2 defines the following acceptable reasons for an ”excused absence” from class:
- Serious illness (must be documented by doctor’s excuse)
- Illness or death of a family member
- University-related trips (must be documented by a letter from sponsor)
- Major religious holidays
- Other circumstances that your instructor finds to be ”reasonable cause for nonattendence”
Students should notify the instructor of an excused absence prior to the absence whenever
possible and complete all work prior to the absence (unless for illness or for the illness or
death of a family member).
Students with Disabilities
Students with documented physical‚ learning‚ or temporary disabilities may receive assistance and support
from the
Disability Resource Center.
It is recommended that students contact the Disability Resource Center early to request specific assistance
so that the required medical or psychological documentation can be reviewed and reasonable accommodations
can be provided from the beginning of class work in order to achieve the greatest benefit to the student.
Changes to this Syllabus
This syllabus may have some changes during the semester. It is responsibility of the students to visit frequently
the webpage of the course for up to date information.