## MAT282 Introduction to Discrete Mathematics Final Exam, Wed 15 Nov. 2000, 8-12 a.m.

1. Let be integers. Prove the following binomial coefficient identities:

Give also a combinatorial interpretation for the second identity.

1. Find the Prüfer codes (as used, e.g., in the proof of Cayley's theorem) of the following trees:
Determine the 8-vertex tree corresponding to Prüfer code (2,7,1,8,2,8).
2. Prove that every tree with at least two vertices has chromatic number .
3. Prove that if a tree contains a vertex of degree , then it also contains at least leaves.

1. Consider a graph whose vertices are all the two-element subsets of the four-element basis set , and there is an edge between vertices and , , if and only if . Draw a picture of this graph, and prove that it is planar.
2. Prove that the corresponding graph formed out of the two-element subsets of the five-element basis set is not planar.

2. A tricky situation has developed in the counting of votes in the presidential election of the Republic of A: a total of 370 votes given to Donald Duck (who was not a candidate in the election) should be divided among the presidential candidates B, G, and N, so that candidate B gets at least 200 votes, candidate G gets between 100 and 199 votes, and candidate N gets at most 10 votes. In how many ways can the duck-votes be partitioned among the candidates in the desired manner?

3. Consider the set of strings over the four-letter alphabet . Denote by the number of -letter strings that contain an odd number of the letter . (Thus , , etc.) Prove that the numbers are related by the recurrence equation , and use this recurrence to find a closed-form expression for the numbers . (Hint: Partition the -letter strings according to whether they begin with or some other letter.)

Grading: Each problem 12 points, total 60 points.