Lectures
Monday, Wednesday and Fridays 1:00pm-1:50pm CB 339.
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.
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 and Quizzes(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.
Problem Sessions
There will be various in-class problem sessions during the semester whose goal is to reinforce the concepts learned
during a given week. During the problem sessions you are strongly encouraged to share what you have learned and
to learn from your fellow class mates (share and learn).
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/24 | Introduction. What is combinatorics? |
| Fri 08/26 | Review of mathematical proofs. |
| Mon 08/29 | Basic Principles of counting. Permutations and factorials |
| Wed 08/31 | Combinations and selections |
| Fri 09/02 | Combinations and selections |
| Mon 09/05 | ACADEMIC HOLIDAY. LABOR DAY |
| Wed 09/07 | Binomial coefficients and Pascal's triangle |
| Fri 09/09 | Binomial coefficients and Pascal's triangle |
| Mon 09/12 | Selections with repetitions, Compositions |
| Wed 09/14 | A useful matrix inversion |
| Fri 09/16 | A useful matrix inversion |
| Mon 09/19 | Recurrences |
| Wed 09/21 | Auxiliary equation method |
| Fri 09/23 | Auxiliary equation method |
| Mon 09/26 | Generating functions |
| Wed 09/28 | Generating functions |
| Fri 09/30 | Derangements. Sorting algorithms |
| Mon 10/03 | Derangements. Sorting algorithms |
| Wed 10/05 | Test 1 Review |
| Fri 10/07 | Test 1 |
| Mon 10/10 | Catalan numbers |
| Wed 10/12 | Graphs |
| Fri 10/14 | Graphs |
| Mon 10/17 | Paths and Trees |
| Wed 10/19 | Spanning trees |
| Fri 10/21 | Spanning trees |
| Mon 10/24 | Bipartite graphs. Planarity |
| Wed 10/26 | Chords of a circle. Polyhedra |
| Fri 10/28 | Chords of a circle. Polyhedra |
| Mon 10/31 | Hamiltonian Graphs |
| Wed 11/02 | The travelling salesman proble |
| Fri 11/04 | Eulerian graphs |
| Mon 11/07 | Eulerian graphs |
| Wed 11/09 | Test 2 Review |
| Fri 11/11 | Test 2 |
| Mon 11/14 | Graph colouring |
| Wed 11/16 | Chromatic polynomial |
| Fri 11/18 | Partitions |
| Mon 11/21 | Partitions |
| Wed 11/23 | THANKSGIVING HOLIDAY |
| Fri 11/25 | THANKSGIVING HOLIDAY |
| Mon 11/28 | Partitions |
| Wed 11/30 | The inclusion-exclusion principle |
| Fri 12/02 | The inclusion-exclusion principle |
| Mon 12/05 | Applications of the IEP |
| Wed 12/07 | Applications of the IEP |
| Fri 12/09 | 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.