1. Which of the following is the balanced string corresponding to the planar diagram

(a) ()()(())((()))()()

(d) (())(())((()()))()

(b) (())((()))()((()))    (e) None of the above.

(c) ()()((()()()()()))

2. Let A = {{∅}, a, {a}, {a, b}, {c}}. Which of the following is true?

(a) ∅ ∈ A

(d) a ∪ {a} ∈ A

(b) {c} ⊆ A

(e) {∅} ∈ A

(c) {a} ∩ {a, b}  A

3. Let X = {1, 2, ..., n}. Then |P(X)| is

(a) n                (b) 2n                      (c) n!              (d) (  )2(n)         (e) nn

4. Which of the following functions f : Z → Z is not injective?

(a) f(n) = 2n                         (b) f(n) = 2n                                       (c) f(n) = n3  + 1

(d) f(n) = n2  − 2                  (e) All of the above are injec-

5. Consider the bijection from the power set to the set of binary sequences

f : P({1, 2, 3, 4}) → {b1 b2 b3 b4 |bi  ∈ {0, 1}}

given by f(B) = b1 b2 b3 b4 , where bi  = 1 if i ∈ B and bi  = 0 otherwise. Then f({1, 3}) is equal to

1010

(d)

1001

(e)

(c) 1100

6. Let A and B be finite sets.  Given that there exists a bijective function f : A → B we may conclude that:

(a) |A| < |B|   (b) |A| ≤ |B|   (c) |A| = |B|   (d) |A| ≥ |B|   (e) |A| > |B|

7. Let A and B be finite sets, let y ∈ B , and let f : A → B be a function such that

(3x ∈ A)(f(x) = y).

Then we may conclude:

(a) |A| = |B|.                      (b) f is not injective.          (c) y is in the image of f .

(d) f is not a function.       (e) y is not in the image of f .

8. The number of permutations of {1, 2, 3, 4} is:

(a) 8                (b) 16              (c) 24              (d) 32              (e) None of the above.

9. The number of injective functions from {1, 2, 3, 4} to {1, 2, 3, 4, 5} is

(a) 24              (b) 32              (c) 100            (d) 116            (e) None of the above.

10. How many numbers are there between 1 and 1000 which are divisible by 15 and 2?

(a) 100

(d) 33

(b) 66

(e) None of the above.

(c) 12

11. Given  |A| =  15,  |B| =  6,  |C| =  12,  |A ∩ B| =  3,  |A ∩ C| =  8,  |B ∩ C| =  3 and |A ∩ B ∩ C| = 3, then |A n B n C| is

(a) 20               (b) 21               (c) 22               (d) 23               (e) Impossible  to

determine.

12. A large jar is full of three types of candies. You grab a handful of twelve of them. How many possible outcomes are there?

(a)  (3(15))

(b) (2(15))

(c)  (3(14))

(d) (2(14))

None of the above.

13. How many solutions are there for the inequality x1  + x2  + x3  ≤ 4 with xi  ∈ N? (a) 31                 (b) 32                 (c) 33                 (d) 34                 (e) 35

14. A Boolean expression in a disjunctive normal form for the following Boolean function

x        y        z

1

0

1

0

1

0

1

0

is

(a) xy\ z ∨ x\ yz\  ∨ x\ y\ z .

(c) xyz\  ∨ x\ yz ∨ x\ y\ z\ .

(e) None of the above.

15. Which of the following propositions is a tautology?

(a) p ∨ (q ∧ r)                        (b) (p ⇒ q) ∨ q                      (c) (p ⇔ r) ∨ (p ∨ ∼ q)

(d) (p ⇒ q) ∨ ( ∼ q ∧ q)         (e) (p ∧ q) ∨ ( ∼ p ∨ ∼ q)

16. The proposition which is logically equivalent to the negation of

(Ax)(∼ p(x) ∨ q(x))

is

