Math 3U03 -- Combinatorics
(Fall 2017)

This course is an introduction to combinatorics

---

News (Last Updated: April 6, 2017)

Below is a summary of what we did in class, plus any relevant news and/or information.

• April 6, 2017 The last day of classes. We finished the course by discussing Steiner Triple Systems (Section 10.3).
• April 4, 2017 We started our discussion of Chapter 10 on block design. I touched upon topics in Sections 10.1 and 10.2.
• April 3, 2017 We finished Chapter 7 by going Section 7.4 which describes how to solve the Probleme des Menages.
• March 30, 2017 We went over Section 7.2 which describes how to count the number of elements in exactly k subsets. I also proved the formula for the Stirling numbers of the second kind. The projects were also due today.
• March 28, 2017 We started Chapter 7 today. I explained the generalized prinple of inclusion-exclusion, and I used it to give a new proof of the dearrangment formula. Please take a moment to fill out the course evaluation on this course at evals.mcmaster.ca
• March 27, 2017 We finished Chapter 6 today. Today I described how to go from a non-homogeneous linear recurrence relation to its general form without going through all the steps of the symbolic differentation.
• March 23, 2017 We went over Section 6.4 on symbolic differentation as technique to solve recurrence relations.
• March 21, 2017 Today I explained how to use the characteristic equation to solve some families of recurrence relations (see Section 6.3).
• March 20, 2017 In today's class we learned how to use generating functions to solve recurrence relations (see Section 6.2).
• March 16, 2017 We started Chapter 6. I went over Section 6.1 which defined the basics of recurrence relations. I also returned the second midterm.
• March 14, 2017 SNOW DAY!
• March 13, 2017 Midterm 2 was today.
• March 9, 2017 We went over Section 5.5 which explained how to use generating functions for ordered strings, and how to use generating functions to count the number of permutations.
• March 7, 2017 We discussed some more results about generating functions (see Sections 5.3 and 5.4). I also explained how to use Wolfram Alpha to find the required coefficients.
• March 6, 2017 Today we started on Section 5.3; I explained how to use generating functions to solve some counting problems.
• March 2, 2017 We finished our review of power series today (see Sections 5.1/5.2). I also handed back assignment 4.
• February 28, 2017 We started Chapter 5 today which focuses on generating functions. I reviewed some of the background on power series and partial fractions that we will require in this chapter.
• February 27, 2017 We finished Chapter 4 today. We discussed Stirling numbers of the second kind, and looked at some of their properties.
• February 16, 2017 We looked at Section 4.3 on partitions of numbers and their connection to distribution problems.
• February 14, 2017 We finished Section 4.2 by focusing on the problem of placing unlabelled balls into labelled urns.
• February 13, 2017 We started Chapter 4 on distribution problems. We solved some basic distributions using our known techniques. I covered Section 4.1 and some of Section 4.2.
• February 9, 2017 Today we talked about multinomial coefficients (see Section 3.6). I also handed back the third homework assignment and the first midterm.
• February 7, 2017 We went over Section 3.5 on bars and stars to give an alternative combinatorial description of binomial coefficients. I also worked out an example involving the Catalan numbers.
• February 6, 2017 Today was Midterm 1.
• February 2, 2017 We went over Sections 3.3 and 3.4 today; in particular, we proved the binomial theorem, and then provided a number of useful identities involving binomial coefficients.
• January 31, 2017 Today we went to the library to learn about citing mathematical papers and how to find resources for your paper. Here are the copies of the SLIDES 1 and SLIDES 2 used in the presentation.
• January 30, 2017 We started our discussion of Chapter 3 on binomial coefficients. Today we went over the material of Section 3.1 (basic properties), and I also did an example of a poker hand (Section 3.2). Assignment 1 was returned.
• January 26, 2017 We finished up Section 2.7. I introduced the Stirling numbers of the first kind.
• January 24, 2017 Today I introduced the cycle notation to describe permutations. I also explained how to count the number of circular permuations, and how to use this to count the number of permuations of a fixed cycle type (see Section 2.7)
• January 23, 2017 I explained how to find the number of permutations of [n] of size k. We used this idea, and previous ideas, to count the number of tic-tac-toe games (see Sections 2.5 and 2.6).
• January 19, 2017 We looked at the problem sitting people around a table (one version), and we looked at Legendre's theorem about the number of prime divisors of n! (see Sections 2.3 and 2.4)
• January 17, 2017 Today I discussed the addition principle, and gave some examples on how to use this principle (see Section 2.2). I also introduced permuations (see Section 2.3).
• January 16, 2017 I introduced the multiplication principle, and I gave some examples of how to use this principle (see Section 2.1).
• January 14, 2017 We are MOVING to ABB 164 starting on Monday!
• January 12, 2017 Today we finished Chapter 1 by going over the idea of a combinatorial proof again (see Section 1.6). I also gave out the first homework. Please note the following changes in the assessment of the homework:
  • Your homework will be graded as follows:
    1. You will receive 1pt for every question you attempt.
    2. For every assignment, 2 or 3 questions will be picked at random, and they will graded in detail (e.g., you are required to write complete mathematical proofs). These questions will be graded out of 5 pts using the rubric described in the course handout.
    I needed to make this change since it would be not possible to grade all the assignments in a timely manner. My plan is to post solutions to all problems so that you can check your other answers as well.
• January 10, 2017 In today's class I introduced the pigeonhole principle and went over some classical examples. See Section 1.5.
• January 9, 2017 Today I did a quick review of Sections 1.2, 1.3, and 1.4 on some basic set theory and counting.
• January 5, 2017 Today was the first day of class. I introduced the course, and discussed the idea of a combinatorial proof.

Useful Links

For more information on proofs, the following notes may help:

• Guide to writing proofs
  A handout on writing proofs I wrote for algebra in 2010.
• A guide to writng proofs
  A nice short guide to writing mathematics by Kevin P. Lee.

Here is an interesting thread that points to other combinatorics books. Send me your favourite links!

• Combinatorics Books Discussion

Official Polices

1. Policy on Academic Ethics. You are expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. Academic credentials you earn are rooted in principles of honesty and academic integrity.

Academic dishonesty is to knowingly act or fail to act in a way that results or could result in unearned academic credit or advantage. This behaviour can result in serious consequences, e.g. the grade of zero on an assignment, loss of credit with a notation on the transcript (notation reads: Grade of F assigned for academic dishonesty), and/or suspension or expulsion from the university.

It is your responsibility to understand what constitutes academic dishonesty. For information on the various types of academic dishonesty please refer to the Academic Integrity Policy, located at: http://www.mcmaster.ca/academicintegrity/

The following illustrates only three forms of academic dishonesty:

• plagiarism, e.g. the submission of work that is not one's own or for which other credit has been obtained.
• improper collaboration in group work,
• copying or using unauthorized aids in tests and examinations.

2. Policy regarding missed work. If you have missed work, it is your responsibility to take action. If you are absent from the university for medical and non-medical (personal) situations, lasting fewer than 3 days, you may report your absence, once per term, without documentation, using the McMaster Student Absence Form (MSAF). See Requests for Relief for Missed Academic Term Work

Absences for a longer duration or for other reasons must be reported to your Faculty/Program office, with documentation, and relief from term work may not necessarily be granted. In Math 3U03, the percentages of the missed work will be transferred to the final examination. Please note that the MSAF may not be used for term work worth 25% or more, nor can it be used for the final examination.

3. Student Accessibility Services. Students who require academic accommodation must contact Student Accessibility Services (SAS) to make arrangements with a Program Coordinator. Academic accommodations must be arranged for each term of study. Student Accessibility Services can be contacted by phone 905-525-9140 ext. 28652 or e-mail sas@mcmaster.ca. For further information, consult McMaster University's Policy for Academic Accommodation of Students with Disabilities.

4. Important Message. The instructor and university reserve the right to modify elements of the course during the term. The university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes.

Course Information

Instructor: Adam Van Tuyl

Office: Hamilton Hall 419
Office Hours: M: 1:30-2:20, Th: 10:30-11:20
Email: vantuyl@math.mcmaster.ca

Place and Time:

Class: MTh 12:30-1:20 and T 1:30-2:20 in ABB 164

