MATH 331, Section 201: Problem Solving

The final exam will be on Tuesday, April 17 from 8:30–11:00 AM in room Math 105 (Mathematics building). For the exam, all you need to bring is your student ID and something to write with. Remember that there will be no makeup exam. Fair warning: you will not be permitted to leave the exam room during the final exam.

I have posted the formula sheet that will be included with the final exam.

For the exam, all the paper you need will be provided for you. No notes, books, calculators, or other aids are allowed; please do not bring cell phones, pagers, alarm watches, or anything else that would make noise during the exam. You might wish to ensure that you are familiar with UBC's Academic Regulations pertaining to misconduct during exams.

Course information

Instructor: Prof. Greg Martin
Office: MATH 212 (Mathematics Building)
Email address: [an error occurred while processing this directive]
Phone number: (604) 822-4371
Office hours: Wednesdays 3–4 PM and Fridays 11 AM–noon

Course description: This course is intended for honors students. The book generatingfunctionology by Herbert S. Wilf is an introduction to generating functions and their applications to solving combinatorial enumeration problems. In other words, we will learn how to form a power series (for example) from a sequence of numbers we're interested in, often a sequence that counts the number of objects with particular properties, and investigate how knowledge of the power series can yield exact formulas or other information about the sequence itself. The text also includes some of the elementary theory of power series considered as functions of a complex variable. This is mainly needed in the final chapter, on asymptotics, and is the most natural approach to such questions.

Use of the web: After the first day, no handouts will be distributed in class. All homework assignments and other course materials will be posted on this course web page, http://www.math.ubc.ca/~gerg/teaching/331-Winter2007.

You may access the course web page on any public terminal at UBC or via your own internet connection. Accounts for the Mathematics department undergraduate computer lab (located in the MSRC building) will be given to any enrolled student who requests one; please email or visit the instructor to request an account.

All documents will be posted in PDF format and can be read with the free Acrobat reader. You may download the free Acrobat reader at no cost by following the link.

Evaluation: There will be six homework assignments and a final exam (no midterms). The course mark will be computed as follows:

• Homework average: 50 percent
• Final exam: 50 percent
  

Homework will be due every second Monday, starting January 15, at the beginning of class. Late homework will not be accepted. To account for forgetfulness or unforseen circumstances, each student's lowest homework score will be dropped. Missed homework will not be excused beyond this point, except for documented medical reasons.

Your homework will be marked on correctness, completeness, rigor, and elegance. A correct answer will not earn full marks unless it is completely justified, in a rigorous manner, and written in a logical manner that is easy to follow and confirm. Students are allowed to consult one another concerning the homework problems, but your submitted solutions must be written by you in your own words. If two students submit virtually identical answers to a question, both can be found guilty of plagiarism.

You are welcome to use the “solutions” in the back of the textbook as hints, but remember that your homework solutions must be written by you in your own words. Also, be warned that often those “solutions” are not complete as written.

Downloads and links

• Homework #1 (due Monday, January 15). The homework was first posted with the wrong page numbers for the problems; this has been corrected. Also, I took out one of the parts of problem I.
• Homework #2 (due Monday, January 29).
• Homework #3 (due Monday, February 12). A typo in problem V has been fixed: “n-tuples” was corrected to “m-tuples”. A few typos in problem IX weren't fixed in time, but I've corrected them now anyway.
• Homework #4 (due Monday, March 5). There was a typo in problem V(b): a factor of 1/n! was omitted from the right-hand side. I've posted the corrected version.
• Homework #5 (due Monday, March 19). I corrected typos in problems I (wrong page number) and IV (X corrected to A). I also removed the Bonus Problem, which will appear on Homework #6. Finally, the conclusion of problem IV was wrong, but I've gotten the right formulation now. The corrected version is now posted.
• Homework #6 (due Monday, April 2). There were two typos in problem II: one was just a wrong page number, and the other was mistyping (1+u)² as (1+u²). There were also mistakes in problem III: in part (a), the φ(0)ⁿ should not be there, and in the first equation in part (b), the 2^m should not be there. Also, problem VIII(b) now refers more specifically to problem III(b). The currently posted version has these corrections.


• The math department's announcement of NSERC USRAs for the summer of 2007
• The Niven Student Lecture, Tuesday, March 6, 2007 at 3:30 PM


• A summary of binomial coefficients
• A summary of complex numbers
• A description of Gosper's Algorithm, which is mentioned in Section 4.4 of Wilf
• A description of the Jacobi Triple Product formula; see in particular equation (5), although you might need to click on “q-series” above equation (3) to explain the notation
• A description of partitions
• A summary of permutations

Reading assignments

• for Wednesday, January 10: pages vii–viii and 1–8
• for Friday, January 12: pages 9–16
• for Monday, January 15: pages 17–23
• for Friday, January 19: Section 2.1 (pages 30–33)
• for Monday, January 22: pages 33–37
• for Wednesday, January 24: page 38–equation (2.3.4) on page 42
• for Friday, January 26: pages 42–45
• for Monday, January 29: pages 46–49
• for Wednesday, January 31: page 50–end of Section 2.5
• for Friday, February 2: page 73–end of Example 1 on page 77
• for Monday, February 5: Section 3.4
• for Wednesday, February 7: Section 3.6
• for Friday, February 9: Sections 3.9 and 3.10
• for Monday, February 12: Example 2 on pages 77–78 and Sections 3.5, 3.7, and 3.8
• for Wednesday, February 14: Sections 3.11–3.13
• for Friday, February 16: pages 92–93 and Section 3.16
• for Monday, February 26: Sections 4.1 and 4.6
• for Wednesday, February 28: pages 118–121
• for Friday, March 2: pages 122–125
• for Monday, March 5: pages 126–130
• for Wednesday, March 7: pages 110–113
• for Friday, March 9: pages 114–117
• for Monday, March 12: Lemma A on page 142
• for Wednesday, March 14: pages 141–144
• for Friday, March 16: pages 145–148 (ending at the proof of the Corollary)
• for Monday, March 19: Section 4.4
• for Wednesday, March 21: Section 5.1
• for Friday, March 23: pages 171–174
• for Monday, March 26: pages 175–180
• for Wednesday, March 28: pages 181–183
• for Friday, March 30: pages 184–187
• for Wednesday, April 4: Section 2.6

Last modified Friday, 13-Apr-2007 17:55:08 PDT