Introduction to Discrete Mathematics
Midterm Exam 1, Wed 25 October, 8-11 a.m.

1. Let ${\cal E}_n$ denote the family of all possible partitions of the set $\{1,2,\dots,n\}$. Define a partial order $\sqsubseteq$ on ${\cal E}_n$ as follows: $E \sqsubseteq E'$, if partition $E$ is finer than partition $E'$, i.e. each class of $E$ is contained in some class of $E'$. For instance, in ${\cal E}_3$ it is true that $\{\{1\},\{2\},\{3\}\} \sqsubseteq \{\{1,2\},\{3\}\}$, but e.g. the partitions $\{\{1,2\},\{3\}\}$ and $\{\{1\},\{2,3\}\}$ are incomparable.
   1. Draw the Hasse diagrams of the partial orders $({\cal E}_2, \sqsubseteq)$ and $({\cal E}_3, \sqsubseteq)$. How many elements do the sets ${\cal E}_4$ and ${\cal E}_5$ have?
   2. Describe in general terms the partial order ( ${\cal E}_n, \sqsubseteq)$. What are its least and greatest elements? How many elements does it have altogether? What are the immediate successors of a given partition $E \in {\cal E}_n$? How many are there?

2. Consider the family of subsets of an $n$-element set $A$. How many ways are there to select a pair of sets $(X,Y)$, $X \subseteq A$, $Y \subseteq A$, so that $X \neq Y$? How about if one requires in addition that $X \subseteq Y$?

3. Six married couples organize a dance party. In how many ways can they be arranged into dancing pairs, when it is required that nobody dances with their own spouse? (Hint: Inclusion-exclusion.)

4. Small-time stock market investor F. U. Ture manages his portfolio according to the following scheme: in the beginning of each week he buys new shares for an amount of money equal to the value of his portfolio two weeks earlier, and sells shares for an amount corresponding to the value of his portfolio three weeks earlier. (Any other possible changes in the values of the shares are ignored here.) Find out how the value of F. U. Ture's portfolio evolves, when he starts investing in the beginning of Week 0 with an initial capital of 1 Euro.

Grading: Problems 1 and 4 each 8 points, Problems 2 and 3 each 7 points, total 30 points.