Computer Science 575 / Mathematics 513 Combinatorics and Graph Theory Final Exam December 17, 2002 Show all your work. Numerical answers don't matter: appropriate unevaluated algebraic expressions are the proper form for your results. 1. Give a combinatorial argument to show that C(2n,2) = 2*C(n,2)+ n^2 2. Consider four-digit positive integers, e.g. 4799. How many have the property that their digits sum to 31? 3. Suppose 12 coins are tossed, one after another, and suppose that there are 3 heads and 9 tails. How many such sequences are there for which there are at least 5 tails in a row? 4. 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. Your answer should include values for H(1), H(2), and H(3). 5. How many ways are there to distribute 25 identical balls into six distinct boxes, with at most 6 balls in each of the first three boxes? 6. Consider n digit numbers (digit sequences) over the digits 0,1,6,8,9. Two numbers are considered equivalent if one can be obtained from the other by flipping, e.g. 8900 and 0068 are equivalent. For n even, how many inequivalent numbers are there over this alphabet? 7. What is the largest possible number of vertices in a graph with 19 edges, with the property that the vertices all have degree at least 3? Draw such a graph.

-- RobbieMoll - 06 May 2004

Topic revision: r2 - 2004-05-06 - 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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback