# Math 239 Assignment 14

Math 239 Spring 2014 Assignment 0 Solutions 1. {6 marks} Counting This is a review of some counting problems. We only require the final answer, and you do not need to expand large powers, factorials and binomial coefficients. (a) A binary string is a sequence of digits where each digit is either 0 or 1. A string is a palindrome if it reads the same forwards and backwards (for example, 101101 and 00100 are palindromes). How many binary strings of length 13 are palindromes? Solution. If a1 a2 · · · a13 is a palindrome, then ai = a13−i for each i = 1, 2, 3, 4, 5, 6. Each of these pairs can be 0 or 1, and also a7 can be 0 or 1. So the total is 27 = 128. (b) There are 7 seats around a round table available for the 7 participants of a discussion panel. Among the 7 participants, 2 of them are married and hence cannot sit next to each other. How many ways can these 7 people be seated? Solution. Suppose A and B are the married couple. There are 7 choices of seats for A. Once we placed A, there are only 4 choices of seats for B, since B cannot be next to A. After A, B are seated, we can place the remaining 5 people into 5 seats in 5! ways. So the total is 7 · 4 · 5! = 3360. (c) For a hypothetical group project, there are 15 combinatorial students that need to be divided into three groups of 5 students each. How many groupings are possible? (Note that the groups are indistinguishable, so if we had only 3 students divided into three groups of 1 student each, there is only 1 way to do it.) Solution. We first count it as if the order of the groups matter. Then there are 15 5 ways to choose the first group. We have 10 remaining students, so there are 10 5 ways to choose the second group. The remaining 5 students will form the third group in 1 way. However, we have overcounted here, since the order does not matter. Since there are 3 groups, each unordered grouping will appear in 3! ways. So the total number is 10 (15 5 )( 5 ) = 126126. 3! 2. {4 marks} Power series We will be using the coefficients of power series to solve some counting problems. Consider the following two power series: X X f (x) = 1 + x + x2 + x3 + x4 + · · · = xi , g(x) = 1 − x + x2 − x3 + x4 − · · · = (−x)i i≥0 Determine the coefficient of x 2014 2 i≥0 2 in (f (x)) and f (x)g(x). 2 Solution. In (f (x)) = (1 + x + x + x3 + · · · )(1 + x + x2 + x3 + · · · ), in order to get x2014 , we need terms xi from the first series and x2014−i in the second series, for i = 0, 1, . . . , 2014. Since there are 2015 terms contributing to x2014 each with coefficient 1, the required coefficient is 2015. In f (x)g(x), the situation is similar, except we have (−1)2014−i x2014−i from the second series. So now odd i’s P2014 contribute −1 to x2014 while even i’s contribute 1 to x2014 . So the required coefficient is then i=0 (−1)2014−i = 1. 3. {3 marks} Recurrence relation Let {an }n≥0 be the sequence defined by a0 = 6, a1 = 12, and for any integer n ≥ 2, an − 4an−1 + 4an−2 = n − 1. You will learn how to find an explicit formula for recurrences like this. For now, we will give the answer to you and ask you to prove that for any integer n ≥ 0, an = (n + 3)(2n + 1). Solution. We can do this by strong induction on n. When n = 0, a0 = (0 + 3)(20 + 1) = 6. When n = 1, a1 = (1 + 3)(21 + 1) = 12. So the base cases hold. Now assume that for some integer k ≥ 1, ai = (i + 3)(2i + 1) for all 0 ≤ i ≤ k. Then ak+1 = 4ak − 4ak−1 + (k + 1) − 1 by the recurrence k = 4(k + 3)(2 + 1) − 4(k + 2)(2k−1 + 1) + k k k = 4k2 + 4k + 12 · 2 + 12 − 4k2 k−1 by ind hyp − 4k − 8 · 2k−1 − 8 + k = k(2k+2 − 2k+1 ) + (6 · 2k+1 − 2 · 2k+1 ) + 4 + k = k · 2k+1 + 4 · 2k+1 + 4 + k = k(2k+1 + 1) + 4(2k+1 + 1) = (k + 4)(2k+1 + 1). So by induction, the result holds. 4. {2 marks} Graph theory For each of the following figures, decide whether or not it can be drawn in one stroke without repeating any line segments (a point of intersection can be visited multiple times). This may sound like child’s play, but it relates to one of the first problems that was studied in graph theory. Circle all figures for which only one stroke is needed (and do not circle others), no explanations required. Solution. This is possible for the second and third drawings, but not the other two. 5. {3 marks} Matching There are 5 jobs available to 5 possible candidates. In the following diagram, there is a straight line joining a candidate and a job if and only if that candidate had an interview for that job. Assume that each candidate can hold at most one job, each job can be filled by at most one candidate, and only those candidates that have been interviewed for a job are eligible for it. If you attempt to match the candidates to the jobs, you may find this to be an impossible task in this instance. Give a reasonable explanation as to why that is the case. Candidates Alice Bob Cindy Dave Eve Jobs Face Goo Inst Micro Twit Solution. Notice that Alice, Cindy and Dave collectively are only interviewed for two jobs Inst and Twit. So at least one of them cannot get a job. Alternatively, notice that the jobs Face, Goo and Micro collectively only interviewed Bob and Eve, so one of these jobs cannot get a candidate. 6. {4 marks} Colouring A famous result in graph theory is the 4-colour theorem, which tells us that in any map, it is possible to use just 4 colours to paint the regions so that bordering regions receive different colours. Here is a simplified problem on colouring, which will also give you a taste of induction in perhaps an unfamiliar situation. We are given a rectangle with several line segments, each joining border to border inside of the rectangle. This divides the rectangle into several regions. We wish to colour these regions with red and blue so that any two regions that border each other through some line segment receive different colours (two regions that touch each other at only a point may have the same colour). An example is given below. Prove (using induction on the number of line segments) that regardless of how we divide the rectangle, such a colouring is always possible. Solution. Using induction on the number of lines n in the rectangle. When n = 0, the rectangle is just one region, and we can colour it with either red or blue. Assume that for some integer k ≥ 0, any rectangle that is divided by k line segments has a proper colouring using red and blue. Suppose a rectangle R has k + 1 line segments. Take any one line and remove it. The resulting rectangle R0 has k line segments, so by induction hypothesis, there is a proper colouring of its regions using red and blue. We keep the colouring of R0 and transfer it to R. Now we put the removed segment back into the rectangle. This line divides the rectangle into two parts, say P1 and P2 . We now switch all the colours in P1 (from red to blue, and from blue to red). In the new colouring, two regions that are adjacent inside P1 or two regions that are adjacent inside P2 still have different colours. Two regions that are adjacent via the line segment we removed are split from one region in R0 . Because we have changed the colour of that part in P1 , these two regions now have different colours. So our colouring of R is valid. Math 239 Spring 2014 Assignment 1 Solutions 1. {4 marks} Let n ≥ 2 be an integer. The n children of the Von Trapp family all have different ages. Whenever they sing, they will all line up so that the oldest child is to the right of the youngest child (it does not have to be directly to the right, for example, the oldest child could be 3 to the right of the youngest child). How many ways can they line up? Use a bijection to prove your answer. (For notation, you may label the n children in order of age from the youngest as 1, 2, . . . , n. Represent one possible line up as a permutation σ : [n] → [n] where σ(i) represents the position of the i-th youngest child in the line up, counting from the left.) Solution. We could formulate the problem as the set S T be the set of all permutations where σ(1) > σ(n). We f (σ) = σ 0 where σ(n) σ(1) σ 0 (i) = σ(i) of all permutations σ of [n] where σ(1) < σ(n). Let define the function f : S → T where for each σ ∈ S, i=1 i=n otherwise In other words, we are switching σ(1) and σ(n) to produce σ 0 . Notice that since σ(1) < σ(n), we must have σ 0 (1) > σ 0 (n), so f (σ) ∈ T . Also, the mapping f −1 : T → S with the same operation as f is the inverse of f . So f is a bijection. This implies that |S| = |T |. Since S ∪ T is the set of all permutations of [n] and S ∩ T = ∅, |S| + |T | = n!, hence |S| = n!/2. 2. {3 marks} Let n ≥ 3 be an integer. How many subsets of [2n] have exactly 3 odd integers and any number of even integers? Describe two sets S and T such that the answer to our question is |S × T |, then determine what is this answer. Solution. Let S be the set of all subsets of {1, 3, . . . , 2n − 1} of size 3. Let T be the set of all subsets of {2, 4, . . . , 2n}. For any set X that is a subset of [2n] with exactly 3 odd integers, X = A ∪ B and where A ∈ S n n B ∈ T . So the total number of subsets X that we want is exactly |S × T |. Since |S| = and |T | = 2 , the 3 total number is n3 2n . 3. {4 marks} Let a, b, c, n be positive integers such that a ≤ b ≤ c ≤ n. Consider the following set. S = {(A, B, C) | A ⊆ B ⊆ C ⊆ [n], |A| = a, |B| = b, |C| = c}. By counting S in two different ways, prove that n n−a n−b n c b = . a b−a c−b c b a Solution. We will count the set of all triples in S in two ways. In the first method, we will choose A first. Since A is an a-subset of [n], there are na ways to pick A. After we have picked A, we note that B must include A, so out of the b elements of B, a of them are chosen. So we need to choose b − a elements out of [n] \ A, which has size n − a. So for every A, there are n−a possible B. After b−a we have picked A, B, we note that C must include B, so out of the c elements of C, b of them are chosen. So we need to choose c − b elements out of [n] \ B, which has size n − b. So for every choice of A and B, there are n−b n n−a n−b ways to choose C. In total, |S| = c−b a b−a c−b . In the second method, we will choose C first. Since C is a c-subset of [n], there are nc ways to pick C. After we have picked C, we see that B is a b-subset of C, so there are cb ways to choose B. After we have picked B, we see that A is an a-subset of B, so there are ab ways to choose A. In total, |S| = nc cb ab , hence the identity holds. 4. Consider the following identity. n X n n−i 3 = 2 . i i=0 n (a) {4 marks} Give a combinatorial proof of this identity. Solution. Consider the set S = {1, 2, 3}n , which consist of all n-tuples (a1 , . . . , an ) where each ai ∈ {1, 2, 3}. Clearly |S| = 3n . We partition S into n + 1 sets S0 , . . . , Sn where for each i = 0, . . . , n, Si is the set of elements of S that contains exactly i 1’s. We can count Si by first deciding which i of the n spots are 1’s, then fill in the remaining n − i spots with either 2 or 3. There are ni ways to choose the i spots, and 2n−i ways to fill in the remaining spots. So |Si | = ni 2n−i . Since S = S0 ∪ · · · ∪ Sn is a disjoint union, n X n n−i 3n = 2 . i i=0 (b) {3 marks} Give an algebraic proof of this identity. (You may assume the binomial theorem.) Solution. By the binomial theorem, n n X X n n j (1 + 2x) = (2x) = (2x)j . j n − j j=0 j=0 n Putting i = n − j, we get n X n (1 + 2x) = (2x)n−i . i i=0 n Substitute x = 1 to get the identity. 5. Let S be the set of all subsets of [3]. (a) {2 marks} Let w be the weight function on S such that w(∅) = 0, and for any nonempty set A ∈ S, w(A) is the sum of all elements of A. Determine the generating series ΦS (x) with respect to w. Solution. We can check the weight of each subset of [3]: w(∅) = 0, w({1, 2}) = 3, w({1}) = 1, w({1, 3}) = 4, w({2}) = 2, w({2, 3}) = 5, w({3}) = 3, w({1, 2, 3}) = 6. Using these weights, we see that ΦS (x) = 1 + x + x2 + 2x3 + x4 + x5 + x6 . (b) {2 marks} Let w∗ be the weight function on S such that for any A ∈ S, w∗ (A) = 3w(A). Determine the generating series Φ∗S (x) with respect to w∗ . Solution. The weights from part (a) are all tripled, so the new generating series is Φ∗S (x) = 1 + x3 + x6 + 2x9 + x12 + x15 + x18 . (c) {2 marks} In general, let T be a set and let w be a weight function on T . Let ΦT (x) be the generating series with respect to w. For a positive integer k, define w∗ to be the weight function on T where for any a ∈ T , w∗ (a) = k · w(a). Let Φ∗T (x) be the generating series with respect to w∗ . Use the definition of generating series to determine a relationship between ΦT (x) and Φ∗T (x). Solution. Using the definition of generating functions, we have X ∗ Φ∗T (x) = xw (σ) σ∈T = X xk·w(σ) σ∈S = X (xk )w(σ) σ∈S = ΦS (xk ). Math 239 Spring 2014 Assignment 2 Solutions 1. {6 marks} Consider the following power series. f (x) = 157 X (−3)i−2 x2i = x4 − 3x6 + 9x8 − · · · − 3155 x314 g(x) = i=2 X f (x)i . i≥3 (a) Express both f (x) and g(x) as rational functions, i.e. p(x) q(x) where p(x), q(x) are explicit polynomials (you should be able to write them out without resorting to sums). Simplify your expressions as much as possible. Solution. We first factor out x4 from f (x). Re-indexing gives us f (x) = x4 155 X 155 X (−3)i x2i = x4 i=0 (−3x2 )i . i=0 Using geometric series, f (x) = x4 x4 − 3156 x316 1 − (−3x2 )156 . = 1 − (−3x2 ) 1 + 3x2 For g(x), we can factor out f (x)3 first, and then use geometric series (this is possible since the constant term in f (x) is 0). 4 156 316 3 x −3 x 3 1+3x2 f (x) (x4 − 3156 x316 )3 3 i g(x) = f (x) f (x) = = = . 4 156 316 x 1 − f (x) (1 + 3x2 )3 − (1 + 3x2 )2 (x4 − 3156 x316 ) 1 − x −3 1+3x2 i≥0 X (b) Does g(x) have an inverse? If so, determine a rational function for it. If not, explain why not. Solution. We see that the constant term in f (x) is 0, and g(x) is equal to f (x)3 multiplied by some series. So the constant term in g(x) is 0, therefore g(x) does not have an inverse. 2. {4 marks} Using mathematical induction on k, prove that for any integer k ≥ 1, X n + k − 1 (1 − x)−k = xn . k−1 n≥0 Solution. When k = 1, holds. n+k−1 k−1 = n 0 = 1. So (1 − x)−1 = Assume that for some positive integer m, (1 − x)−m = P n≥0 P n≥0 n+m−1 m−1 xn = P n≥0 n+1−1 k−1 xn . So the base case xn . We need to prove the equation for m + 1. We see that (1 − x)−(m+1) = (1 − x)−m (1 − x)−1 . i −1 By induction hypothesis, [xi ](1 − x)−m = i+m−1 = 1. Using rules of m−1 . Also, we know that [x ](1 − x) multiplication of power series, we get [xn ](1 − x)−(m+1) = n n X X i+m−1 n+m ([xi ](1 − x)−m )([xn−i ](1 − x)−1 ) = = m−1 m i=0 i=0 where the final step uses an identity from class. Therefore, −(m+1) (1 − x) = X n + m n≥0 Therefore, by induction, the result holds. m xn . 3. {4 marks} Determine the value of the following coefficient. [x26 ](3 + x2 )(1 − 2x6 )−31 (1 + x9 )−41 . Solution. We see that [x26 ](3 + x2 )(1 − 2x6 )−31 (1 + x9 )−41 = 3[x26 ](1 − 2x6 )−31 (1 + x9 )−41 + [x24 ](1 − 2x6 )−31 (1 + x9 )−41 . Note that in the expansion of (1 − 2x6 )−31 (1 + x9 )−41 , the exponents of x are integer combinations of 6’s and 9’s. Such exponents are multiples of 3, so the coefficient of x26 is 0. The required coefficient is then equal to the coefficient of x24 in (1 − 2x6 )−31 (1 + x9 )−41 . There are 2 ways to get x24 in this multiplication: [x24 ](1 − 2x6 )−31 [x0 ](1 + x9)−41 and [x6 ](1 − 2x6 )−31 [x18 ](1 + x9 )−41 . These correspond to the numbers 24 4+31−1 · (−1)0 and 21 1+31−1 · (−1)2 2+41−1 31−1 31−1 41−1 . So the required 31 42 4 34 coefficient is 2 30 + 2 30 40 = 795398. 4. {4 marks} Let {an }n≥0 be a sequence whose corresponding power series A(x) = A(x) = P i≥0 ai xi satisfies −6 − 34x . 1 + 2x − 3x2 Determine a recurrence relation that {an } satisfies, with sufficient initial conditions to uniquely specify {an }. Use this recurrence relation to find a4 . Solution. We see that (1 + 2x − 3x2 )A(x) = −6 − 34x. So −6 − 34x = (1 + 2x − 3x2 )(a0 + a1 x + a2 x2 + a3 x3 + · · · ) X = a0 + (a1 + 2a0 )x + (an + 2an−1 − 3an−2 )xn n≥2 By comparing the coefficients, we see that a0 = −6; a1 + 2a0 = −34, so a1 = −22; and an + 2an−1 − 3an−2 = 0 for n ≥ 2. These are the initial conditions and the recurrence that {an } satisfies. To get a4 , we apply the recurrence relation. a2 = −2a1 + 3a0 = 26 a3 = −2a2 + 3a1 = −118 a4 = −2a3 + 3a2 = 314 5. Let n ∈ N. For a permutation σ : [n] → [n], we use the notation (σ(1)σ(2) · · · σ(n)) to describe the mapping. A pair of integers (i, j) is called an inversion of σ if i < j and σ(i) > σ(j). For example, the permutation (32415) on [5] has 4 inversions: (1, 2), (1, 4), (2, 4), (3, 4). Define the weight function w on a permutation σ to be the number of inversions in σ. Let Sn be the set of all permutations of [n]. (a) {2 marks} Determine the generating series for S1 , S2 , S3 with respect to w. (No work required.) Solution. S1 = {(1)}, which has 0 inversions. So ΦS1 (x) = 1. For S2 , (12) has no inversions, but (21) has one inversion. So ΦS2 (x) = 1 + x. For S3 , (123) has no inversions, (132), (213) have one inversion, (231), (312) have two inversions, and (321) has three inversions. So ΦS3 (x) = 1 + 2x + 2x2 + x3 . (b) {4 marks} Prove that for n ≥ 2, ΦSn (x) = (1 + x + · · · + xn−1 )ΦSn−1 (x). You may use the following (non-standard) notation: If σ is a permutation of [n], denote σ 0 to be the permutation of [n − 1] obtained from σ by removing the element n. For example, if σ = (31524), then σ 0 = (3124). Solution. We split Sn into n sets according to the location of the element n in the permutation. For i = 1, . . . , n, let Ti be the set of all permutations σ ∈ Sn where σ(i) = n. Then Sn = T1 ∪ T2 ∪ · · · ∪ Tn . For each Ti , we can form a bijection between Ti and Sn−1 as follows: f : Ti → Sn−1 where f (σ) = σ 0 . We now compare the number of inversions between σ and σ 0 . Each inversion in σ 0 is still an inversion of σ. However, there are additional inversions introduced by n in σ. Since n is the largest possible element in σ, it creates an inversion with any element after it. Since σ(i) = n, there are n − i additional inversions, namely (i, i + 1), (i, i + 2), . . . , (i, n). Therefore, w(σ) = w(σ 0 ) + (n − i). Since we have a bijection between Ti and Sn−1 , we can say that ΦTi (x) = xn−i ΦSn−1 . Using the sum lemma, we get ΦSn (x) = n X i=1 ΦTi (x) = n X xn−i ΦSn−1 (x) = (1 + x + x2 + · · · + xn−1 )ΦSn−1 (x). i=1 (c) {2 marks} Prove that the number of permutations of [n] with k inversions is Qn (1 − xi ) k . [x ] i=1 (1 − x)n Solution. We see that ΦS1 (x) = 1 from part (a), so this is satisfied for n = 1. Using induction, we see that ΦSn (x) = (1 + x + · · · + xn−1 )ΦSn−1 (x) by part (b) 1 − xn ΦSn−1 (x) = 1−x Qn−1 1 − xn i=1 (1 − xi ) = by ind hyp 1 − x (1 − x)n−1 Qn (1 − xi ) = i=1 (1 − x)n Math 239 Spring 2014 Assignment 3 Solutions 1. {4 marks} Let n ∈ N. Suppose we have an unlimited supply of Canadian nickels, dimes, quarters, loonies, and toonies (they are worth 5, 10, 25, 100, 200 cents each, respectively). How many ways can we make n cents using these coins such that the number of nickels is at least the number of quarters? Note that coins with the same denomination are considered to be identical, so we only care about the number of coins of each denomination. You may say that your answer is equal to a certain coefficient of a power series. Solution. Let Ck = {0, k, 2k, 3k, 4k, . . .}. Each collection of coins can be represented by a 5-tuple (n, d, q, l, t) ∈ C5 × C10 × C25 × C100 × C200 . We define the weight of such a 5-tuple to be w(n, d, q, l, t) = n + d + q + l + t, which represents the value of this collection of coins in cents. To ensure that the number of nickels is at least the number of quarters, we will consider the set Sn to be those collections with exactly n quarters. Then Sn = {5n, 5(n + 1), 5(n + 2), 5(n + 3), . . .} × C10 × {25n} × C100 × C200 . Using the weight function α(a) = a for each set in the cartesian product, by product lemma, ΦSn (x) = 1 1 x30n 1 x5n · · x25n · · = . 5 10 100 200 5 10 1−x 1−x 1−x 1−x (1 − x )(1 − x )(1 − x100 )(1 − x200 ) Now the set of all valid collections is S = ΦS (x) = n≥0 Sn . So by the sum lemma, x30n − x100 )(1 − x200 ) X n≥0 = S (1 − x5 )(1 − x10 )(1 1 (1 − x5 )(1 − x10 )(1 X − x100 )(1 − x200 ) x30n n≥0 1 . = 5 10 (1 − x )(1 − x )(1 − x30 )(1 − x100 )(1 − x200 ) The answer is then [xn ]ΦS (x). 2. {4 marks} Let n ∈ N. How many compositions of n consists of either 5 or 6 parts, and each part is even? Determine a generating series for the set of all such compositions (for all n), and then determine an explicit formula for the answer. Solution. Let Ne = {2, 4, 6, 8, . . .} be the set of all positive even integers. The set of all compositions that we want is then S = N5e ∪ N6e . Using the weight α(a) = a for Ne , we have ΦNe (x) = x2 + x4 + x6 + x8 + · · · = x2 . 1 − x2 Define the weight of a composition as the sum of its parts. Then using the sum lemma and the product lemma, we get ΦS (x) = ΦN5e (x) + ΦN6e (x) 5 6 x2 x2 = + 1 − x2 1 − x2 5 x2 x2 = 1 + 1 − x2 1 − x2 5 x2 1 = 2 1−x 1 − x2 10 x = . (1 − x2 )6 The answer to our question is then [xn ] x10 1 = [xn−10 ] = (1 − x2 )6 (1 − x2 )6 n−10 +5 2 0 5 n is even and n ≥ 10 otherwise 3. Let n be a non-negative integer, and let Sn be the set of all compositions of n where each part is greater than 1. (The number of parts is not restricted.) Let an = |Sn |. (a) {4 marks} Prove that an = [xn ] 1−x . 1 − x − x2 Solution. Let A = {2, 3, 4, . . .}. Then the set that we are counting is [ S= Ak . k≥0 We use the weight function α(a) = a for A and the sum of the parts as the weight of a composition. Then ΦA (x) = x2 + x3 + · · · = x2 . 1−x Using the sum lemma, we get ΦS (x) = X ΦAk (x) k≥0 = X (ΦA (x))k by product lemma k≥0 1 by geometric series 1 − ΦA (x) 1 1−x = . = x2 1 − x − x2 1 − 1−x = 1−x So the answer is [xn ] 1−x−x 2. (b) {4 marks} The generating series from part (a) gives us the recurrence an = an−1 + an−2 for n ≥ 2. Give a combinatorial proof of this recurrence by finding a bijection between Sn and Sn−1 ∪ Sn−2 , and finding its inverse. Solution. We define a function f : Sn → Sn−1 ∪ Sn−2 as follows: For any (a1 , . . . , ak ) ∈ Sn , (a1 , . . . , ak−1 , ak − 1) ak ≥ 3 f (a1 , . . . , ak ) = (a1 , . . . , ak−1 ) ak = 2 For the first case, we have ak ≥ 3, so ak − 1 ≥ 2. So each part of the result (a1 , . . . , ak−1 , ak − 1) is still greater than 1, and they sum up to n − 1, hence it is in Sn−1 . For the second case, by removing the last part, each part is still greater than 1, and all the parts add up to n − 2, hence it is in Sn−2 . Therefore, f is well-defined. The inverse is the function g : Sn−1 ∪ Sn−2 → Sn as follows: For any (b1 , . . . , bl ) ∈ Sn−1 ∪ Sn−2 , (b1 , . . . , bl−1 , bl + 1) b1 + · · · + bl = n − 1 g(b1 , . . . , bl ) = (b1 , . . . , bl , 2) b1 + · · · + bl = n − 2 So f is a bijection (c) {2 marks} Illustrate your bijection by matching up compositions in S7 with compositions in S6 and S5 . Solution. S5 ∪ S6 : (5) (2, 3) (3, 2) (6) (2, 4) (3, 3) (4, 2) (2, 2, 2) S7 : (7) (2, 5) (3, 4) (4, 3) (5, 2) (2, 2, 3) (2, 3, 2) (3, 2, 2) 4. Let n ∈ N. Consider the problem of finding the number of compositions of n with exactly 3 parts (a1 , a2 , a3 ) such that 1 ≤ a1 < a2 < a3 . For example, when n = 9, there are three such compositions: (1, 2, 6), (1, 3, 5), (2, 3, 4). Let S be the set of all such compositions, i.e. S = {(a1 , a2 , a3 ) | 1 ≤ a1 < a2 < a3 }. We will determine the generating series of S with the help of another set T = N × N × N, which is the set of all compositions with exactly 3 parts. (a) {3 marks} Define a bijection f : S → T , and write down its inverse f −1 . Illustrate your bijection by determining f (2, 3, 9) and f −1 (3, 1, 4). Solution. Define f where for each (a1 , a2 , a3 ) ∈ S, f (a1 , a2 , a3 ) = (a1 , a2 − a1 , a3 − a2 ). Notice that since a3 > a2 > a1 ≥ 1, each part of (a1 , a2 − a1 , a3 − a2 ) is positive, hence f (a1 , a2 , a3 ) ∈ T . For the inverse f −1 : T → S, for each (b1 , b2 , b3 ) ∈ T , f −1 (b1 , b2 , b3 ) = (b1 , b1 + b2 , b1 + b2 + b3 ). We can check that this is valid: for each (a1 , a2 , a3 ) ∈ S, f −1 f (a1 , a2 , a3 ) = f −1 (a1 , a2 − a1 , a3 − a2 ) = (a1 , a1 + (a2 − a1 ), a1 + (a2 − a1 ) + (a3 − a2 )) = (a1 , a2 , a3 ). And vice versa. So f is a bijection. As illustrations, f (2, 3, 9) = (2, 1, 6) and f −1 (3, 1, 4) = (3, 4, 8). (b) {2 marks} Let w be the weight function on S where w(a1 , a2 , a3 ) = a1 + a2 + a3 . For each (b1 , b2 , b3 ) ∈ T , define a weight w∗ (b1 , b2 , b3 ) such that w∗ (f (a1 , a2 , a3 )) = w(a1 , a2 , a3 ) for all (a1 , a2 , a3 ) ∈ S. (You need to prove that this property holds.) Solution. We define w∗ (b1 , b2 , b3 ) = 3b1 + 2b2 + b3 . Then for each (a1 , a2 , a3 ) ∈ S, w∗ (f (a1 , a2 , a3 )) = w∗ (a1 , a2 − a1 , a3 − a2 ) = 3a1 + 2(a2 − a1 ) + (a3 − a2 ) = a1 + a2 + a3 = w(a1 , a2 , a3 ). (c) {3 marks} Determine the generating series of T with respect to w∗ , and explain why this is the same as the generating series of S with respect to w. (Hint: You may use question 5(c) from assignment 1.) Solution. For T = N × N × N, we can think of the weight functions α(a) = 3a, β(b) = 2b, γ(c) = c for the x2 x x3 three N in order. The generating series for N with respect to these 3 weight functions are 1−x 3 , 1−x2 , 1−x respectively. Then using the product lemma, the generating series for T with respect to the weight function w∗ is x6 . Φ∗T (x) = 3 (1 − x )(1 − x2 )(1 − x) The reason that this is equal to the generating series for S with respect to w can be shown using the definition of generating series: X ΦS (x) = xw(a1 ,a2 ,a3 ) (a1 ,a2 ,a3 )∈S = X xw ∗ (f (a1 ,a2 ,a3 )) by part (b) (a1 ,a2 ,a3 )∈S = X (b1 ,b2 ,b3 )∈T = Φ∗T (x). xw ∗ (b1 ,b2 ,b3 ) since f is a bijection Math 239 Spring 2014 Assignment 4 Solutions 1. {6 marks} For each of the following expressions representing sets of binary strings, determine if it is ambiguous or unambiguous. If it is ambiguous, provide an example that can be decomposed in two different ways. If it is unambiguous, determine the generating series (as a simplified rational expression) with respect to the lengths of strings. (a) ({1}∗ {001, 0001}∗ )∗ Solution. This is ambiguous. In particular, the empty string ε is inside the main ∗, so it can be written as εε and εεεε. (b) {10001, 001, 00110}∗ Solution. This is ambiguous. Consider the string 00110001. This can be decomposed in two different ways: (001, 10001) and (00110, 001). (c) {00}∗ ({11}{111}∗ {0}{000}∗ )∗ {1, 11, 111} Solution. This is unambiguous (in the same way that the block decomposition is unambiguous). The generating series is ! (1 − x3 )2 (x + x2 + x3 ) 1 1 2 3 (x + x + x ) = . 2 x x 1 − x2 1 − 1−x (1 − x2 )(1 − 3x3 + x6 ) 3 1−x3 2. {9 marks} For each of the following sets of binary strings, determine an unambiguous expression which generates every string in that set (no justification required). (a) The set of binary strings where the length of each block of 0’s is divisible by 3 and the length of each block of 1’s is divisible by 4. Solution. S = {000, 1111}∗ . (b) The set of binary strings where each block of 1’s of odd length is followed by a block of 0’s of length at least 3. Solution. We use the block decomposition. The middle two-block combination is either odd 1’s followed by at least 3 0’s, or even 1’s followed by any number of 0’s. The last part must be either empty or an even block of 1’s, for it does not have any block of 0’s following it. S = {0}∗ ({1}{11}∗ {000}{0}∗ ∪ {11}{11}∗ {0}{0}∗ )∗ {11}∗ . (c) The set of binary strings which contain 000111 as a substring. (Note: An obvious wrong answer is {0, 1}∗ (000111){0, 1}∗ .) Solution. Take all the strings and remove those that do not contain 000111 as a substring. For such a string, any block of 0’s of length at least 3 can be followed by a block of 1’s of length at most 2, and any block of 0’s of length 1 or 2 can be followed by any number of 1’s. S = {0, 1}∗ \ {1}∗ ({000}{0}∗ {1, 11} ∪ {0, 00}{1}{1}∗ )∗ {0}∗ . 3. {5 marks} On Martin’s new game show “It Peis to Play”, there is an unlimited supply of gold and silver coins buried inside a box of sand. As a contestant, you dig up one coin at a time, and Martin will offer you $3 for each gold coin and $1 for each silver coin. You may stop at any time and keep your winnings. However, if you dig up 3 gold coins in a row or 4 silver coins in a row, the game is over and you lose everything. (For this question, you may represent your answers as coefficients of simplified rational expressions.) (a) For some n ∈ N, how many ways can you win exactly $n from Martin and walk away with your winnings? Solution. We set this up as a binary string problem, where 0 represents a silver coin and 1 represents a gold coin. For a string s, we define the weight function w(s) to be the number of 0’s plus 3 times the number of 1’s in s. In this problem, we need the set of all binary strings with no 4 consecutive 0’s and no 3 consecutive 1’s. This can be expressed as the following unambiguous expression: {ε, 0, 00, 000}({1, 11}{0, 00, 000})∗ {ε, 1, 11}. Using the new weight function, we see that the generating series is (1 + x + x2 + x3 ) 1 1− (x3 + x6 )(x + x2 + x3 ) (1 + x3 + x6 ) = (1 + x + x2 + x3 )(1 + x3 + x6 ) . 1 − (x3 + x6 )(x + x2 + x3 ) n The answer is then the coefficient of [x ] in this generating series. (b) For some n ∈ N, suppose you have won $n, but decided to be greedy and then lost everything on the next dig. How many ways can this happen? Solution. Using the same set up as part (a), we now need the set of all binary strings with no 4 consecutive 0’s and no 3 consecutive 1’s, which end with either 000 or 11. (This assumes that the next bit will be the same.) An unambiguous expression for this is {ε, 0, 00, 000}({1, 11}{0, 00, 000})∗ {11} ∪ {ε, 1, 11}({0, 00, 000}{1, 11})∗ {000}. The generating series for this is (1 + x + x2 + x3 )x6 + (1 + x3 + x6 )x3 . 1 − (x3 + x6 )(x + x2 + x3 ) The answer is then the coefficient of [xn ] in this generating series. 4. {4 marks} Let S be the set of binary strings where a block of 0’s cannot be followed by a block of 1’s of greater length. For example, 111110010001110 is in S, but 100011110010 is not. Prove that the generating series for S with respect to the lengths of the strings is ΦS (x) = 1+x . 1 − x − 2x2 + x3 (Hint: You may want to consider using the set T = {01, 0011, 000111, 00001111, . . .}.) Solution. The configuration that we want to avoid is a block of 0’s followed by a block of 1’s of greater length, which can be described as T {1}{1}∗ . By modifying the block decomposition, we see that S = {1}∗ ({0}{0}∗ {1}{1}∗ \ T {1}{1}∗ )∗ {0}∗ . Now ΦT (x) = x2 + x4 + x6 + · · · = x2 . 1 − x2 So, ΦS (x) = 1 1−x1− 1 x2 (1−x)2 − x2 x 1−x2 1−x 1 1−x 1 (1 − x)2 (1 + x) (1 − x)2 (1 − x)2 (1 + x) − x2 (1 + x) + x3 1+x = . 1 − x − 2x2 + x3 = 5. {4 marks} Let T be the set of all binary strings that do not have 0001 as a substring. Determine a recursive definition for T . Briefly explain why your definition is correct and unambiguous. Use this to find the generating series for T with respect to the lengths of the strings. Solution. We split T into two sets T0 and T1 where T0 are strings in T that do not have any 1’s, and T1 are strings in T that have at least one 1. The strings in T0 are simply those with only 0’s, so T0 = {0}∗ . For a string in T , break it after the first 1. The first part is either 1, 01, or 001, and the remaining string is still in T . So we may define T by T = {0}∗ ∪ {1, 01, 001}T. This is correct and unambiguous because in the description above, there is only one way to decompose a string in T in this form. For the generating series, we have ΦT (x) = Φ{0}∗ (x) + Φ{1,01,001} (x)ΦT (x) = 1 + (x + x2 + x3 )ΦT (x). 1−x Solving for T gives us ΦT (x) = 1−x 1 1−x − x2 − x3 = 1 . 1 − 2x + x4

Help

## MATH 267 HOMEWORK ASSIGNMENTS

(1) Thislist is a minimum requirement andproblems with *areforyour additional practice.If time allows, try work on more problems of your own choice from the text book.

(2) Working these problems in a careful and timely manner is the *most important way* you have to learnthe material.

Week #1

Section 1.3,page 16/#3, 7, 13, 17, 22;

Section 2.1, page 28/ #8, 12, 18; 28;||16*

Week #2

Section 2.2,page 39/#1, 4, 15, 22; || 14*

Section 2.3,page 50/#8, 17 || 14*.

Section 2.4,page 62/#1, 3, 5, 7, 13, 15, 17, 21, 23, 33, 38|| 22*, 27*

Week #3

September07:Sect. 2.6,page 85/#9-11,19,21,26, 28;

September 09:page 87 / #22, 24,33-36, 44,47;

September 10:Sect. 2.7, page 98 /# 1,2,8, 10, 15 .

Week #4

September 13: Section 2.9, page 116 / #2, 6, 9, 18, 21, 26, 28 .

September 14: Section 4.1, page 172/ # 1, 3, 5, 7,10, 13;

September16:Quiz2

September 17:page 173/ #12,14, 17, 18.

Section 4.2, page 177/#5, 8

Section 4.3, page 189/#1, 3, 5

Week #5

September 20: Section 4.3, page 189 / #8, 10, 12, 14, 16, 18; 20, 22, 24, 28 || 29*

September 21: Section 4.4, page 197/ #1, 7,12,14;

September 23: Section 4.5, page 207 / #2, 4, 6,8,12, 14, 16, 18, 20, 23;

September 24:Section 4.5, page 208/ # 24, 26, 28, 30, 32, 3839, 43, 44.

This Assignment #5, due September 27: page 189, #10, 16; page 197, #7; page 207,#5, 14;page 208, #24 (answers)

Week #6

The in-class Exam #1 will be on Tuesday, Sept. 28,the topics to be coveredis up to Section 4.4.

This is the Exam #1 and the answers.

Sept. 27,Section 4.6, page 214/ # 1, 3, 5, 11, 14.

Sept. 30, Section 4.7, page 223/ #1, 14, 17;

Oct. 01, Section 5.1, page 239/ #1, 3, 5, 7, 9,12, 25, 27;

Week #7

Oct. 04,Section 5.2, page 246/ # 6, 12, 15, 18, 24, 27, 29, 32,34, 39.

Oct. 05, Section 5.3,page 254 / # 1, 7, 10, 13, 15,27, 31, 34, 36.

Oct. 07,Section 5.4, page 263/ #1, 5, 8, 13, 18, 24, 27, 32;

Oct. 08, Section 5.5, page 276/ #3, 13, 15.

Assignment #6, due October 14: page 246, #24;page 254, #31;page 263,#24;page 276, #15(answers)

Week #8

October 11, Section 5,5, page 276/ #18, 25, 26, 29;

October 12, Section 5.6, page 286/ #3, 7, 9.

Page 296/ #20, 22, 24, 26.

October 14, Section 6.1, page 310 / #1,6, 12, 18, 28, 30

October15, Section 6.2, page 318/ #1, 5, 9,15, 22;

** please findeul.m, rk2.m, rk4.m and some test examples by clickinghere ***

Week #9

October 18, Section 6.3, page 325/ #3, 7, 11.

October 19, reading Section 7.1-7.2.

October21, Section 7.3 / #6, 13,17,30;

Section 7.4/ #9,13,31;

Section7.5/ #1, 9, 25, 33.

October 22, Section 7.6/#7, 24, 34, 43.

Week #10

The in-class Exam #2 will be on Thursday,Oct.28,the topics to be covered

include: Section 4.5 - 4.6,5.1 - 5.7. 6.1—6.2.

October 25, Section 8.1, page 403/ #7, 11, 16.

October 26, Section 8. 4, page435/ #6, 14, 19, 24, 27, 33;

October 28, Exam#2.This is the Exam #2 and the answers.

October 29. Section 9.1/ #1, 10, 15,20, 24,30, 43||52*

Week #11

November 01, reading Section 9.1;

November 02,Section 9.2, page 463/# 1, 8, 22,23, 29,38, 44,49;

November04, Section 9.3,page 480/#1, 10, 16, 20, 25, 41;

November 05, Section 9.4, page 489/# 3, 7, 22, 36, 40;

Week #12

November 08,continue Sections 9.3-9.4

November 09,continue Section 9.4.

November 11,Section9. 5 / #3, 11,13, 17, 25, 34.

November 12,Section 9.6/#2, 5, 12.

Week #13

The in-class Exam #3 will be on Friday,Nov.19,the topics to be covered

include: Section 8.1,8.4,9.1- 9.6

November 15,continue Section 9.6;

November 16, Section 9.7/#1, 5, 10, 18, 22, 36;

November 18,review via doing a list ofpractice problems .Hear are partial answers.No regular class!

November 19,In-class Exam #3. This is the Exam #3and the answers.

Week #14

November 29, review of the exam#3.

November 30, Section 9.7/ #1, 5, 9,19, 23,29,33, 37;

December02,Section 9.8/ #1, 7, 11, 21, 25||29*;

December 03. Overview of Chapter 10.

Week #15

December06,Review #1

December 07, self-review, no class meeting.Here is a list of topics and a list practice problems.

December09,Review #2, review of all topics;

December 10,Review #3, doing more problems… see answers for review problems.

Week #16, Final week.

## 0 comments