Do three questions from each section. If you work more than the required number of problems, make sure that you clearly mark which problems you want to have counted. Standard results from the courses may be used without proof provided they are clearly stated. If you have doubts about the wording of a problem or about what results may be assumed without proof, please ask for clarification. In no case should you interpret a problem in such a way that it becomes trivial.

## Section A.

## Question 1.

a. How many increasing functions are there which map $[ n ] = \{ 1 , 2 , \dots , n \}$ to [m]? [We do not require that the functions are strictly increasing.]

b. Give a closed form expression for $\sum _ { k = 0 } ^ { m } { \binom { n - k } { m - k } }$

## Question 2.

a. Prove that if $f , g : \mathcal { P } ( n ) \longrightarrow \mathbb { R }$ are two real-vauled functions on the power set of [n] then

$$
\forall A \subseteq [ n ] \qquad g ( A ) = \sum _ { B \subseteq A } f ( B )
$$

if and only if

$$
\forall A \subseteq [ n ] \qquad f ( A ) = \sum _ { B \subseteq A } ( - 1 ) ^ { | A \backslash B | } g ( B ) .
$$

b. A subcube of ${ \mathcal { P } } ( n )$ is a subset ${ \mathcal { C } } \subseteq { \mathcal { P } } ( n )$ of the form

$$
\mathcal { C } _ { A , B } = \{ C \subseteq [ n ] : A \subseteq C \subseteq B \}
$$

for some $A \subseteq B \subseteq [ n ]$ . A subcube is trivial if $A \ : = \ : B$ and hence $| { \mathcal { C } } | = 1$ Characterize all functions $h : \mathcal { P } ( n ) \longrightarrow \mathbb { R }$ having the property that for every non-trivial subcube of $\mathcal { P } ( n )$ we have

$$
\sum _ { C \in { \mathcal { C } } } h ( C ) = 0 .
$$

Question 3. Suppose $0 \leq t < n / 2$ and that ${ \mathcal { A } } \subseteq { \mathcal { P } } ( n )$ is an antichain with $| A | \leq t$ for all $A \in A .$ . Define

$$
{ \mathcal { A } } _ { t } = { \biggl \{ } B \in { \binom { [ n ] } { t } } : { \mathrm { t h e r e ~ i s ~ s o m e ~ } } A \in { \mathcal { A } } { \mathrm { ~ w i t h ~ } } A \subseteq B { \biggr \} } .
$$

Prove that $| { \mathcal { A } } | \leq | { \mathcal { A } } _ { t } |$

## Question 4.

a. State and prove Burnside’s lemma concerning the number of orbits of a group action.

b. Some identity cards are to be made by taking square cards ruled into a $7 \times 7$ grid and punching out two of the squares. The cards can be inserted into a scanner with any orientation. How many different identity cards can be produced this way?

Question 5. Given integers $0 < d \leq n$ and a prime power q prove that there exists a linear code $C \subseteq \mathbb { F } _ { q } ^ { n }$ of minimum distance at least d, containing at least

$$
q ^ { n } \Big / \left( \sum _ { i = 0 } ^ { d - 1 } { \binom { n } { i } } ( q - 1 ) ^ { i } \right)
$$

codewords.

## Section B.

## Question 6.

a. Let A be a subset of a topological space X. Prove that both ${ \overline { { A } } } \setminus A$ and A \ int A have empty interior. b. We say that a family A of subsets of a topological space X is locally finite if for all $x \in X$ there exists a neighbourhood U of x such that U meets only finitely many of the sets in A. If A is locally finite prove that

$$
{ \overline { { \bigcup _ { A \in { \mathcal { A } } } A } } } = \bigcup _ { A \in { \mathcal { A } } } { \overline { { A } } } .
$$

Question 7. Show that if A is a proper subset of a connected space X and B is a proper subset of a connected space Y , then $( X \times Y ) \setminus ( A \times B )$ is connected.

Question 8. Suppose that X is an arbitrary topological space and Y is a compact space. Consider the projection map $\pi : X \times Y \to X$ defined by $\pi ( x , y ) = x$ . Prove that if $X \times Y$ has the product topology then π is a closed map (that is, it maps closed sets to closed sets).

Question 9. Let $X = \mathbb { R } ^ { 2 }$ and define an equivalence relation on X by $( x _ { 1 } , x _ { 2 } ) \sim ( y _ { 1 } , y _ { 2 } )$ iff they are equal or $x _ { 1 } = y _ { 1 } = 0$ . Set $Y = X / { \sim }$ Show that Y is Hausdorff but does not have a countable basis for its topology.