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.

This is an older course web page left as an archive from 2014. There is a more recent web page from Fall 2017.

Math 4160 - Combinatorial Mathematics

Professor: Mike Zabrocki
email:

Meetings: Tues-Thurs 2:30-4pm TEL 0005
Office hours: Ross N518 - TBA
Textbook: (optional) How to count by Allenby and Slomson, class notes,

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	Tues, Sept 9	sums, Stirling numbers, addition/multiplication principle
2	Thurs, Sept 11	sums of rising factorials, Stirling numbers of the first kind $s'(n,k)$
3	Tues, Sept 16	a proof that $x^n = \sum_{k=1}^n (-1)^{n-k} S(n,k) (x)^{(k)}$ - $n!$, ${n \choose k}$, $S(n,k)$, $s'(n,k)$, $B(n)$, $n^k$, $(n)_k$, $(n)^{(k)}$
4	Thurs, Sept 18	basic counting, cards and combinatorial identities	HW1 available as of Sept 20
5	Tues, Sept 23	rising factorial, summation solution, distributions
6	Thurs, Sept 25	choose and multichoose, proving combinatorial identities, sequences and generating functions
7	Tues, Sept 30	intro to generating functions (video + ex 1-8 on worksheet), paths and combinatorial identities
8	Thurs, Oct 2	proving combinatorial identities w/paths, coefficients in gfs	HW #1 due
9	Tues, Oct 7	more coefficients in gfs, combinatorial interpretations
10	Thurs, Oct 9	more g.fs, combinatorics with gfs	HW2 assigned
11	Tues, Oct 14	Fibonacci and Lucas identities with g.fs
12	Thurs, Oct 16	complex numbers, partition generating functions
13	Tues, Oct 21	exponential generating functions	HW2 due,
14	Thurs, Oct 23	exponential generating functions	take home midterm
15	Tues, Oct 28	solving problems	midterm due
	Thurs, Oct 30	reading half of a "week"	hw 3 assigned
16	Tues, Nov 4	groups and symmetries of the square and triangle
17	Thurs, Nov 6	groups, homomorphisms, group actions, symmetries of 3d shapes
18	Tues, Nov 11	groups, actions, orbit stablizer theorem	hw 3 due
19	Thurs, Nov 13	relations, equvialence classes
20	Tues, Nov 18	Burnsides Lemma and Polya's theorem
21	Thurs, Nov 20	Burnsides Lemma and Polya's theorem
22	Tues, Nov 25	Polya's theorem and necklaces
23	Thurs, Nov 27	partial orders and Möbius inversion	hw 4 due
24	Thurs, Dec 4	final exam, necklaces, a research problem

Announcements:

(Tuesday, September 9, 2014) - 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 (2012). I will leave my course material from then online and I expect that I will follow the notes that I took from that course with a few modifications. The bookstore has the textbook from last year listed as required ("How to count" by Allenby and Slomson). You can use it if you want, it should be a very good reference.

(Monday, October 20, 2014) - I got a message about a couple of mistakes in the homework and I have corrected them. If you are get an answer that disagrees with mine it can be because I made the mistake. In this case, it looks like I accidentally took the wrong coefficient to arrive at my answer (but it is not clear). There was another typo in the formula that I expected you to prove. PLEASE make sure that you correct my errors, because you will lose marks for "proving" the wrong result.

(Monday, October 20, 2014) - I announced on Tuesday last week that we would have a take home midterm but I never posted on this web page. It should happen on Tuesday to be due Thursday.

(Tuesday, October 21, 2014) - The take home midterm won't be ready until tonight so I instead I will wait until Thursday to post it and it will be due Tuesday the 28th.

(Thursday, October 30) - I had expected to be able to finish homework 3 and post it earlier but I am just getting it up now. I am sure you want to spend your reading week working on this, but I recommend getting a start on it now.

(Thursday, October 30) - I had an announcement on Tuesday in class that I forgot to make. While I spent a lot of time reading and making comments on your second homework, I didn't read very carefully or make comments on the last problem. In fact, I just gave 4 pts if you did the problem (and everyone did).

(Friday, November 7) - I posted a second version of the homework with a bit of a hint on question 2. I decided not to just replace the previous version because I also edited a little question 2 to make it clearer. In the first version I wrote "and the last three appear an even number of times" but I had to think a few times if it was clear and does it mean 'in total the last three appear an even number of times' or does it mean 'the last three each appear an even number of times.' I settled on the latter feeling that it most clearly reflected the language that was there in the first version, but I admit that it could be read either way and I would not argue one reading over another (make sure your solution is clear or give me both solutions!). I have now made it clearer by inserting a few words and if you follow the new reading then I have also included the number of words of length 10 which satisfy this condition in order to give you some confidence that your answer matches mine. I still expect you to tell me the number of words of length 20 satisfying these conditions.

