Final Exam, Wed 15 Nov. 2000, 8-12 a.m.

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

Give also a combinatorial interpretation for the second identity. - Find the Prüfer codes (as used, e.g., in the proof of Cayley's
theorem) of the following trees:
- Prove that every tree with at least two vertices has chromatic number .
- Prove that if a tree contains a vertex of degree , then it also contains at least leaves.

- Find the Prüfer codes (as used, e.g., in the proof of Cayley's
theorem) of the following trees:
- 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.
- Prove that the corresponding graph formed out of the
two-element subsets of the five-element basis set
is
*not*planar.

- 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?
- 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.