Course description:
Topics from algebra of sets, permutations, combinations, occupancy problems,
partitions of integers, generating functions, combinatorial identities,
recurrence relations, inclusion-exclusion principle, Polya's theory of
counting, permanents, systems of distinct representatives, Latin rectangles,
block designs, finite projective planes, Steiner triple systems.
Prerequisites: SC/MATH 2022 3.00 or SC/MATH 2222 3.00;
six credits from 3000-level mathematics courses without second digit 5;
or permission of the course coordinator.
The main goal of this course will be to develop four common tools of
combinatorics that are used to enumerate finite sets: basic counting
principles, bijective arguments, Pólya Theory and generating functions.
We will apply these tools to examine specific examples of combinatorial
objects. The emphasis of assignments will be on problem solving and
development of combinatorial techniques.
WARNING THIS IS AN OLDER WEB PAGE FROM A COURSE GIVEN IN 2017 AND IS HERE FOR REFERENCE ONLY
Announcements:
(Sept. 7, 2017)
(I'm writing this at 10am for a 2:30pm class)
So today we are going to look at how combinatorics can be used to
compute sums of the form $1^r+2^r+...+n^r$. We will just do a bit
of experimenting and conjecturing today, but then I want you to
go home, watch some videos and do some homework and we will get to the punchline next time.
Please watch the following videos:
Then I would like you to to prove the following results using telescoping sums:
- $1^3+2^3+...+n^3 = \frac{n^2(n+1)^2}{4}$
- $1^4+2^4+...+n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$
- $(1)_k + (2)_k + ... + (n)_k = \frac{(n+1)_{k+1}}{k+1}$
Start typing up those in LaTeX. You don't have to hand it in next time, but
you will hand it in when I give you your first homework assignment.
(Sept 7, 2017) In case you are interested in the sage commands that I used
to compute $1^6+2^6+...+n^6$, I typed
[sum(i**6 for i in range(1,n+1)) for n in range(1, 11)]
and this gave me the first 10 terms of that sequence.
(Sept 21, 2017) I meant to post the homework yesterday,
but there were (and still are) edits to do. The problems won't change, but
I will add a few details so please check back. It will be due
October 5, 2017.
Homework #1. You will turn
it in on the
moodle in LaTeX/pdf format.
(Oct 5, 2017) I just posted the next
homework assignment. It will be due
in two weeks (Oct 25 ...corrected from Oct 19 and 23).
(Oct 6, 2017) Please copy the question that you are answering in your
assignments. It is always so unclear when reading your assignments
what an answer is referring to unless the complete question is there.
(Oct 12, 2017) Please figure out the answers to the
matching
worksheet for class today.
(Oct 12, 2017) The correct due date is October 25...corrected from Oct 23 and Oct 19 for the homework.
(Oct 12, 2017) I have a cleaner version of
the proof of Euler's pentagonal
number theorem that I presented roughly last time. A proof of this
this result also appears in the recommended book "How to Count".
(Oct 19, 2017) I wrote up a full solution to
the problem that we discussed in class today.
(Oct 20, 2017) I haven't had any time this week to finish the homework assignments.
I'll start sending back your assignments. I pulled together some examples of
what I was seeing to show that there was a range of "just great" (clear,
complete, correct) to "really difficult to read."
Here is a
pdf
where I pulled a few of these together.
(Oct 23, 2017) I uploaded feedback on your assignments. I won't be able to
give quite so detailed remarks on future assignments, instead I will just
give you a grade based on the types of remarks that I gave you here.
I will give you until next Monday (Oct 30) to update your homework 1 (if you want).
If you want to leave it as is, I will just grade the one that I have.
Just as a reminder, I've extended the due date for the second assignment until
Oct 25.
(Oct 31, 2017) I just posted the
3rd hw assignment (mostly on) exponential
generating functions. It is due Nov 13 (but FYI, we also have the midterm
this Thursday, Nov 2 - Monday, Nov 6)
(Nov 2, 2017) The midterm is available starting from 3pm today.
It only has 3 problems. As you do this exam, I would like you to keep track
of what references you consult (web pages, books, etc.). Please hand in
the list with your midterm. Besides consultations with me,
would like you to work alone on this assignment. I will have extra office
hours for this class 11am-12pm on Friday November 3.
(Nov 17, 2017) Its late, but I want to post a
version of the homework tonight,
but it could potentially have some corrections.
(Nov 30, 2017) The final is posted. You have until December 8 to finish. If you have an early final schedule, I can extend the deadline, but I need to know in advance.
(Dec 2, 2017) I will hold office hours at the regularly scheduled times on Monday 12pm and Thursday 10am the week of December 4-8.
(Dec 4, 2017) Someone pointed out to me that question 3 did not mention that the expression we were looking was for colorings of the graph with k colors. I have corrected this.