MSU MATHEMATICS

MTH 482
Discrete Mathematics II

Spring 2008

Instructor: Prof. Peter Magyar , magyar@math.msu.edu, tel. 353-6330, Wells Hall D-326.
Office hours: Mon, Wed, Fri 9:15−10:15am, 11:15−12:15 map
Course Information: Grading, exam, and homework policies.
Announcements
- Test 3: Mon 4/21 in class (come 5 mins early). Covering:
  - Method of Generating Functions, Otter's enumeration of trees (r_n, t_n, Otter's Lemma)
  - chromatic polynomials, acyclic orientations, Stanley's Theorem
  To study, review:
  - Quizzes 6--10.
  - Notes 3/10--4/11, which give a complete outline of what we have covered.
  - HW 3/17--4/14
  - Review problems below.
Homework: I will not collect homework, but the weekly quizzes will be based on them. These problems are an essential component of the course, and I strongly recommend you do all of them.
For extra points, you may turn in the problems marked Extra Credit, preferably within a week of the HW date.
If you get a score of 6 or less on a quiz, you may write out the correct answers and turn it in for an extra 3 points.
References are listed at the end of this page.
- Graph Theory Review Problems
- Old Homework
- Test 3 Review
  1. Making change (see HW 3/24 #4). Let d_n be the number of ways to make k cents with a handful of pennies (1¢), nickels (5¢) and dimes (10¢). For example, d₁₅ = 6, since we can make 15¢ as:
    10¢ + 5¢ , 10¢ + 5(1¢) , 3(5¢) , 2(5¢) + 5(1¢) , 5¢ + 10(1¢) , 15(1¢)
    1. Find a simple formula for the generating function d(x) = ∑ d_n xⁿ .
    2. Use the dlog method to find a recursive formula for d_n .
    3. Use algebraic tricks to get an explicit formula for d_n . Hint: (1 + x + x² + ⋅⋅⋅ + x⁹)(1 − x) = 1 − x¹⁰.
  2. Let a_n be the number rooted, unlabelled trees which are asymmetric, meaning that there is no symmetry of the tree which preserves the root. For example, a₅ = 3 counts the trees:
    ®−O−O−O−O O−®−O−O−O
    ®
    |
    O− −O− −O− −O
    Any other choice of root allows symmetries. Notice that the star tree cannot be rooted in any way to eliminate symmetries.
    1. Our computation of r_n (the number of all rooted trees) was based on the combinatorial recurrence: a rooted tree with n+1 vertices is equivalent to a multiset of rooted trees with total n vertices. Find a similar recurrence for asymmetric trees.
    2. Use the combinatorial recurrence to deduce a generating function identity similar to that for r(x) = ∑ r_n xⁿ , of the form:a(x)/x = ∑ a_n+1 xⁿ = product with exponents a_k .
    3. Apply the dlog method to find a recurrence for a_n similar to the Second Recurrence for r_n .
    4. Extra Credit: Let b_n be the number of unrooted, unlabelled trees which can be rooted to eliminate symmetries. For example b₅ = 2 counts the two shapes of trees above (but not the star tree). Can you find an anlaog of Otter's Theorem to compute b_n in terms of a_n ?
Notes
- Old Notes
References
- HHM Harris, Hirst Mossinghoff, Combinatorics and Graph Theory, Ch 1 (basic graph theory review)
- FCM Bollobas, Basic Graph Theory, Ch III: Flows, Connectivity, and Matching
- KUR R. Diestel, Graph Theory, Ch 3 & 4 on Kuratowski Theorem.
- Stan R.P. Stanley, Acyclic orientations of graphs, Discrete Mathematics vol. 5 (1973), pp. 171--178.
- Read R. Read, The number of k-colored graphs on labelled nodes, Canadian Journal of Mathmatics vol. 12 (1960), pp. 171--178. Correction: vol. 22 (1970), pp. 594--596.

	®
	\|
O−	−O−	−O−	−O

MSU MATHEMATICS

MTH 482 Discrete Mathematics II

MTH 482
Discrete Mathematics II