Tags:
, view all tags
```
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)+ n2

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

Edit | Attach | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2004-05-06 - RobbieMoll

 Home Moll575 Web View Edit Account
 Edit Attach
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