Math 4160 - Combinatorial Mathematics - Zabrocki

Warning: MathJax requires JavaScript to process the mathematics on this page.
If your browser supports JavaScript, be sure it is enabled.

WARNING: This web page from 2012! OUT OF DATE! The web page for this class offered in 2014 is here

Math 4160 - Combinatorial Mathematics

Professor: Mike Zabrocki
email:

Meetings: Tues-Thurs 2:30-4pm HNE B15
Office hours: TEL 2028 - Monday 12:30-2:30pm, Thursday 4-5pm
Textbook: Bijective Combinatorics - Nicolas A. Loehr

What is the rule?

Course description:

Calendar copy: 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.

The grade for this course will mostly be based on homework assignments. You may work together on these assignments, but I want you to hand in your own work (YOU must work on these problems and they will be compositions so I expect your answers to be original even if you worked with someone).

assignments	55%
midterm	20%
final	25%

Course schedule

Lecture	dates	Topic/sections in text	notes/relevant handouts
1	Thurs, Sept 6	sums, Stirling numbers, addition/multiplication principle
2	Tues, Sept 11	from $\sum_{i=1}^n i = n(n+1)/2$ to $\sum_{i=1}^n i^r = \sum_{k=1}^r S(r,k) (n)_k$
3	Thurs, Sept 13	basic counting - $n!$, ${n \choose k}$, $S(n,k)$, $s'(n,k)$, $B(n)$
4	Tues, Sept 18	basic counting, cards and combinatorial identities
5	Thurs, Sept 20	distributions and multichoose
6	Tues, Sept 25	proving combinatorial identities, beginning of generating functions
7	Thurs, Sept 27	generating functions	Hw #1 due, some problems for next time, Hw #2 assigned
8	Tues, Oct 2	more generating functions
9	Thurs, Oct 4	generating functions and combinatorics	hw #1 returned
10	Tues, Oct 9	review for midterm	note office hours 4-5pm today
11	Thurs, Oct 11	Midterm - take home	office hours cancelled today, available Monday 10:30am - 4:30pm
12	Tues, Oct 16	generating functions, exponential generating functions, partitions	Hw #2 due, midterm due
13	Thurs, Oct 18	partitions, exponential generating functions and combinatorics	matching partition gfs, Hw #3 assigned Oct 20 (revised Oct 28)
14	Tues, Oct 23	partition generating functions	matching partition gfs, partition gfs
15	Thurs, Oct 25	partition generating functions, introduction to groups	partition gfs, midterm returned
16	Tues, Oct 30	coloring a cube, motions of a triangle/square as a group	homework #2 returned
	Thurs, Nov 1	no class
17	Tues, Nov 6	the group of motions of the cube, group actions	Hw #3 due
18	Thurs, Nov 8	group actions, equivalence relations, the orbit-stabilizer theorem
19	Tues, Nov 13	Justified the orbit-stabilizer theorem	Hw #4 assigned
20	Thurs, Nov 15	Burnside's Lemma, Polya's theorem	Returned HW #3
21	Tues, Nov 20	necklaces, permutations of a given cycle type
22	Thurs, Nov 22	coloring spoke graph, permutations of a given cycle type
23	Tues, Nov 27	remarks about hw#4, permutations
24	Thurs, Nov 29	an application of Burnside's lemma, Catalan numbers and Dyck paths	Hw #4 due

Announcements:

(Tuesday, September 4, 2012) - I tend to fill my course web pages as a diary rather than tell you precisely what we will cover for the rest of the term. You should follow changes made to this page and check back on a regular basis. You might want to check out the course page I have for Math 4160 the last time I taught it (2003). I was using a different textbook then and so the topics that we cover this time might be different.

(Thursday, September 13, 2012) - I forgot to mention that I posted my office hours on the web page. They are listed above (M1-3,Th4-5) and on the syllabus that I gave you today. I updated the first assignment with a few corrections and a change out of many of the problems. I think it is correct now.

