Week 8 - Counting and recurrence

Tuesday, 9 April 2019

10:43 PM

 

 

n is the container

r is the amount

 

 Untitled picture.png The pigeonhole principle states that If p items are placed into n containers, then there exists a container which has at least | items. Recall that the celing function is the smallest integer greater than or equal to x. For example [1.6281 = 2. a) If 9 pigeons sleep in 5 nests, then there exists a nest with at least pigeons. Evaluate r ! l. b) If 57 pigeons sleep in 19 nests, then there exists a nest with at least r I pigeons. Evaluate Submit part Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Submit part Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png c) If p pigeons sleep in 19 nests, what is the largest value of p such that P 152 d) If 57 pigeons sleep in n nests, what is the smallest value of n such that 8? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered 7? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png c) If p pigeons sleep in 19 nests, what is the largest value of p such that P 152 d) If 57 pigeons sleep in n nests, what is the smallest value of n such that 8? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered 7? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png When using the pigeonhole principle, you will need to decided what are the pigeons and what are the containers. Suppose you are dealt a hand of 39 cards from a standard deck. a) How many cards, at least, are ofthe same colour? Show steps (Your score will not be affected.) 20 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered b) How many cards, at least, are ofthe same suit? Show steps (Your score will not be affected.) 10 Answer. 10 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part.
