Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
i guess we are saying the same thing. On Wed, Jun 9, 2010 at 1:29 AM, Senthilnathan Maadasamy < senthilnathan.maadas...@gmail.com> wrote: > I found a nice explanation (from some other site) on how to get this > formula T(n) = fib(n+2). > > Consider the set of all binary numbers of length n that end with 0. The > first n-1 positions can be anything (0 or 1). So if we take the set of all > binary numbers of length n-1 and append 0 to each of its element we get this > set. Therefore size of this set is T(n-1). > > Consider the set of all binary numbers of length n that end with 1. Now, > the (n-1)th position has to be 0 (because of the constraint). But there is > no constraint on the first n-2 positions. So if we take the set of all > binary numbers of length n-2 and append 01 to each of its element we get > this set. Therefore size of this set is T(n-2). > > Therefore T(n) = T(n-1) + T(n-2). > > Since T(1) = 2 and T(2) = 3 we get T(n) = fib(n+2). > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
I found a nice explanation (from some other site) on how to get this formula T(n) = fib(n+2). Consider the set of all binary numbers of length n that end with 0. The first n-1 positions can be anything (0 or 1). So if we take the set of all binary numbers of length n-1 and append 0 to each of its element we get this set. Therefore size of this set is T(n-1). Consider the set of all binary numbers of length n that end with 1. Now, the (n-1)th position has to be 0 (because of the constraint). But there is no constraint on the first n-2 positions. So if we take the set of all binary numbers of length n-2 and append 01 to each of its element we get this set. Therefore size of this set is T(n-2). Therefore T(n) = T(n-1) + T(n-2). Since T(1) = 2 and T(2) = 3 we get T(n) = fib(n+2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
recursion. for length n if the count is T(n) then T(n) = 1st digit 0 + 1st digit 1 = T(n-1) + 1st digit 1 && 2nd digit 0 = T(n-1) + T(n-2) QED. On Tue, Jun 8, 2010 at 9:03 PM, Raj N wrote: > I just checked out with so many possibilities and it is indeed matching. I > may not be correct though. > > > On Tue, Jun 8, 2010 at 7:50 PM, divya jain wrote: > >> how do u come to this formula T(n)=fib(n+2).. plz explain >> >> >> On 7 June 2010 21:19, saurabh gupta wrote: >> >>> it might be referring to no of sequences (say T(n) ) with no consecutive >>> 1's >>> for n = 3, ans would be 5 viz. >>> 000, 001, 010, 100, 101 >>> >>> T(n) = fib(n+2) >>> where fib = Fibonacci series >>> which is interesting. >>> >>> >>> On Sat, Jun 5, 2010 at 11:40 AM, Raj N wrote: >>> @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: > @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 > is required answer. > > > On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: > >> Hi, >> I came across this question to find the number of sequences of n >> binary digits that don't contain 2 1's in a row. I wanted to know what >> exactly this means. Is it like if n=3 then compute all binary numbers >> having 3 digits which don't have consecutive 1's 110, 011, 111 ?? >> If not help me understanding it. >> Thanks!! >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > yezhu malai vaasa venkataramana Govinda Govinda > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> >>> -- >>> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. >>> Says he feels all alone in a threatening world where what lies ahead is >>> vague and uncertain. Doctor says "Treatment is simple. Great clown >>> Pagliacci is in town tonight. Go and see him. That should pick you up." >>> Man >>> bursts into tears. Says "But, doctor...I am Pagliacci." >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
I just checked out with so many possibilities and it is indeed matching. I may not be correct though. On Tue, Jun 8, 2010 at 7:50 PM, divya jain wrote: > how do u come to this formula T(n)=fib(n+2).. plz explain > > > On 7 June 2010 21:19, saurabh gupta wrote: > >> it might be referring to no of sequences (say T(n) ) with no consecutive >> 1's >> for n = 3, ans would be 5 viz. >> 000, 001, 010, 100, 101 >> >> T(n) = fib(n+2) >> where fib = Fibonacci series >> which is interesting. >> >> >> On Sat, Jun 5, 2010 at 11:40 AM, Raj N wrote: >> >>> @sharad: What about 101 even it doesn't have two 1's in a row >>> >>> >>> On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: >>> @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: > Hi, > I came across this question to find the number of sequences of n > binary digits that don't contain 2 1's in a row. I wanted to know what > exactly this means. Is it like if n=3 then compute all binary numbers > having 3 digits which don't have consecutive 1's 110, 011, 111 ?? > If not help me understanding it. > Thanks!! > > -- > You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. >> Says he feels all alone in a threatening world where what lies ahead is >> vague and uncertain. Doctor says "Treatment is simple. Great clown >> Pagliacci is in town tonight. Go and see him. That should pick you up." >> Man >> bursts into tears. Says "But, doctor...I am Pagliacci." >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
@saurabh: Hey u're right this is interesting. I checked for n=5 its giving 13 i.e fib(7) On Mon, Jun 7, 2010 at 9:19 PM, saurabh gupta wrote: > it might be referring to no of sequences (say T(n) ) with no consecutive > 1's > for n = 3, ans would be 5 viz. > 000, 001, 010, 100, 101 > > T(n) = fib(n+2) > where fib = Fibonacci series > which is interesting. > > On Sat, Jun 5, 2010 at 11:40 AM, Raj N wrote: > >> @sharad: What about 101 even it doesn't have two 1's in a row >> >> >> On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: >> >>> @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 >>> is required answer. >>> >>> >>> On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: >>> Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> -- >>> yezhu malai vaasa venkataramana Govinda Govinda >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. > Says he feels all alone in a threatening world where what lies ahead is > vague and uncertain. Doctor says "Treatment is simple. Great clown > Pagliacci is in town tonight. Go and see him. That should pick you up." Man > bursts into tears. Says "But, doctor...I am Pagliacci." > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta wrote: > it might be referring to no of sequences (say T(n) ) with no consecutive > 1's > for n = 3, ans would be 5 viz. > 000, 001, 010, 100, 101 > > T(n) = fib(n+2) > where fib = Fibonacci series > which is interesting. > > > On Sat, Jun 5, 2010 at 11:40 AM, Raj N wrote: > >> @sharad: What about 101 even it doesn't have two 1's in a row >> >> >> On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: >> >>> @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 >>> is required answer. >>> >>> >>> On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: >>> Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. Thanks!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> -- >>> yezhu malai vaasa venkataramana Govinda Govinda >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. > Says he feels all alone in a threatening world where what lies ahead is > vague and uncertain. Doctor says "Treatment is simple. Great clown > Pagliacci is in town tonight. Go and see him. That should pick you up." Man > bursts into tears. Says "But, doctor...I am Pagliacci." > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N wrote: > @sharad: What about 101 even it doesn't have two 1's in a row > > > On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: > >> @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is >> required answer. >> >> >> On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: >> >>> Hi, >>> I came across this question to find the number of sequences of n >>> binary digits that don't contain 2 1's in a row. I wanted to know what >>> exactly this means. Is it like if n=3 then compute all binary numbers >>> having 3 digits which don't have consecutive 1's 110, 011, 111 ?? >>> If not help me understanding it. >>> Thanks!! >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> yezhu malai vaasa venkataramana Govinda Govinda >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
@sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar wrote: > @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is > required answer. > > > On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: > >> Hi, >> I came across this question to find the number of sequences of n >> binary digits that don't contain 2 1's in a row. I wanted to know what >> exactly this means. Is it like if n=3 then compute all binary numbers >> having 3 digits which don't have consecutive 1's 110, 011, 111 ?? >> If not help me understanding it. >> Thanks!! >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > yezhu malai vaasa venkataramana Govinda Govinda > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Number of sequences of n binary digits that don't contain two 1's in a row
@rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N wrote: > Hi, > I came across this question to find the number of sequences of n > binary digits that don't contain 2 1's in a row. I wanted to know what > exactly this means. Is it like if n=3 then compute all binary numbers > having 3 digits which don't have consecutive 1's 110, 011, 111 ?? > If not help me understanding it. > Thanks!! > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