(Thursday, September 20, 2012) - After class on Tuesday I did find an error on the homework assignment (thanks to Cynthia) and it is now corrected. I posted lecture notes for the last two lectures. I may not have gotten everything, but I tried to get the most important parts. I will have to change my office hours to Monday 12:30pm-2:30pm (from 1-3pm) because roughly every other week I have a talk to go to at 2:30pm.

(Thursday, September 27, 2012) - So I was surprised that basics of complex numbers isn't in everyone's vocabulary, so here is my quick summary: $i = \sqrt{-1}$ so $i^2 = -1$; $e^{i \theta} = cos(\theta) + i sin(\theta)$ so therefore $e^{\pi i} = cos(\pi) + i sin(\pi) = -1$. We use the notation $\zeta_r = e^{2 \pi i/r}$ and it is called an $r^{th}$ root of unity and $(\zeta_r)^r = 1$ (e.g. $\zeta_2 = -1$ satisfies $(-1)^2 = 1$). Also, $1 + \zeta_r + \zeta_r^2 + \cdots +\zeta_r^{r-1} = 0$.

(October 4, 2012) I posted notes from the last class and at the end I gave you 14 problems in the style of what we were discussing in class. I'll throw a few more exercises for practice and I will put them at the end of the notes as soon as I get the chance. As discussed in class the homework will be due Tuesday, October 16th rather than on October 11th as I had originally posted.

(October 4, 2012) I will cancel my office hours on October 11th and hold them on October 9 from 4-5pm. This seems more practical given that the midterm is on the 11th.

(October 6, 2012) I have decided to make the midterm take home rather than in class. I prefer a take home midterm, but had scheduled the in class test because I knew that I needed to be out of town on the 11th. That being said, "No class on Thursday" (sorry, I have to go give a talk in Philadelphia), but I will post the midterm by that date with instructions.

(October 6, 2012) The practice problems that I have put at the end of the notes for Oct 4 should be an indication about what is expected of you for an exam. There are only 4 problems that have 4 parts (a)-(d). The four parts increase in difficulty and by part (d) usually require you to learn something that I haven't covered explicitly in this class in order to solve them and hence might take some time to solve. A take home exam will mostly be at level (b) and (c). Be prepared to ask questions in class about these problems for Tuesday. Try them out and make sure that you know how to do as many as you can from the sources of (i) the homework (ii) the practice from Oct 2 and 4 notes (iii) the book (iv) my old web page from the last time that I taught the class.

(October 11, 2012) The take home exam is almost ready to post, but I think it would be a mistake for me to do it now (it is a little after midnight) and find errors later. I will try to post it as early as I can, but it might be the evening of the 11th if I can't get an internet connection earlier.
I am placing online now notes from Tuesday's class with solutions to most of the problems we discussed (there may be updates in the future on these notes). In those solutions I included the types of details that I expect to see in a full explanation. Please use these problems as examples for your own work.
I will include instructions about expectations for a take home exam. I don't want you to consult people other than me. I will answer whatever questions you may have, but don't ask other people or other websites for the answers. Ask me!
I will be in my office Monday starting at around 10:30am. I will be available most of the day, but since I teach in the evening I probably won't be available after 4:30pm.

(October 11, 2012) As I expected I was out of internet connection most of the day. I've posted the midterm. I've tried to make the instructions as clear as possible about my expectations of working with other people. If you need help, ask me. If you reference any sources, please list them on the second page of the exam. I will be available in my office Monday October 15, but it is a good idea to let me know that you are coming.

(October 12, 2012, 9am) Someone asked me about the 4th question something I wrote was very unclear about it and it had more than one typo. I just corrected it.
(6:15pm) I tried to make the question even clearer because there was still a question about the way it was stated.

(October 22, 2012) I noticed that some of you did not hand in a signed cover sheet where I asked you to detail the references you used to complete the midterm. I am not handing those back until I get a copy.

