Computer Science 575/ Mathematics 513
Combinatorics and Graph Theory
Final Exam
May 14, 2005

Show all you work!

1.   Given two copies each of the letters a,b,c,d,e, how many length 10 sequences of these letters are
there in which no letter appears consecutively? (For example,  abcdeabcde is ok, abcdeedcba is bad.)

2.   How many ways are there to collect 13 dollar bills from a class of 30 students,
if each student can give at most 2 dollars?

3.   Show that if G is a tree in which all vertices have odd degree, then the number of edges in G is odd.

4.   A 3x3 checkerboard can have its cells colored with 2 different colors, R and B.
If rotations only are allowed, what is the cycle index of the system, and how many distinct
(that is, inequivalent) boards are there with exactly 3 B cells?

5.   What is the coefficient of xy2z2w in (x+y+z+2w)6?

6.   Give a combinatorial argument for the following identity:

C(2n,n) + C(2n,n-1) = (1/2)*C(2n+2,n+1)

7. A 1xN checkerboard can be tiled with a mixture of dominoes (two identical cells make up a tile) and
monominoes (one-celled tiles). There is a restriction on tilings: no two dominoes (2-celled tiles)
can appear consecutively in a tiling. Give a recurrence, H(n), with initial conditions,
for the number of ways the board can be tiled.

-- RobbieMoll - 06 May 2004

This topic: Moll575 > OldFinal
Topic revision: r3 - 2006-12-01 - 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