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