| (10 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| − | I need some help writing the recurrence relation | + | I need some help writing the recurrence relation for this problem, or problem 30, since they are very similar. I've worked out some solutions and this is what I've got:<br><br> |
a1 = 0<br> | a1 = 0<br> | ||
a2 = 0<br> | a2 = 0<br> | ||
a3 = 1<br> | a3 = 1<br> | ||
| − | a4 = 1 + 1<br> | + | a4 = 1 + 1 = 2<br> |
| − | a5 = 2 + 1 + 2<br> | + | a5 = 2 + 1 + 2 = 5<br> |
| − | a6 = 4 + 2 + 2 + 4<br> | + | a6 = 4 + 2 + 2 + 4 = 12<br> |
| − | a7 = 8 + 4 + 4 + 4 + 8<br><br> | + | a7 = 8 + 4 + 4 + 4 + 8 = 28<br><br> |
| − | So, from here I can't find the sequence that gives me those | + | So, from here I can't find the sequence that gives me those sums. I believe what's above is right, but if it isn't or there is a better way to look at it, let me know. Thanks for the help. --[[User:Aoser|Aoser]] 17:09, 15 October 2008 (UTC) |
| + | ---- | ||
| + | I'm not sure if I'm correct, but I arrived at different values of strings with consecutive 0's of length (n). granted I don't read the problem as having "ONLY" 3 consecutive 0's so strings with more then 3 consecutive 0's are also counted (but only once){'''''000'''''0 and 0'''''000''''' are the same and only counted once}.<br> | ||
| + | a1 = 0<br> | ||
| + | a2 = 0<br> | ||
| + | a3 = 1 {000}<br> | ||
| + | a4 = 1 + 2 = 3 {0001, 0000, 1000}<br> | ||
| + | a5 = 3 + 4 = 7 {00011, 00010, 00001, 00000, 10001, 10000, 11000 }<br> | ||
| + | a6 = 7 + 8 = 15 {000111, 000110, 000101, 000100, 000011, 000010, 000001, 000000, 100011, 100010, 100001, 100000, 110001, 110000, 111000 }<br> | ||
| + | this is simplified to a(n) = 2*a(n-1)+1, but I'm unsure if this is correct, or why. --[[User:Mnoah|mnoah]] 20:23, 15 October 2008 (UTC) | ||
| + | ---- | ||
| + | In your solution, for example, a5 is not 7, but 8. You don't count "01000". And so on. The initial conditions were found correctly: a1=0, a2=0, a3=1. To construct the recurrence relation, here is a hint: an = # of bit strings starting from "1" + # of bit strings starting from "01" + # of bit strings starting from "001" + # of bit strings starting from "000". Hope it helps. --[[User:Asuleime|Asuleime]] 20:53, 15 October 2008 (UTC)<br> | ||
| + | ---- | ||
| + | I considered strings of lenght n to which you can add a 0 or a 1 to make it of lenght n+1; then I considered the strings of lenght n which do not contain 3 consecutive 0's, fixed two 0's at the end of the strings, and added one 0 to make it of lenght n+1. --rtabchou | ||
| + | |||
| + | ---- | ||
| + | |||
| + | I found Asuleime's example to be helpful. Mainly you need to consider the number of bit strings which satisfy the condition at each recursion until you reach a point where all the bit strings of that type satisfies to condition. | ||
| + | --[[User:ysuo|ysuo]] 15:23, 16 October 2008 (UTC) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | I did about what rtabchou did. There is an example in the book that shows how to find all the strings that DON'T have a string of 3 zeroes in it. Find that then find the converse by subtracting from the total number of ways possible...MUCH easier, although it may not seem that way on the outside. | ||
Latest revision as of 10:43, 18 October 2008
I need some help writing the recurrence relation for this problem, or problem 30, since they are very similar. I've worked out some solutions and this is what I've got:
a1 = 0
a2 = 0
a3 = 1
a4 = 1 + 1 = 2
a5 = 2 + 1 + 2 = 5
a6 = 4 + 2 + 2 + 4 = 12
a7 = 8 + 4 + 4 + 4 + 8 = 28
So, from here I can't find the sequence that gives me those sums. I believe what's above is right, but if it isn't or there is a better way to look at it, let me know. Thanks for the help. --Aoser 17:09, 15 October 2008 (UTC)
I'm not sure if I'm correct, but I arrived at different values of strings with consecutive 0's of length (n). granted I don't read the problem as having "ONLY" 3 consecutive 0's so strings with more then 3 consecutive 0's are also counted (but only once){0000 and 0000 are the same and only counted once}.
a1 = 0
a2 = 0
a3 = 1 {000}
a4 = 1 + 2 = 3 {0001, 0000, 1000}
a5 = 3 + 4 = 7 {00011, 00010, 00001, 00000, 10001, 10000, 11000 }
a6 = 7 + 8 = 15 {000111, 000110, 000101, 000100, 000011, 000010, 000001, 000000, 100011, 100010, 100001, 100000, 110001, 110000, 111000 }
this is simplified to a(n) = 2*a(n-1)+1, but I'm unsure if this is correct, or why. --mnoah 20:23, 15 October 2008 (UTC)
In your solution, for example, a5 is not 7, but 8. You don't count "01000". And so on. The initial conditions were found correctly: a1=0, a2=0, a3=1. To construct the recurrence relation, here is a hint: an = # of bit strings starting from "1" + # of bit strings starting from "01" + # of bit strings starting from "001" + # of bit strings starting from "000". Hope it helps. --Asuleime 20:53, 15 October 2008 (UTC)
I considered strings of lenght n to which you can add a 0 or a 1 to make it of lenght n+1; then I considered the strings of lenght n which do not contain 3 consecutive 0's, fixed two 0's at the end of the strings, and added one 0 to make it of lenght n+1. --rtabchou
I found Asuleime's example to be helpful. Mainly you need to consider the number of bit strings which satisfy the condition at each recursion until you reach a point where all the bit strings of that type satisfies to condition. --ysuo 15:23, 16 October 2008 (UTC)
I did about what rtabchou did. There is an example in the book that shows how to find all the strings that DON'T have a string of 3 zeroes in it. Find that then find the converse by subtracting from the total number of ways possible...MUCH easier, although it may not seem that way on the outside.
