MAS1003 Discrete Mathematics: Problem sheet 2 Please hand in solutions to your tutor no later than Monday 8th November 1. [1] How many anagrams has the word MISSISSIPPI?

2. [1] Find the

(i) coefficient of x^{2}y^{2}z^{2} in (x + y + z)^{6}; (ii) coefficient of a^{2}b^{5}c in (a + b + c)^{8}; (iii) coefficient of r^{6}st^{3} in (r + s + t)^{10}; (iv) coefficient of x^{6}y^{4}z^{3} in (x + y + z)^{12};

(v) coefficient of a^{2}b^{2}c^{2}d^{2} in (a + b + c + d)^{8}.

3. [2] Find the

(i) coefficient of x^{2}y^{2}z^{2} in (x − 2y + 3z)^{6}; (ii) coefficient of a^{2}b^{3}c^{3} in (2a − 3b + 5c)^{8}; (iii) coefficient of r^{3}stu^{2} in (r − s + t − u)^{7}.

5. [3] In this question we consider the number of r-element subsets of the set {1, 2, …, n} that contain no pair of consecutive numbers. For instance {1, 4, 5, 9} has a pair of consecutive numbers, but {1, 4, 6, 8} does not. Let A(n, r) be the number of r-element subsets of {1, 2, …, n} having no pair of consecutive numbers. Find A(n, r) for small values of n and r (for instance for n up to 10 and r up to 5). [It may help to list all the r-element subsets of {1, 2, …, n} having no consecutive numbers.] Conjecture (guess) a formula for A(n, r). Can you prove it? Assuming this conjecture calculate A(49, 6) and \binom{49}{6}.

6. [2] For the binomial theorem

(a + b)^{n} = ∑_{k=0}^{n} \binom{n}{k}a^{n−k}b^{k}

to make sense when n and a are zero, what must we define 0^{0} to be?

7. [3] A bridge hand consists of 13 cards from a standard pack. How many bridge hands have a 5-card suit, i.e., exactly 5 cards from a particular suit? [Note that a hand may have two 5-card suits.]

How many bridge hands contain a void, i.e., the hand contains no cards from a particular suit? [Note that a hand may have more than one void.]

8. [2] Recall that a derangement of the set {1, 2, …, n} is a permutation of the numbers 1, 2, …, n with the property that no number j appears in the j-th place. Also recall there are

D_{n} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} = n! (\frac{1}{0!} − \frac{1}{1!} + \frac{1}{2!} − ⋯ + \frac{(−1)^{n}}{n!} )

derangements of {1, 2, …, n}. Calculate D_{n} and D_{n}/n! for all n ≤ 10, the latter up to the accuracy of your calculator, comparing the result with e^{−1}.

9. [3] In a permutation (a_{1}, a_{2}, …, a_{n}) of {1, 2, …, n} call the number j good if a_{j} = j, that is if j is the j-th number in the sequence. For instance 3 and 5 are the only good numbers in (4, 6, 3, 2, 5, 1). A derangement is a permutation with no good numbers.

(i) In how many permutations of {1, 2, 3, 4, 5} is 4 the only good number? (ii) How many permutations of {1, 2, 3, 4, 5} have exactly one good number? (iii) How many permutations of {1, 2, …, n} have exactly one good number? (iv) How many permutations of {1, 2, …, n} have exactly two good numbers?

(v) How many permutations of {1, 2, …, n} have exactly k good numbers?

10. [2] Find the solutions of the following linear recurrences:

(i) a_{1} = −1, a_{2} = 17, a_{n} = 6a_{n−2} + a_{n−1} for n ≥ 3; (ii) a_{0} = 1, a_{1} = 11, a_{n} = a_{n−1} + 2a_{n−2} for n ≥ 2; (iii) a_{0} = 2, a_{1} = 3, a_{n} = 4a_{n−1} − 4a_{n−2} for n ≥ 2; (iv) a_{0} = 0, a_{1} = 1, a_{n} = 2a_{n−1} − 2a_{n−2} for n ≥ 2;

(v) a_{0} = 1, a_{1} = 0, a_{2} = 0, a_{n} = a_{n−1} + a_{n−2} − a_{n−3} for n ≥ 3.

11. [2] The Fibonacci recurrence can be rewritten as F_{n} = F_{n+2} − F_{n+1}. Use this recurrence to define F_{n} for integers n ≤ 0, and evaluate F_{n} for 0 ≥ n ≥ −10. What is the relation between F_{n} and F_{−n}?

12. [3] The Lucas numbers L_{n} are defined recursively by L_{0} = 2, L_{1} = 1 and L_{n} = L_{n−1} +L_{n−2} for n ≥ 2. Find a general formula for L_{n}. Use this formula to prove that F_{2n} = F_{n}L_{n} and L_{2n} = 5F_{n}^{2} + 2(−1)^{n} for each n, where F_{n} denotes the n-th Fibonacci number.

13. [3] For each n ≥ 0, let

G_{n} = \binom{n}{0} + \binom{n − 1}{1} + \binom{n − 2}{2} + ⋯ + \binom{n − k}{k} + ⋯,

the sum continuing as long as n−k ≥ k. For instance G_{5} = \binom{5}{0}+\binom{4}{1}+\binom{3}{2} = 1 + 4 + 3 = 8. Note that these are sums of diagonals in Pascal’s triangle. Compute G_{n} for n up to 12. Conjecture an expression for G_{n}. Can you prove it?

14. [3] Consider the following problem: you are given a 2 by n rectangle, and a supply of n blank 1 by 2 dominoes, and you are asked to cover the rectangle with the dominoes. Denote the number of ways this can be done by C_{n}. Find all coverings for n up to 5. Conjecture an expression for C_{n}. Can you prove it?

RJC 19/10/1999