1.8 Exercises: 1, 3, 5, 7, 9, 14, 17, 21. (These need not be handed in, since solutions are in the book.)
1.10 Supplementary exercises: 1, 4, 6, 7, 12, 16, 21, 22, 26, 31.
2.8 Exercises: 2, 5, 6, 7, 9, 11, 14. (These need not be handed in, since solutions are in the book.)
2.10 Supplementary exercises: 1, 5, 6, 7, 10, 13.
2.8 Exercises: 16, 17, 18, 19, 20, 26, 29, 32, 38. (These need not be handed in, since solutions are in the book.)
2.10 Supplementary exercises: 18, 20, 22, 28, 29, 33, 38, 39.
Extra credit: prove that the coefficients of the polynomial x(x+1)(x+2)…(x+(n-1)) are the cycle numbers c(n,k).
3.8 Exercises: 1, 3, 4, 9, 12, 13, 14, 17. (These need not be handed in, since solutions are in the book.)
3.10 Supplementary exercises: 3, 4, 6, 7, 8, 12, 33.
3.8 Exercises: 21, 25, 26. (These need not be handed in, since solutions are in the book.)
3.10 Supplementary exercises: 15, 16, 17, 18, 23.
Extra problem 1: Build a GF for the following constructions. It is not necessary to compute the coefficients explicitly. Suppose we have beads in masses 1g, 2g, 3g, … . Each bead comes in one of two different colors. Explain how to count (1) Lists of seven beads with total mass n grams. (2) Arbitrary length lists of beads with mass n grams. (3) Necklaces of arbitrary size of beads with total mass n grams. (4) Number of ways to make a bag of beads with total mass n grams. (5) Number of ways to make a bag of beads with total mass n grams, where each bead of a given color may be used at most once.
Extra problem 2: Thanksgiving dinner servings are to be assembled from portions of turkey, stuffing, potatoes, cranberry sauce, gravy, and Lemonheads (tm). Not every serving has to have any particular portion, and multiple portions of the same food can be used if desired. The portions have respectively 250, 100, 100, 50, 150, and 200 calories. (1) Construct a GF counting the number of servings with n calories, if all the portions are served by putting them around the edge of a circular plate, and we don’t care if the plate is rotated. (2) Construct a GF counting the number of servings with n calories, if all the portions are served by dumping them into a large plastic bag.
5.9 Exercises: 1, 5, 15, 16, 17. (These need not be handed in, since solutions are in the book.)
5.11 Supplementary exercises: 2.
Additional problems:
1. Use the transfer matrix method to compute generating functions that count the following. In all of them you can assume that there is one length 0 string (if length 0 makes sense … this is not a serious issue either way). (You can use wolfram alpha to compute determinants if you don’t have access to anything else.)
1a. The number of binary strings of length n that begin with 0 and end with 1. Answer: x2/(1–2x)
1b. The number of binary strings of length n that have any number of zeros and an even number of 1’s. (The 1’s don’t have to be consecutive.) Answer: (1-x)/(1–2x)
1c. The number of binary strings of length n that don’t have the substring 111. Answer: (-x2 - x - 1)/(x3 + x2 + x - 1)
1d. The number of length n strings built from the characters {0,1,2} that don’t contain 01 or 12 as a substring. Answer: -1/(x3 - 2x2 + 3x - 1)
2. Let G be the 3-cycle (vertices {1,2,3}, edges {12, 23, 13}), also known as the complete graph on 3 vertices.
2a. Write the adjacency matrix A for G.
2b. Let a(n) be the number of n-step walks from vertex 1 to vertex 1, and let b(n) be the number of n-step walks from vertex 1 to vertex 2. Compute a(n), b(n) for n<=4.
2c. Show that a(n) = (2n + 2*(-1)n)/3 and b(n) = (2n + (-1)^(n-1))/3.
3.
3a. Draw the 11 unlabeled trees on 7 vertices. (Check your work here.)
3b. For each, determine the number of labelings and verify that there are 75 labeled trees on 7 vertices (this requires adding 11 moderately sized integers).
3c. Determine which are represented by the following Pruefer codes.
i. [1,2,3,4,5]
ii. [1,3,2,2,2]
iii. [2,2,2,2,2]