Untitled picture.png When using the pigeonhole principle, you will need to decided what are the pigeons and what are the containers. Suppose you are dealt a hand of 39 cards from a standard deck. a) How many cards, at least, are ofthe same colour? Show steps (Your score will not be affected.) 20 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered b) How many cards, at least, are ofthe same suit? Show steps (Your score will not be affected.) 10 Answer. 10 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Untitled picture.png c) How many cards, at least, have the same value? (Your score will not be affected.) Show steps Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png How many ways can you place indistinguishable r objects into n buckets, if objects can be selected more than once? The answer depends upon whether the order of selection is important. • Ifthe order of selection is important, then the number ofways is nr. • Ifthe order of selection is not important, then the number ofways is C(n + r The NUMBASsyntax for C(n, r) is . a) A dinner menu consists of 4 entrees, 4 main meals and 4 desserts. How many dinners are possible? 3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png How many ways can you place indistinguishable r objects into n buckets, if objects can be selected more than once? The answer depends upon whether the order of selection is important. • Ifthe order of selection is important, then the number ofways is nr. • Ifthe order of selection is not important, then the number ofways is C(n + r The NUMBASsyntax for C(n, r) is . a) A dinner menu consists of 4 entrees, 4 main meals and 4 desserts. How many dinners are possible? 3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png How many ways can you place indistinguishable r objects into n buckets, if objects can be selected more than once? The answer depends upon whether the order of selection is important. • Ifthe order of selection is important, then the number ofways is nr. • Ifthe order of selection is not important, then the number ofways is C(n + r The NUMBASsyntax for C(n, r) is . a) A dinner menu consists of 4 entrees, 4 main meals and 4 desserts. How many dinners are possible? 3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered b) You have to purchase 5 snacks to get yourself through your late night study session. The local store only has a selection of 4 snacks. What is the total number of ways you can choose snacks for the night? comb ( 8, 3) Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1
Untitled picture.png How many ways can you place indistinguishable r objects into n buckets, if objects can be selected more than once? The answer depends upon whether the order of selection is important. • Ifthe order of selection is important, then the number ofways is nr. • Ifthe order of selection is not important, then the number ofways is C(n + r The NUMBASsyntax for C(n, r) is . a) A dinner menu consists of 4 entrees, 4 main meals and 4 desserts. How many dinners are possible? 3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered b) You have to purchase 5 snacks to get yourself through your late night study session. The local store only has a selection of 4 snacks. What is the total number of ways you can choose snacks for the night? comb ( 8, 3) Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Untitled picture.png c) A band of 8 pirates plunders a booty of 5 gold soverigns. How many ways can the booty be divided between the pirates? comb (12, 7) Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered d) A total of 10 identical marbles must be placed into the buckets labeled , an, , :r5. How many ways can the marbles be placed into the buckets? comb (14, 4) Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png The number of non-negative integers solutions to the equation is C(n + r — 1, r — 1). The following questions invite you to explore variations ofthis identity. Remember that the NUMBAS syntax for C(n, r) is . a) How many non-negative integer solutions are there to the equation with no further restrictions? comb ( 6 9 , 3) 66 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png The number of non-negative integers solutions to the equation is C(n + r — 1, r — 1). The following questions invite you to explore variations ofthis identity. Remember that the NUMBAS syntax for C(n, r) is . a) How many non-negative integer solutions are there to the equation with no further restrictions? comb ( 6 9 , 3) 66 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png b) How many non-negative integer solutions are there to the equation with each x - > 3? 66 Assume that 3. We cannot use the above formula directly on this equation, so instead let's reformulate the question in terms of the new variableyj = % 3 > 0: Yi —3) + (o — = 66—3 x 4 — 54. You can think of yj as representing the 'extra' bit that - has on top of 3. Now we can apply the above formula because the only restriction is that yj 0. (Your score will not be affected.) Hide steps 57 Answer: comb (57, 3) C3 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png Machine generated alternative text: c) How many non-negative integer solutions are there to the equation with eachxj < 27? 66 Let U be the set of solutions without any restriction, and let Sj be the set of solutions where:rj > 27. The size of Sl can be found by replacing with — 28 and applying the given forumula. What is the size of Sr? comb (66-28+4-1, 3) What is the size of Sl n S2? comb What is the size of Sl n S2 n S3? Submit part Your answer is numerically correct. Not marked Submit part Your answer is numerically correct. Not marked Submit part Untitled picture.png Machine generated alternative text: By the inclusion/exclusion principle, the answer is IUI — + IS41) + (ISI n + (Your «ore will not be affected.) Hide steps . + n S41) Answer: comb (69,3) -4k (comb (66-28+4-1, 3) ) 3) 69C3 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png Machine generated alternative text: By the inclusion/exclusion principle, the answer is IUI — + IS41) + (ISI n + (Your «ore will not be affected.) Hide steps . + n S41) Answer: comb (69,3) -4k (comb (66-28+4-1, 3) ) 3) 69C3 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png Machine generated alternative text: d) How many non-negative integer solutions are there to the equation where each .r.j is even? Assume that Tj is even then define the new variableyj = x Then Yl+Y2+ 2 Now we can applythe above formula because the only restriction is thatyj 0. (Your «ore will not be affected.) Hide steps Answer: comb (36, 3) 66 33. Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png Machine generated alternative text: d) How many non-negative integer solutions are there to the equation where each .r.j is even? Assume that Tj is even then define the new variableyj = x Then Yl+Y2+ 2 Now we can applythe above formula because the only restriction is thatyj 0. (Your «ore will not be affected.) Hide steps Answer: comb (36, 3) 66 33. Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png Machine generated alternative text: Let pn be the probability that in a group of n people, at least two share the same birthday. Assume there are 365 days in a year, and that all birthdays are equally likely. a) What is the probability that in a group ofn people, at least two have the same birthday? You may use NUMBAS formula for I-perm (365, 2) /36SA2 3652 I-perm (365, 3) /36SA3 3653 I-perm (365, 4) /36SA4 p4 3654 I-perm (365, S) /36SAS 3655 Untitled picture.png Machine generated alternative text: What is the total number of ways to choose birhtdays for n people, with no restiction? 36SAn 365'1 Submit part Your answer is numerically correct. You were awarded 1 mark. Score: 1/1 Answered What is the number of ways that all n people can have different birthdays? Hint: there are 365 ways the first person can choose their birthday, then 364 choices for the second person, and so on. Use the NUMBAS command perm in your answer. perm (365, n) Submit part Your answer is numerically correct. You were awarded 1 mark. So the probability that at least two people have the same birthday is I—perm (365, n) / 36SAn 1 of that n people birthdayÆ 1 total nu mber of w3}Æ can birthdays 365p 365" Score: 1/1 Answered Submit part Your answer is numerically correct. You were awarded 1 mark.
Untitled picture.png Machine generated alternative text: What is the total number of ways to choose birhtdays for n people, with no restiction? 36SAn 365'1 Submit part Your answer is numerically correct. You were awarded 1 mark. Score: 1/1 Answered What is the number of ways that all n people can have different birthdays? Hint: there are 365 ways the first person can choose their birthday, then 364 choices for the second person, and so on. Use the NUMBAS command perm in your answer. perm (365, n) Submit part Your answer is numerically correct. You were awarded 1 mark. So the probability that at least two people have the same birthday is I—perm (365, n) / 36SAn 1 of that n people birthdayÆ 1 total nu mber of w3}Æ can birthdays 365p 365" Score: 1/1 Answered Submit part Your answer is numerically correct. You were awarded 1 mark. Untitled picture.png Machine generated alternative text: b) Consider the following values ofpn for 15 n < 25: P15 — P16 = P17 ¯ P18 = What is the smallest value of n such thatpn 0.5? 0.25 0.28 0.32 0.35 0.38 0.41 0.44 0.48 0.51 0.54 Submit part Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png Machine generated alternative text: b) Consider the following values ofpn for 15 n < 25: P15 — P16 = P17 ¯ P18 = What is the smallest value of n such thatpn 0.5? 0.25 0.28 0.32 0.35 0.38 0.41 0.44 0.48 0.51 0.54 Submit part Your answer is correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png Machine generated alternative text: A recurrence relation is an equation which can be used to construct a sequence from an initial value. A first order recurrence relation is of the form where Cl is constant and f(n) is a function ofn. When f(n) recurrence relation is both simple and fundamental. a) Consider the homogenous first order recurrence relation form r.rn = 3.Tn—1 to find 0 the recurrence relation is called homogenous. The concept of a homogenous . r.r2 18 54 162 e. = Oforn > Owith initial condition xo Gap 1 2. Re-arrange the relation into the Submit part Your answer is numerically correct. You were awarded 0.25 marks. Gap 2 Your answer is numerically correct. You were awarded 0.25 marks. Gap 3 Your answer is numerically correct. You were awarded 0.25 marks. Gap 4 Your answer is numerically correct. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Untitled picture.png b) The n'th term of a first order homogenous recurrence relation can be expressed in the form = Acn where c is determined by the coefficients, and A is determined by the initial conditions. This is also called the homogenous solution. What is the value of c in the homogenous solution for the above sequence? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered
Untitled picture.png b) The n'th term of a first order homogenous recurrence relation can be expressed in the form = Acn where c is determined by the coefficients, and A is determined by the initial conditions. This is also called the homogenous solution. What is the value of c in the homogenous solution for the above sequence? Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png c) Consider the non-homogenous first order recurrence relation into the form = — 6to find -24 -78 —6 forn > Owith initial condition xo Gap 1 2. Re-arrange the relation Submit part Your answer is numerically correct. You were awarded 0.25 marks. Gap 2 Your answer is numerically correct. You were awarded 0.25 marks. Gap 3 Your answer is numerically correct. You were awarded 0.25 marks. Gap 4 Your answer is numerically correct. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered ( Follows part (a) ) ﷐𝑥﷮0﷯=2 -> A ﷐ℎ﷮𝑛﷯=2﷐𝑐﷮𝑛﷯ ﷐ℎ﷮0﷯=﷐𝑥﷮0﷯=2=2﷐𝑐﷮𝑛﷯=2﷐𝑐﷮0﷯=2×1=2… ﷐ℎ﷮1﷯=﷐𝑥﷮1﷯=6=2﷐𝑐﷮𝑛﷯=2×﷐3﷮1﷯=2×3=6 𝑐=3
Untitled picture.png c) Consider the non-homogenous first order recurrence relation into the form = — 6to find -24 -78 —6 forn > Owith initial condition xo Gap 1 2. Re-arrange the relation Submit part Your answer is numerically correct. You were awarded 0.25 marks. Gap 2 Your answer is numerically correct. You were awarded 0.25 marks. Gap 3 Your answer is numerically correct. You were awarded 0.25 marks. Gap 4 Your answer is numerically correct. You were awarded 0.25 marks. You scored 1 mark for this part. Score: 1/1 Answered Untitled picture.png The n'th term of a first order non-homogenous recurrence relation can be expressed in the form where hr, is the homogenous solution, and pn is the non-homogenous solution. The sum of the homogenous and non-homogenous solutions is also called thesolution to the recurrence relation. Find the solution to — 3xn_1 = —6 subject to the initial condition = 2. There is no one method to finding pn, and so we must 'guess and check'. Suppose pn is a solution to the non-homogenous equation: Since the non-homogenous part f(n) = —6 is constant, we 'guess' that p.n The value of C is: C for some constant: —6. Submit part Your answer is numerically correct. You were awarded 0.5 marks. You scored 0.5 marks for this part. Score: 0.5/0.5 Answered The solution is hr, + C where hr, and C are determined above. Now apply the initial condition to determine the value of A, which is: Submit Dart Untitled picture.png The answer is hr, + pn A x 3R + C where A and C have the values determined above. (Your score will not be affected.) Hide steps Answer. - (3) "11+3 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. Because you received full marks for the part, your answers to the steps aren't counted. You scored 1 mark for this part. Score: 1/1 Answered Use your solution to evaluate :r7. —37+3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1
Untitled picture.png The answer is hr, + pn A x 3R + C where A and C have the values determined above. (Your score will not be affected.) Hide steps Answer. - (3) "11+3 Submit part You revealed the steps. Your answer is numerically correct. You were awarded 1 mark. Because you received full marks for the part, your answers to the steps aren't counted. You scored 1 mark for this part. Score: 1/1 Answered Use your solution to evaluate :r7. —37+3 Submit part Your answer is numerically correct. You were awarded 1 mark. You scored 1 mark for this part. Score: 1/1

 

 

Created with Microsoft OneNote 2016.