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

1. Let $n \geq r \geq k \geq 1$ be integers. Prove the following binomial coefficient identities:
   
   $${{n}\choose{k}} = \frac{n}{k}{{n-1}\choose{k-1}},\qquad {{n}\choose{r}}{{r}\choose{k}} = {{n}\choose{k}}{{n-k}\choose{r-k}}.$$
   
   
   Give also a combinatorial interpretation for the second identity.

2. 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 $T$ with at least two vertices has chromatic number $\chi(T) = 2$.
   3. Prove that if a tree contains a vertex of degree $d \geq 1$, then it also contains at least $d$ leaves.

3. 1. Consider a graph whose vertices are all the two-element subsets of the four-element basis set $\{1,2,3,4\}$, and there is an edge between vertices $X$ and $Y$, $X \neq Y$, if and only if $X \cap Y \neq \emptyset$. 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 $\{1,2,3,4,5\}$ is not planar.

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

5. Consider the set of strings over the four-letter alphabet $\{A,B,C,D\}$. Denote by $a_n$ the number of $n$-letter strings that contain an odd number of the letter $A$. (Thus $a_0=0$, $a_1=1$, $a_2=6$ etc.) Prove that the numbers $a_n$ are related by the recurrence equation $a_{n+1} = 2a_n+4^n$, and use this recurrence to find a closed-form expression for the numbers $a_n$. (Hint: Partition the $(n+1)$-letter strings according to whether they begin with $A$ or some other letter.)

Grading: Each problem 12 points, total 60 points.