(Tuesday, November 11) - For next time I asked you for next time to give me the number of different colorings of the vertices of a square with Red, Green and Blue that are different when they are acted on by the group $G$ where $G$ is one of four different groups.
$\{ e \}$
$\{ e, R_{90}, R_{180}, R_{270} \}$
$\{ e, R_{90}, R_{180}, R_{270}, F_V, F_H, F_{D1}, F_{D2} \}$
$\{ e, F_V \}$

Two colorings $c_1$ and $c_2$ are the same under the group $G$ if there is an element $g$ in the group $G$ such that $g \bullet c_1 = c_2$.

(Wednesday, November 26) An FYI, I edited slightly question number 7 to remove the words "with black and white" because it was unclear. At Tuesday's class I asked you to answer a question for Thursday, that is: How many ways are there of putting 8 beads on a necklace using $k$ colors assuming that adjacent beads cannot be the same color.

(Thursday, December 4) I posted notes from the last class because I never covered posets and inclusion-exclusion in this way in 2012. Unfortunately I didn't finish them yet so I am posting a draft which I intend to revise. I will post the exam at 2:30pm. Please don't discuss the exam with anyone but me. I offer you lots of trust on this assignment instead of an in-class exam and I will only continue as long as I feel like that there is an understanding that you are to treat the final as exam conditions.

(Friday, December 5) I've updated the notes on partial orders, Mobius inversion and inclusion-exclusion. Its not done yet, but I will add more detail when I have time.

(Monday, December 7) I've been asked about problem number 3(b). You do not need to list all elements of the group, I will be happy if you just list a representative of each cycle type and tell me how many there are of each type.

(Wednesday, December 10) I've corrected a few minor typos on the final as I've found them. The one that might have been a little misleading is 2 (c) that should have read '$\left< x \right>_r$ for $r \geq 1$ ' instead of ' $\left< x \right>_3 , \left< x \right>_4, \left< x \right>_5$ '.

(Thursday, December 11) The weather outside is frightful. I will be in my office unless the university closes. You can email me your final exam too.

(Thursday, December 11) One more thing... (and this is one to keep with you forever).
NEVER, NEVER, EVER explain an equality with a calculation by reducing it to $$1=1$$ or $$\frac{u}{1-x} = \frac{u}{1-x}$$ or any other equality of the form $A=A$. Let me try to explain why:
Say you have a statement which is either TRUE or FALSE, and through a sequence of deductions you conclude $A=A$. Then what have you shown? You have shown that $A=A$. You have NOT shown that the original equality is TRUE. One reason is because "FALSE implies TRUE" is "TRUE." That means you could have started with a FALSE statement and derived $A=A$ (which is TRUE, has always been TRUE, and never needed justification). That means it could be the case that the statement you are trying to prove is FALSE.

I know what you are thinking to yourself right now: TL;DR and "its too late now, the final is due today." (sigh)

(Thursday, December 11) While I accept the final versions electronically, please convert it into PDF before you send it (export as pdf should be an option in the file menu...). Other formats do not generally come though on my end.

Handouts:

(Tuesday, September 9, 2014) Notes from 2012
(Thursday, September 11, 2014) Notes from Sept 9
(Saturday, September 20, 2014) Notes from Sept 11 (the wrong ones were posted before)
(Wednesday, September 17, 2014) Link to Terence Tao's Google+ post on induction
(Tuesday, September 23, 2014) Notes from Sept 16 (rougher and shorter than other notes)
(Saturday, September 20, 2014) Notes from Sept 18
(Saturday, September 20, 2014) Homework 1 due October 2
(Thursday, September 25, 2014) Notes from Sept 23
(Thursday, October 2, 2014) Notes from Sept 25
(Thursday, October 2, 2014) video 1 and video 2 that we watched in class
(Thursday, October 2, 2014) The set of videos and text about generating functions
(Thursday, October 2, 2014) Worksheet on generating functions
(Thursday, October 2, 2014) video 3 that we watched in class
(Saturday, October 9, 2014) Homework 2 due October 21
(Thursday, October 23, 2014) Take home midterm due October 28
(Thursday, October 20, 2014) Homework 3 (older version) due November 11
(Friday, November 7, 2014) Homework 3 (updated) due November 11
(Monday, November 17, 2014) Homework 4 due November 27
(Thursday, December 4, 2014) Notes from Dec 27 (to be revised)
(Thursday, December 4, 2014) Final exam - Due Dec 11, 2014 at 2:30pm