# 575/513 Final Fall 2006 Answers

1. How many distinct four digit numbers have the property that their digits sum to 31?

Answer: Via generating functions - look for coefficient of x31 in (1+x+x2...+x9)4 .

2. Give a recurrence for the number of sequences of length n, H(n), that are made up of the letters A, B, C, such that any non-final occurrence of the letter A is followed immediately by the letter B. Thus ABC and ABCA are both legal, but ACBA is illegal -- if any letter follows an A, it must be a B. Your answer should include values for H(1), H(2), and H(3).

3. Six women and four men form a line. In how many ways can this be done if no two men can be next to each other.

4. Suppose G is an undirected, connected planar graph with 11 vertices. Prove that G must have a vertex of degree 4 or less.

Answer: E <= 3V-6, and handshaking lemma. Get contradiction if all vertices have degree 5 or higher.

5. Suppose 8 distinct dice are rolled. What is the probability that on a single roll, all numerical values -- 1-2-3-4-5-6 -- appear?

Answer: count how many times condition can happen, then divide by 6**8 possible outcomes. To do the count, use inclusion/exclusion, with Ai = "score of i doesn't come up on any of the faces". See hwk problem 11-1

6. Suppose you have a string that holds 7 beads. Beads come in 2 colors – red and green. You can “flip” the string, and two bead arrangements are equivalent if one can be flipped to the other. How many inequivalent arrangements of beads are there? What is the cycle index of the system? How many inequivalent bead arrangements are there with exactly two red beads?

Answer: Cycle index: 1/2[x17 + x1x23] - with 2 colors - 72 classes. 12 with 2 reds

7. If 10 sweaters and 15 watches are distributed among 4 people, how many ways are there to give each person at most 5 sweaters and at most 5 watches?

Answer: Sweater, watch distribution are independent: so count ways to distribute sweaters, then ways for watches, then multiply together. Using gen fns, sweaters are (1+x2 +...+ x5)4 seek coefficient of x10 . For watches, seek coef of x15 for same generating fn .

8. What is the coefficient of x15 in this expression: (1+x3)-4?

Answer: -C(8,5), when viewed as (1-u)-4 where u is -x3 .

-- RobbieMoll - 2012-05-07

Topic revision: r3 - 2012-05-08 - RobbieMoll    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback