The University of Sydney School of Mathematics and Statistics Solutions to Tutorial 1 (Week 2) MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022 1. Given a set X and a subset A X , define a function fA : X → {0, 1} by setting fA(x) = 1 if x ∈ A and fA(x) = 0 if x /∈ A. If B is also a subset of X , define (fAfB)(x) = fA(x)fB(x). (a) Work out fAfB when X = {1, 2, 3, 4, 5}, A = {2, 4, 5} and B = {1, 2, 5}. Solution: fAfB takes that value 1 on 2 and 5 and is 0 elsewhere. (b) What subset, if any, does fAfB correspond to Solution: fAfB corresponds to A ∩ B. (c) Define f ′A by f ′ A(x) = 1 fA(x). What subset, if any, does f ′ A correspond to Solution: f ′A corresponds to X A. (d) Form combinations of fA and fB which represent (i) the union of A and B; Solution: We have fA∪B(x) = fA(x) + fB(x) fA(x)fB(x). (ii) the symmetric difference A+B = (A B) ∪ (B A) of A and B. Solution: Define (fA + fB)(x) = fA(x) + fB(x) 2fA(x)fB(x). Alternatively, define (fA + fB)(x) = fA(x) + fB(x), where addition is taken modulo 2. 2. For the following sets X , Y and function X → Y , determine whether the function is injective or surjective (a) X = N, Y = N, f(x) = x+ 1. Solution: If x, y ∈ N and x + 1 = f(x) = f(y) = y + 1, then x = y. Therefore f is injective. Recall that N = {0, 1, 2, . . .}. The function is not surjective because x+ 1 = 0 has no solution with x ∈ N. (b) X = Z, Y = Z, g(x) = x+ 1. Solution: The function g : Z → Z, x ‘→ x + 1 is injective for the same reason as in part (a). It is surjective because if x ∈ Z, x = (x 1) + 1 = g(x 1). (c) X = Z, Y = Z, h(x) = x2 + 5. Solution: We show that the function h : Z → Z, x ‘→ x2 + 5 is neither injective nor surjective. We have f(1) = 12 + 5 = 6 = ( 1)2 + 5 = f( 1). Furthermore, f(x) = x2+5 = 4 is insoluble because the square of an integer is never negative. (d) X = Z, Y = Z, p(x) = x3 + 1. Solution: We show that the function p : Z→ Z, x ‘→ x3 + 1 is injective but not surjective. First we prove that p is injective by establishing the Copyright c 2022 The University of Sydney 1 stronger result that p is increasing, that is, if x, y ∈ Z and x < y, then p(x) < p(y). This follows from the fact the function of real variable f(x) = x3 + 1 is increasing. Finally we show that p is not surjective. If n ! 2, p(n) ! p(2) = 9. On the other hand if n " 1, p(n) " p(1) = 2. Therefore p(n) )= 3 for any integer n. (e) X is a nonempty set, Y = P(X) (the set of all subsets of X), h(x) = {x}. Solution: The function h : X → P(X), x '→ {x} is injective because if {x} = h(x) = h(y) = {y}, then x = y. However h is not surjective because the empty set ∈ P(X) does not satisfy h(x) = {x} = for any x ∈ X . *3. Given finite sets A and B, let E be a subset of A× B. For a ∈ A, let E(a) = { b ∈ B | (a, b) ∈ E } and for b ∈ B, let E∨(b) = { a ∈ A | (a, b) ∈ E }. Prove that ∑ a∈A |E(a)| = ∑ b∈B |E∨(b)|. Solution: Find the cardinality |E|. For each a ∈ A there are |E(a)| pairs (a, y) ∈ E and so |E| = ∑ a∈A |E(a)|. Similarly, for each b ∈ B there are |E∨(b)| pairs (x, b) ∈ E and therefore |E| = ∑ b∈B |E∨(b)|. Equating these two expressions for |E| gives the result. 4. If there are 40 students in the class, their surnames can’t all start with different letters (because there are only 26 letters). What can be said if there are 80 students in the class Solution: The Pigeonhole Principle says that there must be ,8026- = 4 students whose surnames begin with the same letter. This doesn’t mean that there is nec- essarily a letter which ‘has’ exactly 4 students, but there must be a letter which has at least 4. Recall the reasoning: if each of the 26 letters were to have at most 3 students, then there could be at most 26× 3 = 78 students. 5. How many six-digit numbers are there (not starting with 0) How many of these have six different digits Explain your answers. Solution: The six-digit numbers are all the numbers greater than or equal to 100000 and less than 1000000, so there are 900000 of them. Another way to count them is to note that there are 9 possibilities for the first digit, and then choosing the other digits is an ordered selection of 5 from 10 possibilities with repetition allowed, so the total is 9 × 105. The number of six-digit numbers which have no repeated digits is 9 × 9(5) = 9 × 9 × 8 × 7 × 6 × 5 = 136080, because there are 9 choices for the first digit, and then choosing the other digits is an ordered selection of 5 from 9 possibilities with repetition not allowed. 6. A permutation of {1, 2, 3, 4, 5} can be thought of as a number with these five digits in some order, such as 21453 or 41352. There are 5! = 120 such numbers. 2 (a) How many of these numbers start with 5 and end with 2 Solution: To specify such a number we just need to specify the order of 1, 3, 4 in the middle three digits; there are 3! = 6 possible orders. (b) How many have a first digit which is larger than the second digit Solution: The smart answer is that the first digit is just as likely to be larger than the second digit as it is to be smaller (and they can’t be equal), so exactly half of the 120 numbers have the required property. Another way to get the answer 60 is to note that there are ten possibilities for the first two digits (21, 31, 32, 41, 42, 43, 51, 52, 53, or 54), and for each of these there are six possibilities for the last three digits, as in the previous part. (c) How many have the property that the first digit is larger than the second, which is smaller than the third, which is larger than the fourth, which is smaller than the fifth (Hint : what positions can the digit 1 occupy in such a number ) Solution: Clearly the digit 1 must be in either second place or fourth place, because otherwise it would have to be larger than some other digit. Because the condition is symmetric, the numbers satisfying the condition where 1 is the fourth digit are just the reversals of the numbers satisfying the condition where 1 is the second digit. So we only need to consider one of these cases: say that 1 is the second digit. Then the requirements that the first digit is larger than the second, and the second smaller than the third, are automatically satisfied. There are four possible choices for the first digit. Whatever first digit is chosen, there are three out of {2, 3, 4, 5} remaining to fill the last three digits, and the requirements mean that we have to choose the smallest of these three as the fourth digit; the other two can be the third and fifth digits in either order. So there are 4×2 = 8 numbers satisfying the condition where 1 is the second digit, and another 8 where 1 is the fourth digit, so 8 + 8 = 16 is the answer to the question. *7. Use the Pigeonhole Principle to prove that for any positive integer n, there is a multiple of n which has no digits other than 0’s and 1’s (in its usual decimal expression). Solution: Consider the set of numbers X = {1, 11, 111, 1111, · · · , 111 · · ·1}, where the last number is a string of n ones. If any of the elements of X is a multiple of n, then we are done, so suppose none of them is a multiple of n. We then have a function from X to the set {1, 2, · · · , n 1}, given by taking the remainder after division by n. By the Pigeonhole Principle, this function cannot be injective, since |X| > |{1, 2, · · · , n 1}|. So there must be two elements of X which have the same remainder after division by n. Subtracting the smaller from the larger gives a multiple of n which has the form 11 · · ·100 · · ·0, so we are done. 3 The University of Sydney School of Mathematics and Statistics Solutions to Tutorial 2 (Week 3) MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022 1. Suppose you have 7 different ornaments to put on your mantelpiece. (a) If you want to use all of them, how many possible arrangements are there Solution: There are 7 choices for which ornament goes first, then 6 choices for which goes next, then 5, etc. So the answer is 7! = 5040. (b) If you want to use 6 of them, how many possible arrangements are there Solution: By the same reasoning as in the previous part, the answer is 7 × 6 × 5 × 4 × 3 × 2, which is also 5040. It makes sense that the answer should be the same as the previous part, because you can imagine storing the unused ornament at the right-hand edge of the mantelpiece and thus ‘using’ it after all. (c) If you can use all, some, or none of them, how many possible arrangements are there Solution: If you use k of the ornaments, then by the same reasoning as in the previous parts, the number of possible arrangements is 7(k) = 7! (7 k)! . So the answer is 7! 0! + 7! 1! + 7! 2! + 7! 3! + 7! 4! + 7! 5! + 7! 6! + 7! 7! = 13700. *(d) Divide your answer to part (c) by your answer to part (a); this ratio measures how much extra freedom you get by not necessarily using all the ornaments. Notice that it agrees with e up to four decimal places. Is this a coincidence Solution: The ratio is 137005040 = 2.718253 · · · , whereas e = 2.718281 · · · . This is no coincidence, because the ratio can also be written as 1 0! + 1 1! + 1 2! + 1 3! + 1 4! + 1 5! + 1 6! + 1 7! , i.e. the sum of the first eight terms of the series ∞∑ n=0 1 n! , which is well known to converge to e. 2. An ordinary knock-out singles tennis tournament (with no seeds or byes) consists of a series of rounds. In each round, the remaining players play against each other in pairs, with the losers being eliminated and the winners going through to the next round; in the last round, the only two remaining players play the final match to determine the winner of the tournament. Suppose that there are 7 rounds. (a) How many players are there at the start of the tournament Solution: Every round halves the number of remaining players. So if you imagine starting at the end with the sole winner and going back in time, the number of players is multiplied by 2 for every round, and there must have been 27 = 128 players at the start. Copyright c 2022 The University of Sydney 1 (b) How many matches are played in total Solution: The smart answer is that every match eliminates one player, and all but one of the original players gets eliminated, so there are 127 matches. An alternative method is to note that there are 26 = 64 matches in the first round, 25 = 32 matches in the second, and so on up to 20 = 1 match in the last round (the final), so the answer is 26+25+ · · ·+20, which equals 27 1 by the formula for the sum of a geometric progression. (c) Before the tournament starts, the organizers need to construct the draw, which specifies who plays who in the first round, and then which first-round winners play which other first-round winners in the second round, and so on. Of course, the organizers don’t know who the first-round winners will be, so in the draw they are just thought of as “the winner of the match between player X and player Y”, and so forth. How many possible draws are there Use the fact, proved in lectures, that the number of ways to group 2k people into k pairs is (2k)! 2kk! . (The answer is too large to evaluate, so just leave it as a fraction of expressions involving a factorial.) Solution: Since there are 128 players at the start, the number of possi- bilities for who plays who in the first round is 128! 264 64! . Then there are 64 players to be paired off in the second round (their actual identities may not be known, but they can be identified by what first-round match they won); the number of ways to do this is 64! 232 32! , and so forth. In the final round there are only two players, and only 2! 211! = 1 way to pair them off, obviously. By the Product Principle, the total number of draws is the product of all these numbers, which is 128! 64! 32! 16! 8! 4! 2! 264+32+16+8+4+2+1 64! 32! 16! 8! 4! 2! 1! = 128! 2127 . (d) Suppose that after the tournament is finished, the only things that are recorded are the draw and the winners of each match. How many differ- ent such records are possible Solution: Given the draw, the number of possible outcomes of the tour- nament is 2127, because each of the 127 matches can have 2 possible winners. So by the answer to the previous part, the number of possible records is 128! 2127 2127 = 128!. This answer is of course the same as the number of ways of ordering the 128 players. The explanation for this is that you can use the record of the tournament to number the players, as follows. The winner of the final is player 1, and the loser of the final is player 2. The other semi-finalists are numbered 3 and 4, with player 3 being the one who lost to player 1 and player 4 being the one who lost to player 2. Then the other quarter-finalists are numbered 5 up to 8, with player n+4 being the one who lost to player n for 1 ! n ! 4; and so on until all the players are numbered. This gives a bijection between the possible records and the numberings of the players. So the fact that there are 128! possible records also follows from the Bijection Principle. 2 3. Let X = {m,m+ 1, · · · , n 1, n} be a set of consecutive positive integers, and A the subset of X consisting of those elements which are multiples of 3. You would expect |A| to be about |X|3 , but the latter is not always an integer, so you may have to round it up or down. (a) Give an example where |A| does not equal $ |X|3 %. Solution: One example is X = {3, 4, 5, 6}, where A = {3, 6}. Here $ |X|3 % = $ 4 3% = 1, whereas |A| = 2. (b) Show that if X = {1, 2, · · · , n}, then |A| = $n3 %. Solution: If a is a positive integer, then 3a ! n if and only if a ! $n3 %. So A = {3× 1, 3× 2, · · · , 3× $n3 %}, and the result follows. (c) Hence give a formula for A when X = {m,m + 1, · · · , n} and m ” 2. Solution: Let Y = {1, 2, · · · , m 1} and Z = {1, 2, · · · , n}, and let B and C be the subsets of Y and Z respectively consisting of multiples of 3. Then X is the complement of Y in Z, and A is the complement of B in C. Hence by the Difference Principle, |A| = |C| |B| = n 3 m 1 3 . *4. If m is a positive integer, write v2(m) for the exponent of the highest power of 2 that divides m. For example: v2(m) = 0 m is odd, v2(m) = 1 m is even but not a multiple of 4, v2(m) = 2 m is a multiple of 4 but not of 8, etc. (a) Show that v2(mm′) = v2(m) + v2(m′) for all integers m,m′. Solution: We can write m = 2v2(m)m0 and m′ = 2v2(m ′)m′0 where m0 and m′0 are odd. So mm ′ = 2v2(m)+v2(m ′)m0m ′ 0 where m0m ′ 0 is odd, which shows that v2(mm′) = v2(m) + v2(m′). (b) Prove that for all positive integers n, v2(n!) = n 2 + n 22 + n 23 + n 24 + · · · · · · . (Note that although this sum appears to go on forever, all the terms will be zero from a certain point on, because when 2k > n we have $ n2k % = 0.) Solution: By definition, n! is the product of the numbers 1, 2, 3, · · · , n. So by the previous part, v2(n!) = v2(1) + v2(2) + · · ·+ v2(n). Now imagine the numbers 1, 2, · · · , n as positions in a line, with a stack of v2(i) blocks put at position i. We want to count the total number of blocks; we can do this by adding up the number of blocks in the bottom level, the number of blocks in the second level, and so on (once the level is sufficiently high, there will be no more blocks). The number of blocks in the kth level from the bottom is the number of elements i ∈ {1, 2, · · · , n} such that v2(i) ” k, which by definition is the number of multiples of 2k in {1, 2, · · · , n}. So there are $ n2k % blocks in the kth level, and adding up the levels gives the claimed formula. 3 (c) Deduce that v2((2n)!) = n+ v2(n!). How could this be proved another way Solution: By the previous part with n replaced by 2n, v2((2n)!) = 2n 2 + 2n 22 + 2n 23 + 2n 24 + · · · = n+ n 2 + n 22 + n 23 + · · · = n+ v2(n!). Another proof of this fact comes from the observation made in lectures that (2n)! = 2nn!(2n 1)!!, where (2n 1)!! is the product of the odd integers from 1 up to 2n 1. Since (2n 1)!! is odd, v2(2 nn!(2n 1)!!) = v2(2 n) + v2(n!) + v2((2n 1)!!) = n + v2(n!) + 0, as required. *5. Let Fn be the set of functions f : {1, 2, . . . , n} → {1, 2, . . . , n} such that if i < j then f(i) ! f(j), and for all i, f(i) ! i. Given two rows of boxes with n boxes in each row, . . . . . . a standard tableau is obtained by placing the numbers 1, 2, . . . , 2n bijectively in the boxes so that the numbers increase from left to right in each row and so that each number in the bottom row is larger than the number in the box above it. Let Tn be the set of standard tableaux with entries 1, 2, . . . , 2n. Construct a bijection Fn → Tn. [The cardinality |Fn| = |Tn| is known as the n-th Catalan number ]. Solution: Wemay represent a function by the list of its values: f(1)f(2) . . . f(n). Begin with an increasing function f as described and then create a two-rowed tableau with first row f(1), f(2) + 1, f(3) + 2, . . . , f(n) + n 1 and whose second row consists of the remaining integers from {1, 2, . . . , 2n} in ascending order. For i < j we have f(i) ! f(j) and therefore f(i) + i 1 < f(j) + j 1. Thus the first row begins with 1 and is strictly increasing. Moreover, f(n) + n 1 < 2n and therefore the last entry in the bottom row is 2n. We need to see that the values increase down the columns. We can think of filling the tableau beginning at the leftmost column and proceeding to the right. When we come to fill the k-th column, the top row will be the one obtained by restricting f to {1, 2, . . . , k} and so the k-th entry in the bottom row must be at least 2k. Conversely, if we begin with a standard tableau with two rows of length n, we construct the increasing function from the first row of the tableau by subtracting k 1 from the value in the k-th box for k = 1, . . . , n. The value in the top box of the k-th row is always less than 2k; that is, f(k) + k 1 < 2k and so f(k) ! k, as required. 4 **6. Use the Pigeonhole Principle to prove that for any odd integer m " 3, at least one of the numbers 22 1, 23 1, · · · , 2m 1 1 is divisible by m. Solution: Let X = {1, 2, · · · , m 1}, and let f : X → X be the function which takes n to the remainder after dividing 2n by m (it is impossible for this remainder to be 0, since no odd number greater than 1 can exactly divide a power of 2). Suppose that f(n) = 1 for some n ∈ X : then 2n 1 is divisible by m, and we clearly cannot have n = 1, so the desired result follows. Henceforth we assume that f(n) *= 1 for all n ∈ X , and try to find a contradiction. Our assumption means that the range of f is a subset of Y = {2, · · · , m 1}, whose size is strictly smaller than |X|. By the Pigeonhole Principle, f : X → Y cannot be injective, so there must be two different elements n1 < n2 in X such that f(n1) = f(n2). This means that 2n1 and 2n2 have the same remainder after division by m, so their difference 2n2 2n1 = 2n1(2n2 n1 1) has remainder 0, i.e. is divisible by m. Since m is odd, it must divide the 2n2 n1 1 part, which means that 2n2 n1 has remainder 1. But n2 n1 is clearly an element of X , and we have shown that f(n2 n1) = 1, contradicting our assumption. This finishes the proof. 5 The University of Sydney School of Mathematics and Statistics Solutions to Tutorial 3 (Week 4) MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022 1. A factory makes jelly beans of 15 different flavours, which it sells in bags of 10. If the jelly beans in a bag must all have different flavours, how many possible kinds of bag are there What about if this restriction is removed Solution: We are making an unordered selection of 10 from 15 possibilities. If repetition is not allowed (i.e. you can’t repeat a flavour), the answer is ( 15 10 ) = 3003. If repetition is allowed, the answer is ( 15+10 1 10 ) = 1961256. 2. If there are 10 chairs in a row and 8 students who want to sit down, you would normally say there are 10(8) = 1814400 possible outcomes (a case of ordered selec- tion with repetition not allowed). What unusual circumstances would make you change this answer to 108 How about ( 10 8 ) or ( 17 8 ) Solution: The answer would be 108 if repetition was allowed; in the context of the question, this would mean that more than one student was allowed to sit in a single chair (in fact, for the answer to be truly 108, you would even have to allow the possibility that all the students sit in the same chair). The answer would be ( 10 8 ) if repetition was not allowed, but the students were indistinguishable in the sense that it didn’t matter which student sat where – in this case, it is an unordered selection, and you are really just choosing which 8 of the 10 chairs are occupied. The answer would be ( 10+8 1 8 ) = ( 17 8 ) if repetition was allowed and it was an unordered selection – in other words, if more than one student per chair was allowed, and the students were indistinguishable – in which case you are really just choosing how many students are sitting on each chair, with a fixed total of 8. 3. Suppose that A and B are subsets of some set X , and |A| = 140, |B| = 92. (a) Find |A ∪ B|, given that |A ∩ B| = 36. Solution: By the Inclusion/Exclusion Principle, we have |A ∪B| = |A|+ |B| |A ∩ B| = 140 + 92 36 = 196. (b) Find |A ∩ B|, given that |A ∪ B| = 150. Solution: By the Inclusion/Exclusion Principle, we have |A ∩B| = |A|+ |B| |A ∪ B| = 140 + 92 150 = 82. *(c) Prove that it is impossible to have another subset C of X such that |C| = 58, |A ∩ B| = 32, |A ∩ B ∩ C| = 10, |A ∪ B ∪ C| = 250. Copyright c 2022 The University of Sydney 1 Solution: Suppose there exists a C with these properties. Then by the Inclusion/Exclusion Principle, we have 250 = |A ∪ B ∪ C| = |A|+ |B|+ |C| |A ∩B| |A ∩ C| |B ∩ C|+ |A ∩B ∩ C| = 140 + 92 + 58 32 |A ∩ C| |B ∩ C|+ 10 = 268 |A ∩ C| |B ∩ C| But both A∩C and B∩C contain A∩B ∩C, so |A∩C| ≥ 10, |B∩C| ≥ 10. Thus 250 ≤ 268 10 10 = 248, which is a contradiction. Hence no such set C exists. 4. If you are dealt 5 cards from a standard deck of 52 (4 suits, each containing A,K,Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2), the number of possible hands is ( 52 5 ) = 2598960. (a) How many of these hands contain the ace of spades Solution: If we know that the hand contains the ace of spades, choosing the rest of it amounts to choosing 4 cards from the other 51. So the answer is ( 51 4 ) = 249900. (b) How many of the hands contain exactly two aces Solution: There are four aces in the deck, so we can choose the two aces in ( 4 2 ) = 6 ways. Then we have to choose the remaining 3 cards from the 48 non-aces, which can be done in ( 48 3 ) ways. So the answer is 6 ( 48 3 ) = 103776. (c) How many of the hands contain at least two aces Solution: We need to add to the previous answer the number of hands which contain exactly three aces and the number which contain all four aces. The number which contain exactly three aces is 4 ( 48 2 ) = 4512, and the number which contain all four aces is ( 48 1 ) = 48, by the same reasoning as in the previous part. So the answer is 103776+ 4512+ 48 = 108336. Note that the answer is not ( 4 2 )( 50 3 ) , as you might expect if you thought of choosing two aces first and then choosing the three other cards. The reason is that this will count hands which have more than two aces more than once. (d) How many of the hands are a full house (three of one value and two of another, with no condition on the suits) Solution: We can choose the values involved in 13(2) = 13 × 12 = 156 ways (13 choices for the value which occurs three times and 12 choices for the value which occurs twice). Then we can choose the suits for the triplet in ( 4 3 ) = 4 ways and the suits for the pair in ( 4 2 ) = 6 ways. So the answer is 156× 4× 6 = 3744. (e) How many of the hands are a flush (all of the same suit), but not a straight flush (all of the same suit and five consecutive values, counting J= 11, Q= 12, K= 13, A= 14) 2 Solution: The number of flushes (including straight flushes) is 4× ( 13 5 ) = 5148, because you can choose the suit in 4 ways and then the cards from that suit in ( 13 5 ) ways. The number of straight flushes is 4× 9 = 36, because once the suit is chosen you just need to specify the lowest card of the straight, which can be anything from 2 to 10 (inclusive). So the number of flushes which are not a straight flush is 5148 36 = 5112. *(f) By replacing “at least two” with “at least zero” in part (c), show the equality( 52 5 ) = ( 4 0 )( 48 5 ) + ( 4 1 )( 48 4 ) + ( 4 2 )( 48 3 ) + ( 4 3 )( 48 2 ) + ( 4 4 )( 48 1 ) . Of what general identity is this a special case Solution: Obviously every hand has at least zero aces, so the number of hands with at least zero aces is ( 52 5 ) . But we could also work it out as in part (c), by dividing into the cases of no aces, one ace, two aces, three aces, and four aces, and these would give rise to the terms of the sum on the right-hand side. This proves the equality. The same argument shows the general identity: ( n k ) = k∑ k1=0 ( n1 k1 )( n n1 k k1 ) , for all 0 ≤ n1 ≤ n and k ≥ 0 (notice that some of the terms on the right-hand side may be zero, if k1 > n1 or k k1 > n n1; the argument still works). 5. The 4 players in a bridge game (North, South, East, and West) are each dealt 13 cards from the same deck of 52. (a) How many possible deals are there (assuming that it matters who gets which cards) Solution: A deal corresponds to a way of writing the set of all 52 cards in the deck as a disjoint union of four numbered subsets of size 13. These are counted by the multinomial coefficient( 52 13, 13, 13, 13 ) = ( 52 13 )( 39 13 )( 26 13 ) = 52! (13!)4 . *(b) In how many of these deals do North and South end up with all the spades between them Solution: The easiest way to count this is to imagine that you first remove all the spades from the deck, and then make 3 hands of 13 from the remaining 39 cards, in ( 39 13,13,13 ) ways. The first two of these three hands can then be given to East and West. The remaining hand can be mixed back with the spades, and then those 26 cards divided between North and South in ( 26 13,13 ) ways. So the answer is( 39 13, 13, 13 )( 26 13, 13 ) = 39! 26! (13!)5 . 6. In this question you should use the Stirling numbers S(5, 2) = 15, S(5, 3) = 25, S(5, 4) = 10 computed in lectures. 3 (a) Count the surjective functions {1, 2, 3, 4, 5}→ {1, 2, 3, 4}. Solution: By the result proved in lectures, the answer is 4!S(5, 4) = 24× 10 = 240. (b) Count the ways of assigning five students to five tutors so that exactly one of the tutors is not assigned any students. Solution: There are 5 ways to choose which tutor gets no students, and having made this choice the number of ways is the same as the surjective functions counted in the previous part. So the answer is 5× 240 = 1200. (c) Count the ways of assigning five students to four tutors so that at most two of the tutors are assigned students. Solution: If the number of tutors who are assigned students is 2, then there are ( 4 2 ) = 6 ways to choose which two, and then 2! × S(5, 2) = 30 ways to do the assignation. If only one tutor is assigned any students, there are 4 ways to choose which one, and then the assignation is automatically determined. So the answer is 6× 30 + 4 = 184. (d) Write n5 as a linear combination of binomial coefficients ( n k ) . Solution: Using the formula n5 = 5∑ k=1 k!S(5, k) ( n k ) , we get n5 = ( n 1 ) + 30 ( n 2 ) + 150 ( n 3 ) + 240 ( n 4 ) + 120 ( n 5 ) . *7. The Bell number B(n) is defined to be the total number of partitions of the set {1, 2, · · · , n} (or any set with n elements). Thus B(n) = ∑n k=0 S(n, k). Prove the following recurrence relation for the Bell numbers: B(n) = n∑ i=1 ( n 1 i 1 ) B(n i), for all n ≥ 1. (Hint: say that the first step in constructing a partition of {1, 2, · · · , n} is to choose the block containing n.) Solution: To construct a partition of the set {1, 2, · · · , n}, we can first choose the block containing n, and then all that remains is to choose a partition of the complement of that block. The size i of the block containing n can be anything from 1 to n, and for each specified i the block can be chosen in ( n 1 i 1 ) ways (since we know it contains the element n, so we only need to choose i 1 of the remaining n 1 elements). The complement then has size n i, so there are B(n i) ways to choose a partition of it. The desired equation follows. *8. Suppose that m, k ∈ N with m ≥ k. Prove that the number of surjective functions f : {1, 2, · · · , m}→ {1, 2, · · · , k} equals ∑ m1,m2,··· ,mk≥1 m1+m2+···+mk=m ( m m1, m2, · · · , mk ) . 4 How many terms are there in this sum Solution: A surjective function f : {1, 2, · · · , m} → {1, 2, · · · , k} is completely determined by the preimages f 1(1), f 1(2), · · · , f 1(k), which are all nonempty, and of which {1, 2, · · · , m} is the disjoint union. If the size of f 1(i) is mi, then we must have mi ≥ 1 and m1 +m2 + · · ·+mk = m. Having fixed the sizes of the preimages, the number of ways of choosing them is by definition the multinomial coefficient ( m m1,m2,··· ,mk ) . So we get the formula in the question. The problem with this formula is that the number of terms in the sum is too large for it to be of any practical use. Choosing themi’s is equivalent to choosing the ni’s where ni = mi 1; these are nonnegative integers which add up to m k. We saw in lectures that the number of ways of choosing a k-tuple of nonnegative integers which add up to n is( n+k 1 k 1 ) , so the number of terms in our sum is ( m 1 k 1 ) . **9. Prove the formula S(n, k) = 1 k! k∑ i=0 ( 1)i ( k i ) (k i)n by induction on n, using the recurrence relation for the Stirling numbers. Solution: When n = 0, the left-hand side is 1 if k = 0 and 0 otherwise. The right-hand side is 1 k! k∑ i=0 ( 1)i ( k i ) (k i)0 = 1 k! k∑ i=0 ( 1)i ( k i ) = 1 k! (1 + ( 1))k, which is obviously also 1 if k = 0 and 0 otherwise. Now assume that n ≥ 1, and that the formula for S(n 1, k) holds. The recurrence relation then gives S(n, k) = S(n 1, k 1) + k S(n 1, k) = 1 (k 1)! k 1∑ i=0 ( 1)i ( k 1 i ) (k i 1)n 1 + k k! k∑ i=0 ( 1)i ( k i ) (k i)n 1 = 1 (k 1)! [ k∑ i=1 ( 1)i 1 ( k 1 i 1 ) (k i)n 1 + k∑ i=0 ( 1)i ( k i ) (k i)n 1 ] = 1 (k 1)! k∑ i=0 ( 1)i (( k i ) ( k 1 i 1 )) (k i)n 1 = 1 (k 1)! k∑ i=0 ( 1)i ( k 1 i ) (k i)n 1. To derive the claimed formula and complete the induction step, we need only use the fact that ( k 1 i ) = k i k ( k i ) , which follows easily from the formula ( n i ) = n(i) i! . Note that the result can also be obtained from the Inclusion/Exclusion count of surjective functions given in lectures, since the number of surjective functions {1, 2, · · · , n}→ {1, 2, · · · , k} is k!S(n, k). 5 The University of Sydney School of Mathematics and Statistics Solutions to Tutorial 4 (Week 5) MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022 1. Prove by induction that, for all n ≥ 0, (a) n3 + 5n is a multiple of 3 (i.e. n3 + 5n = 3! for some integer !). Solution: The n = 0 case holds because 03 + 0 = 0 is a multiple of 3 (it is 3× 0). Suppose that n ≥ 1 and that the result is known for n 1, i.e. (n 1)3 + 5(n 1) = 3!, for some integer !. Then 3! = n3 3n2 + 3n 1 + 5n 5 = n3 + 5n 3(n2 n+ 2) , so n3 + 5n = 3(!+ n2 n + 2) is a multiple of 3, establishing the inductive step and completing the proof. (b) 5n 4n 1 is a multiple of 16. Solution: The n = 0 case holds because 50 4 × 0 1 = 0 is a multiple of 16. Suppose that n ≥ 1 and that the result is known for n 1, i.e. 5n 1 4(n 1) 1 = 16!, for some integer !. This equation can be rewritten as 5n 1 = 4n 3 + 16!. So 5n 4n 1 = 5(4n 3 + 16!) 4n 1 = 16(n 1 + 5!) , which is a multiple of 16, establishing the inductive step and completing the proof. 2. Use the characteristic polynomial to solve the following recurrence relations: (a) an = 5an 1 6an 2 for n ≥ 2, where a0 = 2, a1 = 5. Solution: The characteristic polynomial is x2 5x + 6 = (x 2)(x 3) with roots 2 and 3, so the general solution is an = C12n + C23n for some constants C1, C2. In our case we have 2 = a0 = C1 + C2 and 5 = a1 = 2C1 + 3C2. Solving yields C1 = C2 = 1, so the solution is an = 2 n + 3n. Copyright c 2022 The University of Sydney 1 (b) an = 4an 1 3an 2 for n ≥ 2, where a0 = 1, a1 = 2. Solution: The characteristic polynomial is x2 4x + 3 = (x 1)(x 3) with roots 1 and 3, so the general solution is an = C11n + C23n for some constants C1, C2. In our case we have 1 = a0 = C1 + C2 and 2 = a1 = C1 + 3C2. Solving yields C1 = 5/2 and C2 = 3/2, so the solution is an = 3n+1 5 2 . (c) an = 4an 1 4an 2 for n ≥ 2, where a0 = 3, a1 = 8. Solution: The characteristic polynomi
