MAS1003

UNIVERSITY OF EXETER SCHOOL OF MATHEMATICAL SCIENCES

DISCRETE MATHEMATICS

January 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 are full houses? (A full house consists of three cards of one value and two cards of another value.) (5)

(b) Prove, by induction on n, that

1^{3} + 2^{3} + ⋯ + n^{3} = \frac{n^{2}(n + 1)^{2}}{4}

for all integers n ≥ 1. (6)

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

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

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

(f) Find the Prüfer code of the following tree.

[figure: 6; 7; 4; 9; 3; 1; 2; 5; 10; 8]

(6)

(g) Find the tree with Prüfer code (7,6,6,10,1,6,1,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) super full house: four cards of one value and two of another; (ii) 3-2-1 : three cards of one value, two of a second and one of a

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

(9)

(b) How many anagrams of the word DEPRESSED are there? In how many of them are the two Ds adjacent? (4)

(c) How many arrangements of the letters E, F, I, L, M, N, R, T, U

contain at least one of the three words LEFT, MILE and TURN? (7) [20]

3. (a) Recall that the Fibonacci numbers F_{n} are defined by the recurrence F_{1} = F_{2} = 1, F_{n} = F_{n−1} + F_{n−2} for n ≥ 3. Show, by induction on n, that

∑_{j=1}^{n} F_{2j} = F_{2n+1} − 1

for each integer n ≥ 1. (6)

(b) Find the solutions of the following recurrences:

(i) A_{0} = 1, A_{1} = 2, A_{n} = 4A_{n−1} − A_{n−2} for n ≥ 2;

(ii) B_{0} = 0, B_{1} = 1, B_{n} = 4B_{n−1} − B_{n−2} for n ≥ 2. (8)

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

[20] 4. (a) Show that if a ≡ b (mod n) and c ≡ d (mod n) then ac ≡ bd

(mod n). Show by induction that if a ≡ b (mod n) then a^{r} ≡ b^{r} (mod n) for all integers r ≥ 1. (7)

(b) Let t be an invertible element of Z_{n}. Show that the square L_{t} with rows and columns indexed by Z_{n} and entries L_{t}(i, j) = ti+j (in Z_{n}) is a Latin square. Give an example of a number n and a non-zero t ∈ Z_{n} for which L_{t} fails to be a Latin square. (7) Find two Latin squares which are orthogonal to the following Latin square (the addition table of Z_{5}) and to each other:

0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 .

(6) [20]

5. (a) Let σ and ρ be permutations. Show that (ρσρ^{−1})^{m} = ρσ^{m}ρ^{−1} for each integer m ≥ 1. Deduce that (ρσρ^{−1})^{m} = id if and only if σ^{m} = id. (8)

(b) Let σ and ρ be permutations. Show that the inverse of the permutation σρ is ρ^{−1}σ^{−1}. Deduce that if τ_{1}, τ_{2}, …, τ_{r} are transpositions then the inverse of τ_{1}τ_{2} ⋯ τ_{r} is τ_{r} ⋯ τ_{2}τ_{1}. (6)

(c) Determine all the possible cycle structures for permutations of order 6 in S_{8}. Hence calculate the number of even permutations of order 6 in S_{8}. (6)

[20]

Page 4 of 4 MAS1003/END OF PAPER