5

Problem 7: (10 points) Recall that string that contains only 0 $, 1's, and 2 s is called ternary string: (For example. 01122012 is ternary string of length 8) ...

Question

Problem 7: (10 points) Recall that string that contains only 0 $, 1's, and 2 s is called ternary string: (For example. 01122012 is ternary string of length 8) Let G, denote the number of ternary strings of length that do not contain two consecutive 0 s_ Find the values of & and 01.Find recurrence relation for the sequence {an}nzo:(iii) Solve the recurrence relation that you have obtained into find the closed form of an.

Problem 7: (10 points) Recall that string that contains only 0 $, 1's, and 2 s is called ternary string: (For example. 01122012 is ternary string of length 8) Let G, denote the number of ternary strings of length that do not contain two consecutive 0 s_ Find the values of & and 01. Find recurrence relation for the sequence {an}nzo: (iii) Solve the recurrence relation that you have obtained in to find the closed form of an.



Answers

a) Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.
b) What are the initial conditions?
c) How many ternary strings of length six do not contain two consecutive 0s or two consecutive 1s?

Okay, so here it And it's gonna be the number of turn ery strings, which means it's a bit. Is there a one and can contain a 01 or two Senator Neri strings, uh, link, then that Do not contain so say, without a pair of consecutive 000 right next to each other. Okay, so first, our string could start with a one. Right? And if that was the keys, it would have eighth e n minus one possible strings that would be without apparent your zeros. And the exact same thing could be said for the start of the two and then goes on right. The rest of the string length here is n minus one digits long. So there are eti n minus one ways he strings starting with the two, uh, could be without a pair of zero zero's. So then we consider the case where the sequence starts with a 01 and in this instance, how we're working with and minus two remaining digits, right? So there's going to be 80 and minus two ways. This string could be without a pair of zero zero's, and the same thing goes for if it has a 02 by the exact same logic. And this exhaust every possible string that would not contain a 00 Okay, so that means that a then the number of these turn ery strings without a pair of your zeros is gonna be equal to the A number of ways. It could be that starting with a one across the number of ways it could be without the Para zero starting with a two plus the number of ways it could be without the double zeros, starting with 01 and a zero tune. Of course, we have some, like, terms here. So we combine those we get that Evan is equal to 2 a.m. Ice one plus two times a to the N minus two. Okay. And so is this our recurrence relation? They moved to part B. Okay, So when n is equal to zero, we have ah, no string. Essentially the empty string. And that empty string contains one string that doesn't contain this pair zeros, right. The empty strain does not contain our double zero. So that's gonna be equal to one now on N is equal to one. We could have a zero a one or a two for our strings. And all three of those do not contain a pair of double zeros. Let's give equal to three. Okay, so these are our initial conditions and part see here wants us to see what happens when we have a a string of length six. So we'll start by finding a two. And this means that we want two times a one plus two times and not itself from our initial conditions. We know that this will be two times one is me. Two times three plus two times and not and not was one. It's gonna be six plus two is equal to eight. OK, it's a lot of the same thing For a three. This is gonna be two times a two plus two times a one. Okay, so two times a two is two times eight. I was just 16 and then a one was three. So two times three is six. So add six to that, and that is equal to 22 a four that is gonna give us two times a three's. That's going to times 22 plus two times a two, which was eight plus two times eight. How's that be? 44 plus 16 is equal to 60. Speed up a little bit here. Then, if you get the patterns of a five that is gonna be two times 6420 plus two times 22 is 44 is equal to 164 and lastly, a six is two times a fire. So two times 164 is 3 28 plus two times a +42 times 60. 420 is equal to 448 and that is the number of Turn Aires.

