MA/CS 415G 001 Combinatorics and Graph Theory

Instructor: Rafael S. González D'León
Office: Patterson Office Tower, Room 767.
Office Hours: TW 2:00PM to 3:00PM or by appointment.


Monday, Wednesday and Fridays 1:00pm-1:50pm CB 341.


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



This is an approximate schedule of the course containing the syllabus:
Wed 08/26Introduction. What is combinatorics?
Fri 08/28Review of mathematical proofs.
Mon 08/31Basic Principles of counting. Permutations and factorials
Wed 09/02Combinations and selections
Fri 09/04Binomial coefficients and Pascal's triangle
Wed 09/09Selections with repetitions, Compositions
Fri 09/11A useful matrix inversion
Mon 09/14Recurrences
Wed 09/16Auxiliary equation method
Fri 09/18Generating functions
Mon 09/21Generating functions
Wed 09/23Derangements. Sorting algorithms
Fri 09/25Catalan numbers
Mon 09/28More generating functions
Wed 09/30Test 1 Review
Fri 10/02Test 1
Mon 10/05Graphs
Wed 10/07Paths and Trees
Fri 10/09Spanning trees.
Mon 10/12Bipartite graphs. Planarity
Wed 10/14Chords of a circle. Polyhedra
Fri 10/16Hamiltonian Graphs
Mon 10/19The travelling salesman problem
Wed 10/21Eulerian graphs
Fri 10/23Partitions
Mon 10/26Partitions
Wed 10/28Graph colouring
Fri 10/30Chromatic polynomial
Mon 11/02Chromatic polynomial
Wed 11/04Test 2 Review
Fri 11/06Test 2
Mon 11/09The inclusion-exclusion principle
Wed 11/11Applications of the IEP
Fri 11/13Applications of the IEP
Mon 11/16Graphs and linear algebra
Wed 11/18Graphs and linear algebra
Fri 11/20The matrix tree theorem
Mon 11/23Permutation statistics
Mon 11/30Permutation statistics
Wed 12/02Additional topics
Fri 12/04Additional topics
Mon 12/07Additional topics
Wed 12/09Additional topics
Fri 12/11Review 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 defines the following acceptable reasons for an ”excused absence” from class: 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.