MATH
317 – Combinatorics
Fall 2010
Professor:
Dr. Janet Vassilev
Office: Humanities 467
Office
Hours: MWF 11 am-12 pm and by appointment.
Telephone: 
(505)
277-2214
email: jvassil@math.unm.edu
webpage: http://www.math.unm.edu/~jvassil
Text
:
Principles and Techniques in Combinatorics, by Chen Chuan-Chong and Koh, Khee-Meng
Course
Meetings: The course lectures will be held in Mechanical Engineering
220 on Mondays, Wednesdays and Fridays at 10-10:50 am.
Topics: Basic enumeration including combinations,
permutations, set and integer partitions, distributions, and rearrangements,
binomial and multinomial theorems together with pigeon-hole and
inclusion-exclusion principles and mathematical induction principles, discrete
probability, elementary ordinary generating functions, recurrence relations,
and sorting algorithms.
Homework
(200 points): Homework will be assigned weekly on Fridays and will be
collected the following Friday at the beginning of class. Homework will
not be graded unless it is written in order and labeled
appropriately. The definitions and theorems in the text and
given in class are your tools for the homework proofs. If the theorem has a name, use it. Otherwise, I would prefer that you fully
describe the theorem in words that you plan to use, than state “by Theorem
3”. Each week around 4 of the assigned problems will be graded. The
weekly assignments will each be worth 20 points. I will drop your lowest two homework scores
and the remaining homework will be averaged to get a score out of 200.
Project
(200 points): Instead of a second midterm, all students will research
a “combinatorial” topic not covered in the course and creatively present their
research in either a paper, a poster or a class
presentation. More details on the
project will be handed out in class.
Topics need to be approved by me before any research can commence. Link to
project description.
Exams (300
points): I will give one midterm (100 points) and a final (200
points). There are no make up exams. If a test is missed,
notify me as soon as possible on the day of the exam.
For the midterms only, if you have a legitimate and documented
excuse, your grade will be recalculated without that test. The Midterm is
tentatively scheduled for Monday October 11. The Final is on Friday,
December 17, from 7:30 am-9:30 am.
Grades: General guidelines
for letter grades (subject to change; but they won't get any more strict):
90-100% - A; 80-89% - B; 70-79% - C; 60-69% - D; below 60% - F. In
assigning Final Grades for the course, I will compare your grade on all course
work (including the Final) and your grade on the Final Exam. You will
receive the better of the two grades.
Schedule (for Dr.
Vassilev’s Combinatorics) will be filled in as we proceed:
Date
|
Section
|
Topic
|
Homework
|
8/23
|
handout
|
The Addition, Multiplication and Subtraction Principles
|
|
8/25
|
1.2
|
Division
Principle, Examples of the basic principles and Permutations
|
|
8/27
|
1.2, 1.3
|
Permutations
and Circular Permutations
|
Chapter 1
problems: 2, 3, 4, 5, 6, 10, 11(ii), 14(i, iv)
Additional Problems
|
8/30
|
1.3, 1.4
|
Circular
Permutations and Combinations
|
|
9/1
|
1.4
|
Combinations
|
|
9/3
|
1.5
|
Injection and
Bijection Principles
|
Chapter 1
problems: 15, 16, 17, 19, 20, 21, 23, 26, 30, 35, 37
|
9/8
|
1.5
|
Examples of IP
and BP
|
|
9/10
|
1.6
|
Arrangements
with repetition
|
Chapter 1
problems: 25, 41, 42, 43, 47, 48, 50, 51, 77, 81(i, ii), 82
|
9/13
|
1.7
|
Selections with
repetition and distribution of distinct objects in distinct boxes
|
|
9/15
|
1.7
|
Distribution of
distinct objects in distinct boxes
|
|
9/17
|
1.7
|
Distribution of
indistinct objects in distinct boxes
|
Chapter 1
problems: 54, 55, 57, 58, 65, 66, 68, 72, 73, 84, 91
|
9/20
|
1.7
|
Distribution of
distinct objects in indistinct boxes and probability
|
|
9/22
|
2.2
|
Discrete
probability and the Binomial Theorem
|
Probability notes
|
9/24
|
2.2, 2.3
|
More on the
Binomial Theorem
|
Chapter 1
problems: 44
Chapter 2 problems: 1,
2, 10, 11, 14, 18, 24, 25, 26
Additional Problems
|
9/27
|
2.3, 2.5
|
Vandermonde’s
Identity and Chu Shih Chieh’s Identity
|
|
9/29
|
2.5, 2.6
|
Examples of CSC
and Shortest Paths and binomial coefficients
|
|
10/1
|
2.6
|
More on
Shortest paths and binomial coefficients
|
Chapter 2
problems: 12, 16, 19, 21, 30, 31, 34,
35, 40, 44
|
10/4
|
2.6, 2.7
|
Reflection
Principle and binomial coefficients modulo p
|
|
10/6
|
2.7, 2.8
|
Binomial coefficients
modulo p and the Multinomial Theorem
|
|
10/8
|
|
Review
|
Chapter 2
problems: 5, 7, 9, 15, 51, 52, 64, 66,
67
|
10/11
|
|
Midterm
|
|
10/13
|
3.2, 3.3
|
Pigeonhole
Principle
|
|
10/18
|
3.4
|
Ramsey Numbers
|
|
10/20
|
3.5, 4.1
|
Bounds for
Ramsey numbers and Principle of Inclusion and Exclusion
|
|
10/22
|
4.1, 4.2
|
Principle of
Inclusion and Exclusion
|
Chapter 3
problems: 1, 2, 4, 8, 10, 15, 22, 28, 31, 34, 35
|
10/25
|
4.3, 4.4
|
Generalized Principle of Inclusion and Exclusion
|
|
10/27
|
4.5
|
Derangements
and generalized derangements
|
|
10/29
|
4.6, 4.7
|
Euler phi
function and the problem of seating married couples around a table…
|
Chapter 4
problems: 1, 3, 6, 9, 11, 13, 14, 21, 27(4.6.2, 4.6.4, 4.6.6), 28, 32
|
11/1
|
5.1
|
Generating
Functions
|
|
11/3
|
5.1, 5.2
|
Solving
problems using generating functions
|
|
11/5
|
5.2, 5.3
|
More problems
and generating functions for partitions
|
Chapter 4
problems: 38, 39, 44, 46
Chapter 5 problems:
1, 2, 4, 6, 8, 10, 15
|
11/8
|
5.3, 5.4
|
Ferrer’s
diagrams and exponential generating functions
|
|
11/10
|
6.1, 6.2
|
Intro to
recurrence relations
|
|
11/12
|
6.3
|
Homogeneous
linear recurrence relations of order upto 2.
|
Chapter 5
problems: 17, 21, 31, 32, 34, 38, 39, 49, 53, 63
|
11/15
|
6.3
|
Homogeneous
linear recurrence relations of higher order
|
|
11/17
|
6.4
|
Nonhomogeneous
linear recurrence relations
|
|
11/19
|
6.4
|
Nonhomogeneous
linear recurrence relations
|
Chapter 6
problems: 1, 2, 4, 7, 9, 11, 12, 18, 19, 22
Additional Problems
|
11/22
|
6.5, 6.6
|
Applications of
recurrence relations, Systems of recurrence relations
|
|
11/24
|
6.7
|
Generating
functions and recurrence relations
|
|
11/29
|
6.8
|
Nonlinear
recurrence relations
|
|
12/1
|
6.9
|
Nonlinear
recurrence relations
|
|
12/3
|
|
|
Chapter 6
problems: 14, 15, 16, 26, 27, 28, 32,
35, 37, 39, 41
|
12/6
|
|
|
|
12/8
|
|
|
|
12/10
|
|
|
|
12/17
|
|
Final exam
|
|