Hey, we're looking for a recurrence relation ship for the number of turn ery strings of length on containing two consecutive zeroes in a turn ery string is similar to a binary one, except instead of zeros and ones it zero ones and twos, Right, but sort of in any any capacity. We're looking at one that is an of length end, okay. And in particular containing two consecutive zeros. And so we can break this down into a handful of different cases. Um, see, Case one try to exhaust all other options here. So in this case, are sequence ends in a one with the first case we investigate. Okay, so then if the n wth element is the one that we're only considering n minus one length bit string Okay, so then that means that there is going to be a and minus one. Possible strings contain the pair of consecutive zeros if we let you know a n b number of consecutive of the possible strings that contain consecutive zeros. So, case, too somebody case well on, except instead, we're seeing is gonna end in a two. Well, just like above. We're not working with again. And minus one elements. And there's going to be then eight of the n minus one ways puzzle strings that could contain a hair of zeros. It's a case three. Well say ends in a one and his era. Same idea as before. Except now, we've removed two elements. So it's gonna be if a man is the member of ways, a pair of consecutive zeros. Then they pulled two honest men than a en masse to is the number of ways to get a CZ hair consecutive zeros that end in 10 So case three. I'm sorry, we're on four. So case four, then is one. And this is similar to case three. It's gonna end in a two in, then a zero, but we'll get the same answer. The concept is the same. And the last case that it ends in 00 Okay, well, in this case, we've already met the condition of having two these pair of consecutive zeros. And so then we just looking at how many possibilities how many possible strings are there of length and minus two rights. We start to remove these two from our length, and so there's three cc's. We could be a 01 or two to the power of and minus two bit strings of length and minus two. And so a of end here is gonna be We're gonna add all of these cases together, but you'll see that case one and two are like terms here. And case three and four were like terms, right? So this is actually going to be equal to to a and this one plus two AM I s too. And then I don't want to add this three to the power of a minus to as well. And that is our recursive relationship. Okay, but this was just part, eh? Okay, So Part B asks us what are the initial conditions? And so in n is equal to zero, it is their art. Zero bits in the strings and empty string. Then it does not. It cannot contain a pair of zeros. Right? So is zero must equal zero. And by a similar argument, when n is equal to one, regardless of whether that bit is a zero, it one or a two, there cannot exist a pair of consecutive zeros. So a string of length one. We'll also have zero pears of consecutive zeros. Okay, now one end is equal to two. There is exactly one bit string that contains a pair of zeros. It should be I string 00 Anything else? 10 or 1121 does not help. Okay, so so then we know that it, too, is also equal to one. We also put the case where any calls to into our recurrence relationship. Right. So we had Where is it to equal? Be to a one plus two. A zero plus 3 to 2 minus two, which would equal zero zero plus one is ableto one so that that matches. So whether you want to think about it by inspection for that case, or actually put it into a relationship, uh, you could see it ankles to Does not need to be an initial condition because it checks out from part, eh? And no part. See, we're gonna use the relationship that we have. So we had a zero equals zero if one equals zero. And of course, the relationship itself. Even two A and minus one plus two. It and my ass too. Plus three to the m I s too to derive a six. Okay, so it wants us to find a six. OK, so we know that a 000100 and also from the previous page eight to is equal to one. Okay. So that we can go ahead and calculate a 345 and six. So a three is gonna be too times two plus two times a one plus three. The power of three minutes to rights. That's gonna be equal to two times one plus two times zero plus three to the power of one. Just gonna be two plus three is equal to five on same idea. For the fourth case, what should be four times a three, which is five. So as two times a three, which is five plus two times a two, which is one plus three to the four minus two. Just meet the power of two. Yes, this is going to equal 10 plus two plus nine, which is 21 Kevin for the fifth case. Bring it two times. Previous cases. Just 21 plus two times a three, which is five. Has three are finalized. Chooses me three. Cute. I calculate that out we're gonna get 79. And, of course, the last case a six here's gonna equal to two times 79 plus two times 21 plus three to the power of four six minus two. Um, and with the help of the calculator, we get that that is equal to 281. And so there are 281.

Okay, so here we're letting a ll and be the number of turn ery strings, the length and which do not contain a pair of any consecutive numbers. So without a 00 11 nor a, uh to to OK, so first we consider a string that starts with a zero. Okay, so the remaining bit of string is length and minus one, and this comes start with either a one or a two. All right, so the number of such strings that start with a one or a two is gonna be equal to 2/3 e and minus one writes the length is and minus one, but it can't start with any number. It could just start with the one or two. That's 203 possible options for eternity. String by a similar argument. If the strings started, they won. You know, you get the length of n minus one again, and this time it can start with either a zero or a two, which again is going to be equal to 2/3. Aye, and minus one. And she might see what is going starts with a two er it can The next digit can either be a zero or one. All right, so it's again going to be equal to 2/3 a the n minus one. And so, if you add these altogether, that's what we want to do to find a n. All right, We end up getting three times. 2/3 There's three lum a and minus one. And so this is just gonna counsel out real nice, eh? So we get that. Hey, Sven is equal to two times a n minus one. Okay, so for part B, we want to find the initial conditions. And so when N is equal to zero, we have the empty string, okay? And the empty string does not contain consecutive numbers. So that means a not the empty string, uh, is one string which does not contain any of these pairs. Now, if it is equal to one, we're going to get three choices, right? Convene a zero, or it could be a one, or it could be a two. But all three of these do not contain the pair of consecutive numbers. So when the length is one, then there are three strings that do not contain these pears. Okay, so we move on, then to part see what we're finding Turn every strings of length six will use the recurrence relation. So we have found a not equal one. And a one is equal to three from part B. Okay, then a two is gonna be equal to two times a one. All right. Says just going to be two times three, which is six and a three is going to be equal to two times a to which for us is two times six, right? Two times six is 12 a four. It's gonna be two times a three sets me two times 12. 24 a five is two times a four busts Me two times 24 is 48. And lastly, a six, which is what we're looking for is two times a five and two times a five is two times 48 is equal to 96. So 96 possibles dreams, eyes the

