MAS1003

UNIVERSITY OF EXETER SCHOOL OF MATHEMATICAL SCIENCES

DISCRETE MATHEMATICS

December 25, 1999  9:30 a.m. – 12:30 p.m.

Duration: 3 hours

Examiner: Dr Robin Chapman

Answer Section A (40%) and any THREE of the four questions in Section B (20% for each). Marks shown in questions are merely a guideline. Approved calculators of the following type may be used Casio fx82 series, Sharp EL521 or EL531 Series and Texas TI-30X or TI-36X.

SECTION A

1. (a) A Poker hand contains five cards from a standard pack (4 suits and 13 values). How many Poker hands contain one pair? That is they contain two cards of one value, the remainingthree cards having three other values. (6)

(b) Find the coefficients of x^{3}y^{3}z^{4} and x^{7}yz^{2} in (2x − y + z)^{10}. (6)

(c) Solve the following recurrence: a_{0} = 0, a_{1} = 1, a_{n} = a_{n−1} + 12a_{n−2} for n ≥ 2. (6)

(d) Find the least positive integer a with 6^{1000} ≡ a (mod 19). (5)

(e) Let σ = (1 5 6 2)(3 8 4 7) and τ = (1 8 2 7 3 6 4 5) be elements of S_{8}. Calculate στ, τσ, σ^{2}, τ^{−1} and τστ^{−1}, and find the order and sign of each of these. (5)

(f) Express the following permutations as products of transpositions: σ = (1 2 5 7 4)(3 8 6) and τ = (1 12 3)(2 4 11 7)(3 6 10 5 8). (6)

(g) Find the tree with Prüfer code (1,3,6,9,10,1,3,1). (6) [40]

SECTION B

2. (a) Some students play an unconventional form of Poker where each player receives a hand of six cards from a standard pack (4 suits and 13 values). How many hands are there of each of the following types?

(i) four of a kind: four cards of one value, the remaining two of two other values:

(ii) 3-2-1 : three cards of one value, two of a second and one of a

third; (iii) two threes: three cards of each of two different values.

(9)

(b) Show that

\binom{2n}{n − 1} = \frac{n}{n + 1}\binom{2n}{n}

for each positive integer n. (3)

(c) How many anagrams of ENTERTAIN contain at least one of the

three words ENTER, TENT and RATE? (8) [20]

3. (a) Let A be an arbitrary six-digit number. Create a number B by splitting A into two three-digit blocks, and subtracting the first from the second. For instance if A = 135864 then B = 864−135 =

729. Show that A is divisible by 13 if and only if B is divisible by 13. (6)

(b) Find the solutions of the following recurrences:

(i) A_{0} = 1, A_{1} = 1, A_{n} = 2A_{n−1} − 3A_{n−2} for n ≥ 2; (ii) B_{0} = 0, B_{1} = 1, B_{n} = 2B_{n−1} − 3B_{n−2} for n ≥ 2.

Using the formulas you obtain, show that B_{2n} = 2A_{n}B_{n} and A_{n}^{2} + 2B_{n}^{2} = 3^{n} for each n. (14)

[20] 4. (a) Let σ and ρ be permutations. Show that (ρσρ^{−1})^{2} = ρσ^{2}ρ^{−1} and

(ρσρ^{−1})^{−1} = ρσ^{−1}ρ^{−1}. (5)

(b) How many permutations in S_{9} have order 6? How many of them

are even and how many of them are odd? (15) [20]

5. (a) Draw the complete bipartite graph K_{4,4} and find an Eulerian walk therein. (5)

(b) State Euler’s formula, and use it to show that the complete graph K_{5} is not planar. (10)

(c) By considering colourings, or otherwise, show that the graphs G and H are not isomorphic.

[figure: G:; H:] (5)

[20]

Page 4 of 4 MAS1003/END OF PAPER