(October 23, 2012) There was an error (or two) on the homework. It has been corrected.

(October 23, 2012) The registrar's office has released a tentative date for our exam as Saturday, December 15, 2012 at 9am. I'm not sure if we will have a take home exam.

(October 27, 2012) Please check the pdf of the homework for a correction to the assignment (again). If $n$ is odd, then the sum includes a term ${n \choose n+1} = 0$, but this is ok.

(October 29, 2012) Since classes aren't being held on Thursday, I won't be holding my office hours Thursday afternoon either. If you need to see me then, please either schedule an appointment for another time (I can make Tuesday at 4pm this week).

(November 13, 2012) I'm not quite ready to post the 4th hw assignment. I posted a draft because I am still working on the last bit so at least you can take a look. I should have the final version ready by tomorrow.

(November 14, 2012) I updated the homework assignment.

(November 16, 2012) While we have an exam date scheduled for this class, the final exam will be take home. I will give it to you either the last day of class or just after and it will be due by Friday, December 14.

(November 22, 2012) I corrected several typos in each of the last three homework problems. There was also a missing $u$ in the differential equation that I said that $B(x,u)$ satisfied in class.

(November 30, 2012) I will have office hours December 4 from 12-1:30pm. I will also be available Wednesday December 5 from 10am-12pm.

(December 5, 2012) Question 9 on the final was worded strangely and there was an error on question 4 and 5 that I have now corrected. Please take a look. I will send an email about it shortly.

(December 9, 2012) I expect to be in my office Tuesday December 11, from 11-12:30pm.

(December 10, 2012) I've had two people ask for some additional time for office hours. I can only offer 11-12pm Thursday December 13.

(December 11, 2012) WARNING! I will leave at 2:30pm on Friday afternoon (when the finals are due). Do not try to submit assignments after this time. You may submit your exam any time before this by slipping it under my door if I am not there.

(January 7, 2012) Sorry, but the final grades are currently being held up (otherwise I would have submitted them last week). I will try to let you know as I find anything out about the expected arrival time but I currently don't know for sure.

Handouts:

(Thursday, September 13, 2012) Notes from the first two lectures
(Thursday, September 13, 2012) First assignment

(Thursday, September 20, 2012) Notes from Sept 13-18
(Thursday, September 27, 2012) Notes from Sept 20-25
(Thursday, September 27, 2012) Some problems to think about for next time
(Thursday, September 27, 2012) Second assignment (due Oct 16)
(Thursday, September 27, 2012) Notes from Sept 27
(Thursday, October 4, 2012) Notes from Oct 2
(Saturday, October 6, 2012) Notes from Oct 4
(Thursday, October 11, 2012) Notes from Oct 9
(Thursday, October 11, 2012) Take home midterm
(Thursday, October 18, 2012) Notes from Oct 16
(Saturday, October 20, 2012) Notes from Oct 18
(Saturday, October 20, 2012) Third assignment (due Nov 6) (Note: revised version Oct 28)
(Saturday, October 20, 2012) worksheet from class Oct 18
(Tuesday, October 23, 2012) worksheet from class Oct 23
(Sunday, October 28, 2012) Notes from Oct 23
(Sunday, October 28, 2012) Notes from Oct 25
(Thursday, November 1, 2012) Notes from Oct 30
(Thursday, November 8, 2012) Notes from Nov 6
(Saturday, November 10, 2012) Notes from Nov 8
(Wednesday, November 14, 2012) Fourth assignment (due Nov 29)
(Friday, November 16, 2012) Notes from Nov 13
(Saturday, November 17, 2012) Notes from Nov 15
(Sunday, November 25, 2012) Notes from Nov 20
(Monday, November 26, 2012) Notes from Nov 22
(Thursday, November 29, 2012) Take home final exam - due December 14 at 2:30pm
(Thursday, November 30, 2012) Notes from Nov 27