All right. So here we have, um, and being the number of Terry strings like on that contained pairs consecutive numbers either repair zero's a pair of one's or a pair of twos. And much like many of these videos, we're gonna break it down into cases s so I'm just gonna actually do the 1st 3 cases so together. So it's gonna be case one to end three we're gonna consider Here is let's say the string start with zero, and the next value is not a zero. So either a one or a two. Okay, We have, of course, then and minus one in length for the rest of this string. Now, the number of strings you could put here that contain our consecutive pairs is going to be 80 and minus one. However, we're not considering the ones where the first numbers at zero, right, And so it's actually going to be 1/3 of them. So 1/3 of these numbers will start with a 0 1/3 will start with a one and one thing. We'll start with a two. So there are actually 2/3 ADM in its one ways in which we can get this combination in case too. And three will be the same for whether we have a one followed by a not one or a two as our first number followed by not the number two and we'll get thes. Same answer here. Okay, So for all three of these cases, we get 2/3 avian minus one, which means for this bit we can consider 2/3 a to the N minus one times three. Is this gonna be too? Is about minus one. Now, for the next three instances cases four through six. I'm also gonna glom together. Okay? And here we're considering where it starts with either a 00 A 11 or a 22 writes this. Well, then exacerbate exhaust every possible starting element for this string. Either as a zero and then not zero. Or is there a zero T? There's a one followed by not one or it starts with a one and that one. And it either has a two. Followed by not a two, or followed by a second to Randers. No other possible string than in these six cases. So for each of these, we are sort of element has already didn't met. So the pairs already in there. So we're just looking at the number of ways uh, we could have and minus two as a length for a true Neri string. And we find that by taking our three elements the 01 or two and raising it to the N minus two length. Right? But of course, we're doing this three times for the case of 00 for the case of 11 and the case of two to So, if we multiply that by three tons of being three to the N minus one, we're gonna add this three the n minus one, together with the two times A M minus one to get our our actual solution here. So we'll have a seven. It's gonna be equal to the sum of all of our cases two times, days of in minutes, one plus three to the n minus one. And this is our solution to player, eh? And so we see that we need here. Is it? Then goes back just one step. Right? So, to get our initial conditions for part B, we just need the 1st 2 cases where n is equal to zero and as equal to one. Okay, so if n is equal to zero, we have an empty string are right. There's nothing in there. And so therefore zero must equal zero cannot contain a pair. All right, then, for N go to one. That means that our strings you did just a zero. Just wait one more, just a two. And in any of these instances, we cannot have a pair, right? So everyone is equal to zero. So, of course, this mommy is going to ethical for n greater than or equal to two. Okay, so we moving right along then, too part. See now, Part C wants us to derive a six. Okay, so we have our initial conditions. That is, euros equal to a one is equal to zero. So go ahead and put in a two. And we'll find from our formula that for eight to this and be two times a one plus three times are three to power of and minus one, which is gonna be one. Okay. And then two times a 10 plus three part of one three. So the total numbers three. And you know, if we have terry strings of length to then we know that there could be 00 11 or 22 would all Phil this requirement right there. So there's three. So that matches up. So it's a good sign for what we've derived here. So it's continued until we hit a six. Okay, so a three, then it's gonna be equal to two times eight to you, plus three to the power of too. Right? So it's gonna be two times three plus nine. So six plus nine is 15. Cancel a four. It's gonna be two times a three plus three times form to the power of former. This one is equal to 30 plus 27 equal to 57 a five. We get to a four plus three to the power of five minus one. It's gonna be equal to 114 because 81 which is 195 and finally the last step here for a six is gonna be equal to two times a five. Our previous step plus three to the power of six minus one case like is US 390 plus 243 which is equal to 633 possible turn. Aires


Similar Solved Questions

