MATH 357 -- Combinatorics, Spring 2017

Syllabus and Schedule

• Course syllabus (.pdf)
• Day-by-day course schedule, modified, March 7.

Examples, Class Notes, Etc.

• A diagram from a Chinese mathematical text from the 1300's CE. (And this mathematics is actually is even much older than that, going back at least to Islamic mathematicians in the 800's CE.) So why is it called Pascal's triangle?? (Note: Blaise Pascal lived from 1623 to 1662 CE.)
• Some Maple tricks for computing with generating functions.
• A Polya enumeration example

Announcements

• No problem set the week of May 1 because of final project presentations.
• Final Exam (for those not doing a project) is coming up on Friday, May 12 at 11:30am. To help you review:
  1. Review sheet for final and solutions for the practice problems.
  2. Review sheet for Exam 1 with some review/practice problems and solutions for the practice problems.
  3. Review sheet for Exam 2 with some review/practice problems and solutions for the practice problems.
• The textbook for the course is
  
  R. Beeler, How to count: An introduction to combinatorics and its applications, Springer, ISBN 978-3-319-13844-2
  
  If you click on the link here, it should take you to an electronic version of the book that you can download free of charge. The College library has purchased a large package of electronic books from this publisher for use on campus. You should be able to print out sections as well if you want hardcopies. You can also obtain conventional bound copies of the book in any of the usual ways if you would prefer that.

Assignments

• Discussion 1 -- group writeups due: Wednesday, February 1.
• Problem Set 1: From Beeler How to Count Problems 1.5.10, 1.5.11 (Extra Credit), 2.1.14, 2.1.15, 2.1.19 (Note: For the purposes of this problem, a ``word'' is simply a string of letters in the Roman alphabet. It does not need to be an actual word in any language.), 2.1.23, 2.2.7, 2.2.8, 2.2.11 (Include in your solutions for 2.2.7 and 2.2.11 a clear explanation of the way that you are interpreting the sentence ``No two restaurants have the same menu.'') due: Friday, February 3.
• Problem Set 2: From Beeler, Problems 2.3.5, 2.3.6, 2.3.7 (a ``binary matrix'' is one all of whose entries are either 0 or 1), 2.4.9, 2.4.10, 2.5.6 (Hint: try the case n = k first. There are no other pieces on the board.) besides the k rooks), 2.5.8 (the ``meeting'' is the group of five people who attend -- one from each club, either the actual representative or the alternate, but not both), 2.7.13, 2.7.14, 2.7.20. due: Friday, February 10.
• Discussion 2 -- group writeups due: Wednesday, February 15.
• Problem Set 3: From Beeler, Problems 3.1.13, 3.1.14, 3.1.17 (Hint: See Proposition 3.1.8), for Extra Credit do 3.1.19 but with this change in directions: This problem is apparently defective as stated because the obvious answer is somewhat silly: Suggest a change that makes it more interesting and solve the restated problem, 3.2.6, 3.3.6, 3.3.7, 3.4.6, 3.4.7, 3.5.5. due: Friday, February 17.
• Problem Set 4: From Beeler, Problems 3.6.12 (i) and (ii) only, 3.6.14 (i) and (iii) only, 3.6.19 (Note: ``anagrams'' means distinguishable permutations of the letters in the word; the rearranged letters do not need to form actual words), 3.6.23, 3.6.24, 4.2.13, 4.2.14, 4.2.17. due: Friday, March 3.
• Problem Set 5: From Beeler, Problems 4.3.13 (BUT interchange the 9 and the 16 so there are 16 balls and 9 urns!), 4.3.17 (i), 4.3.18, 4.3.20, 5.1.10 (i) and (iv) only (Note: ``into the form above'' means into one of the forms given for q(x) on page 120 or 121, depending on whether or not there are multiple roots), 5.1.11 (i) only, 5.2.8, 5.2.10 due: Friday, March 17.
• Information on final projects.
• Problem Set 6: From Beeler, Problems: 5.3.10 but with modified directions: (i) First compute the number of ways to spend exactly $15 enumerating all the ways to do that explicitly as partitions of 15 and also using the appropriate generating function, then (ii) solve the problem as stated; 5.3.13, 5.3.20, 5.3.21 (Note: we did 5.3.19 in class on Friday, 3/15. You'll need that for 5.3.21), 5.4.6, 6.1.14, 6.1.15, 6.1.18. You can use Maple for the problems that ask for a numerical answer as a coefficient in a generating function. See the Example above for useful ``Maple tricks.'' due: Friday, March 24.
• Problem Set 7: From Beeler, Problems 6.2.6, 6.2.8 (Except: make the recurrence R<sub>n</sub> = 5 R<sub>n-1</sub> + 29 R<sub>n-2</sub> - 105 R<sub>n-3</sub>), 6.3.9 (But with this addition: The statement in the problem is true ``generically'' but not in absolutely every case. Explain what this means and what extra condition you might add to make it true under that condition.), 6.3.13, 6.5.18, 6.5.20. Note: The directions "Find a closed form for the recurrence" mean to find a closed formula for the terms in the sequence R_n as a function of n -- what we called "solving the recurrence" in class. due: Friday, March 31.
• Problem Set 8: From Beeler, 7.1.19 (Hint: Maple!), 7.3.6, 7.3.7, 8.2.12 (think of the D₅ as a subgroup of S₅ as is done for D₄ on page 226), 8.2.13, 8.3.13. due: Friday, April 21.
• Discussion 3, group writeups due: Wednesday, May 5.

Solutions

• Solutions for Problem Set 1
• Solutions for Problem Set 2
• Solutions for Problem Set 3
• Solutions for Midterm Exam 1, given February 24.
• Solutions for Problem Set 4
• Solutions for Problem Set 5
• Solutions for Problem Set 6
• Solutions for Problem Set 7
• Solutions for Midterm Exam 2, given April 7.
• Solutions for Problem Set 8
• Solutions for Final Exam, given May 12.

Related Links and Other Information

• Note: The Greek phrase appearing next to the heading of this page is one traditional rendering of the reported inscription over the entrance to Plato's Academy in Athens (founded about 387 BCE). It means (roughly) Let no one ignorant of geometry enter. This is a reflection of the foundational role of geometry and mathematics more generally in Plato's ideas about knowledge and education.

Last modified: May 12, 2017