Textbook:

How to Count
by Robert Beeler
(You can obtain a free eBook through the McMaster library)

Homework Assignments

Homework is given out every Thursday, and will be due, at the beginning of class, the following Thursday. Assignments must conform to the guidelines in the course outline. Your homework will be graded as follows:

1. You will receive 1pt for every question you attempt.
2. For every assignment, 2 or 3 questions will be picked at random, and they will graded in detail (e.g., you are required to write complete mathematical proofs). These questions will be graded out of 5 pts using the rubric described in the course handout.

Assignments are posted below.

Assignment 1 (Due: Jan. 19)

Sec. 1.2: 1.2.7
Sec. 1.3: 1.3.13, 1.3.16
Sec. 1.4: 1.4.6, 1.4.7
Sec. 1.5: 1.5.8, 1.5.10
Sec. 1.6: 1.6.4, 1.6.7

Assignment 2 (Due: Jan. 26)

Sec. 2.1: 2.1.19, 2.1.24
Sec. 2.2: 2.2.8, 2.2.13
Sec. 2.3: 2.3.9, 2.3.11
Sec. 2.4: 2.4.7, 2.4.9

Assignment 3 (Due: Feb. 2)

Sec. 2.5: 2.5.6, 2.5.8, 2.5.9
Sec. 2.6: 2.6.8, 2.6.10
Sec. 2.7: 2.7.13, 2.7.15, 2.7.18, 2.7.20

Assignment 4 (Due: Feb. 16)

Sec. 3.1: 3.1.15
Sec. 3.2: 3.2.9
Sec. 3.3: 3.3.6, 3.3.7
Sec. 3.4: 3.4.7
Sec. 3.5: 3.5.13
Sec. 3.6: 3.6.16, 3.6.22
Bonus: A problem is incorrect in 3.4. Find it and explain why.

Assignment 5 (Due: March 2)

Sec. 4.2: 4.2.12, 4.2.13, 4.2.16, 4.2.18, 4.2.19
Sec. 4.3: 4.3.15, 4.3.17(i)

Assignment 6 (Due: March 9)

Sec. 4.3: 4.3.18, 4.3.20
Sec. 5.1: 5.1.11 (i)
Sec. 5.2: 5.2.8, 5.2.10, 5.2.11, 5.2.15

Assignment 7 (Due: March 23)

Sec. 5.3: 5.3.9, 5.3.13, 5.3.14, 5.3.15
Sec. 5.4: 5.4.6, 5.4.7, 5.4.10
Sec. 5.5: 5.5.4
Note: You will need to use a computer algebra system; Also, in 5.4.6, the first equation should be x_1+3x_2+5x_3+7x_4 = 15.

Assignment 8 (Due: March 30)

Sec. 6.1: 6.1.11(ii), 6.1.20
Sec. 6.2: 6.2.6, 6.2.10
Sec. 6.3: 6.3.11, 6.3.15
Sec. 6.4: 6.4.9,6.4.15*
Sec. 6.5: 6.5.21*
* Use a computer algebra system

Assignment 9 (Due: April 6)

Sec. 7.1: 7.1.8, 7.1.16*
Sec. 7.2: 7.2.4*, 7.2.5
Sec. 7.3: 7.3.7
Sec. 7.4: 7.4.7
* Use a computer algebra system

Handouts

All class handouts are available as PDF files.

Course Information
Course handout from first day of class

Library Slides 1 and Slides 2
Slides from Library Presentation

Grading Scheme

Your final mark is broken down as:

Homework = 20%
Midterm (x2)= 30%
Project = 10%
Final Exam = 40%

Important Dates

Jan. 4, 2017
Second semester classes begin

Feb. 6, 2017
Midterm 1

Feb. 9, 2017
Project topic due

Feb. 20-25, 2017
Fall Midterm Break (no classes)

Mar. 9, 2017
Project draft due

Mar. 10, 2017
Last day for cancelling courses without failure by default

Mar. 13, 2017
Midterm 2

Mar. 30, 2017
Project Due

Apr. 6, 2017
Second semester classes end

Apr. 21, 2017
Final Exam (9:00AM)