5 answers
What is the pressure (in atm) of 0.0255 moles of gas if it has a volume of 105.2 mL at a temperature of 45 "C? Hint: R = 0.08206 (Lratm)/(mol-K)
What is the pressure (in atm) of 0.0255 moles of gas if it has a volume of 105.2 mL at a temperature of 45 "C? Hint: R = 0.08206 (Lratm)/(mol-K)...
5 answers
2, y =sin x > cos % 0 <<4#/* abouty = -1by eci-J = 0, > ~cos'g, ~m/2 <* < #/2 (a) About the x-axis (6) About y
2, y =sin x > cos % 0 <<4#/* abouty = -1 by eci- J = 0, > ~cos'g, ~m/2 <* < #/2 (a) About the x-axis (6) About y...
5 answers
I Utta ! 1 11331 Acl uliug > uneIiin oirl umd tstccn #WuI
i Utta ! 1 1 1 331 Acl uliug > uneIiin oirl umd tstccn #WuI...
5 answers
Y1 Polnts]DETAILSPREVIOUS ANSWERSFind M,' and (x, Y) for the laminas o unlform density bounded by the graphs of the equations Y = Vx,y = 0,* = 1616p48(y) =Nead Help?peoa Kceden[-/1 Polnts]DETAILSFlnd MandY) for the lamlnas of uniform density bounded by the graphs of thc equatlons
Y1 Polnts] DETAILS PREVIOUS ANSWERS Find M,' and (x, Y) for the laminas o unlform density bounded by the graphs of the equations Y = Vx,y = 0,* = 16 16p 48 (y) = Nead Help? peoa K ceden [-/1 Polnts] DETAILS Flnd M and Y) for the lamlnas of uniform density bounded by the graphs of thc equatlons...
5 answers
Magnetic force of 230 N acts Onl a positively charged object when it moves north with a speed of 120 m_ in a field of strength 0.73 T directed 40 north of east. Calculate its charge. point) 6.236 B. 1.444€ C. 3.427 €C D. 4.907 C E. 2.519 €
magnetic force of 230 N acts Onl a positively charged object when it moves north with a speed of 120 m_ in a field of strength 0.73 T directed 40 north of east. Calculate its charge. point) 6.236 B. 1.444€ C. 3.427 €C D. 4.907 C E. 2.519 €...
5 answers
Nl? . 3" (F1)" (2n + 1)1Apply the ratio test toPart 1: Evaluate the LimitEvaluateOntl limPart 2: Conclusionn2 The series '(F1)" (2n + 1)!
nl? . 3" (F1)" (2n + 1)1 Apply the ratio test to Part 1: Evaluate the Limit Evaluate Ontl lim Part 2: Conclusion n2 The series '(F1)" (2n + 1)!...
5 answers
Write the complete electron configurations for the following elements. Also write the number of unpaired electrons and underline the valence electrons lithiumoxygencalciumtilanlumrubidiumphosphorouspolassium
Write the complete electron configurations for the following elements. Also write the number of unpaired electrons and underline the valence electrons lithium oxygen calcium tilanlum rubidium phosphorous polassium...
1 answers
Perform the indicated operation. $$-\frac{5}{4}\left(\frac{8}{15}\right)$$
Perform the indicated operation. $$-\frac{5}{4}\left(\frac{8}{15}\right)$$...
5 answers
Algebraically (not graphically) solve the following equation To receive full credit, you must showyour work:4.8 = loga.2 (62 + 2)
Algebraically (not graphically) solve the following equation To receive full credit, you must showyour work: 4.8 = loga.2 (62 + 2)...
4 answers
3_ The output of a radio signal detection system is a normal random variable N(p,1) with unknown mean /. Consider the binary simple hypotheses Ho pL = 0 VS Hi p = 0.34_A sample mean of 0.5 was obtained from n = 16 independent measurements_ At significance level 2.5%, find the rejection region of the Neyman- Pearson test and determine the outcome.Find the pvalue of the above test and determine the outcome_Find the probability of the Type II error of the test in part
3_ The output of a radio signal detection system is a normal random variable N(p,1) with unknown mean /. Consider the binary simple hypotheses Ho pL = 0 VS Hi p = 0.34_ A sample mean of 0.5 was obtained from n = 16 independent measurements_ At significance level 2.5%, find the rejection region of th...
5 answers
Whaut is ie: Ilt;sjor praxljci (f il:' fllaowviru; resi tichi?1) Mg2) L 3) HOHO_Ho
whaut is ie: Ilt;sjor praxljci (f il:' fllaowviru; resi tichi? 1) Mg 2) L 3) HO HO_ Ho...
5 answers
Ues tionthc fllowing $ in Graph 3-spaccX=}Y= -12= -2x+yl-4 220 9+22 =4 X=0 (y-2)*+224,X2o Y= 3 / 23-1 xl+yl t22= 25 2= 3 2- JT-xyz
Ues tion thc fllowing $ in Graph 3-spacc X=} Y= -1 2= -2 x+yl-4 220 9+22 =4 X=0 (y-2)*+224,X2o Y= 3 / 23-1 xl+yl t22= 25 2= 3 2- JT-xyz...
5 answers
Uh el mel lim UKOH I
Uh el mel lim UKOH I...
5 answers
Find the current through the 9.0 0 resistor.6.099.02.0912v0.71 A21A13A0.86
Find the current through the 9.0 0 resistor. 6.09 9.0 2.09 12v 0.71 A 21A 13A 0.86...

-- 0.022361--