(a) (3x)(p(x)∧ ∼ q(x))                                 (b) (Ax)(p(x)∧ ∼ q(x))

(c) (Ax)(p(x)∨ ∼ q(x))                                 (d) (3x)(p(x)∨ ∼ q(x))

None of the above.

17. Suppose n > 2 is a product of two primes n = pq and a > 1 divides n.  Then we may conclude that:

(a) n divides a                                                (b) a divides p and a divides q

(c) a divides p or a divides q                       (d) a doesn’t divide p and a doesn’t divide q (e) a doesn’t divide p or a doesn’t divide q

18. The closed form for the generating function z2  + 3z3  + 9z4  + 27z5  + · · · is

1      

(b)    z2     

(c)        z        (1 − 3z)2

(d)     1    

(e)    z2      

1 − 3z

19. The sequence an  with the generating function G(z) =  is given by

(a) an  = 3 − 2n+1                              (b) an  = ( −1)n+1(3 − 2n+1) (c) an  = ( −1)  (3n  − 2  )n

(d) an  = ( −1)n (3 − 2n+1)     (e) an  = ( −1)  (3 + 2nn+1)

20.  Let p be a propositional variable that can be assigned true or false, and let r(x) be a

propositional statement.

Consider the following statements:

(1) There are infinitely many primes.

(2) The compound proposition ((p V ∼p) ⇒ (p ⇒ ∼p)) is a theorem.

(3) ^2 is rational.

(4) ∼ (3x)r(x) ≡ (3x) ∼r(x).

Which one of the following correctly describes these statements?

(a) (1), (3) and (4) are true, (2) is false.

(b) (2), (3) and (4) are true, (1) is false.

(c) (1) and (2) are true, (3) and (4) are false.

(d) (2) and (3) are true, (1) and (4) are false.

(e) None of the above.

Extended Answer Section

There  are three  questions in this section, some with a number of parts .   Write your

answers  in  the  space provided  below  each part.   You  must show  your working  and give

reasons for your answers .  If you  need more  space  there  are  extra pages  at  the  end  of the

examination paper.

1.  (a) Consider the sets A  =  {a, b, c, 1, 2, 3}, B  =  {b, c, 1, 4, 5}, and C  =  {1, 2, 3, 4, 5}. Write down explicitly a bijection from A / B to B ∩ C, or explain why one does not exist.

(b) Let X, Y be sets and consider functions f : X → Y and g : Y → X .  Suppose that for every y ∈ Y we have that f (g(y)) = y . Prove that f is surjective.

(c) Suppose that A,B, C are sets. Prove the statement

A / (B ∩ C) = (A / B) n (A / C).

(A Venn diagram alone is not sufficient, be explicit about the elements in A, B , and C .)

2.  (a) How many arrangements are there of the letters of WOOLLOOMOOLOO? (In all parts of this question it is not necessary to evaluate formulas involving factorials, binomial coefficients, etc.)

(b) How many arrangements are there with the three Ls together?

(c) How many arrangements are there with the W and M together?

3. Consider the sequence (an )n≥0  defined by the recurrence

an+2  = an+1  + 12an

with initial conditions a0  = 0 and a1  = 1. Let

F (z) =  an zn  = a0  + a1 z + a2 z2  + · · ·

be the generating function for this sequence.

(a) Compute the terms a2  and a3 .

(b) Write down and solve the characteristic equation of the recurrence.

(c) Using part (b), or otherwise, find a closed formula for an .

(d) Explain why

and deduce that          F (z) − zF (z) − 1 z(2)z2 F (z) = z

1 − z − 12z2 .

(e) Use the method of partial fractions applied to part  (d) and geometric series to recover the same closed formula that you found in part (c).

(f)  Consider a new sequence (bn )n≥0   that corresponds to a generating function G(z) with the following rational form:

G(z) =             1            

(1 − z − 12z2   )2.

bn  =  ak+1an+1−k .