A more theoretical answer to the question can be the following:
Let's try to construct a tree for all such possible sequences.
Level 0 => 0 or 1
Level 1 => 0 1 0
Level 2 => 0 1 0 0 1
Level 3 => 0 1 0 0 1 0 1 0
....
Simple observation will tell you that for every 0 in a position, the next
position can have either 0 or 1, but for a 1 in the position, the next bit *has
*to be a 0. -- (1)
Let us call the function N0(p) to be the number of 0s at level (position) p
in the sequence; N1(p) to be the number of 1s at level p. The total number
of nodes at level p is then N(p) = N0(p) + N1(p).
It is also clear from statement (1) that
N0(p) = N0(p-1) + N1(p-1) --- (2)
and
N1(p) = N0(p-1) -- (3)
i.e. the number of 0s in the next level equal to the number of 0s in the
previous level plus the number of 1s in the previous level,
whereas the number of 1s is equal to the number of 0s in the previous level.
Thus, combining (2) and (3), we have... N(p) = N0(p-1) + N1(p-1) + N0(p-1)
--- (4)
Now, N0(p-1) + N1(p-1) is really N(p-1) - i.e. the total number of possible
sequences of length p.
Also, N0(p-1) = N0(p-2) + N1(p-2) = N(p-2) from (2)
Therefore, (4) reduces to
N(p) = N(p-1) + N(p-2)
The above, you would recognize as the generative recursive form of the
sequence of fibonacci numbers.
thanks,
mayur
On Fri, Jun 11, 2010 at 2:05 PM, Debajyoti Sarma
<sarma.debajy...@gmail.com>wrote:
> clarification to all
>
> n=1
> 0,1 no of sequence =2
>
> n=2
> 00,01,10 no of sequence =3
>
> n=3
> 000,100,010,001,101 no of sequence =5
>
> n=4
> 0000,1000,0100,0010,0001,1010,0101,1001 no of sequence
> =8
>
> n=5
> 00000,10000,01000,00100,00010,00001,10100,10010,10001,01010,01001,00101,10101
> no of sequence =13
>
> so its coming in fibo no.
>
> no of sequence =fibo(n+2) if you exclude 0 from fibo no
>
> no of sequence =fibo(n+3) if you include 0 in fibo no
>
>
>
> On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma <
> sarma.debajy...@gmail.com> wrote:
>
>> @Rohit Saraf
>>
>> i understood the question.
>> Superb solution by u.
>>
>>
>> On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com
>> > wrote:
>>
>>> write an efficient algo to compute no. of sequences of n binary digits
>>> that do not contain 2 1's in a row. eg 1100001 is invalid whereas
>>> 1001001 is valid.
>>>
>>> HERE the number of sequences comes to be a fibonacci number , precisely
>>> fib(n+2).
>>> So this prob is equivalent to finding fibonacci numbers
>>>
>>> --------------------------------------------------
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>>
>>>
>>> On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh <singh.sund...@gmail.com
>>> > wrote:
>>>
>>>> @rohit: fibonacci sequence may be the answer to the prob, but I am
>>>> curious why? I haven't come across any such fib sequence property...
>>>>
>>>> On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf <
>>>> rohit.kumar.sa...@gmail.com> wrote:
>>>>
>>>>> @junta : are fibonacci sequence is the answer of the prob, it is not
>>>>> used :D
>>>>>
>>>>> --------------------------------------------------
>>>>> Rohit Saraf
>>>>> Second Year Undergraduate,
>>>>> Dept. of Computer Science and Engineering
>>>>> IIT Bombay
>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>>>>
>>>>>
>>>>> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf <
>>>>> rohit.kumar.sa...@gmail.com> wrote:
>>>>>
>>>>>> @debajyoti: read the prob before posting
>>>>>>
>>>>>> --------------------------------------------------
>>>>>> Rohit Saraf
>>>>>> Second Year Undergraduate,
>>>>>> Dept. of Computer Science and Engineering
>>>>>> IIT Bombay
>>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>>>>>
>>>>>>
>>>>>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>>>>>> sarma.debajy...@gmail.com> wrote:
>>>>>>
>>>>>>> First 20 fibo no as follows with binary form
>>>>>>> 0 = 0
>>>>>>> 1 = 1
>>>>>>> 1 = 1
>>>>>>> 2 = 10
>>>>>>> 3 = 11
>>>>>>> 5 = 101
>>>>>>> 8 = 1000
>>>>>>> 13 = 1101
>>>>>>> 21 = 10101
>>>>>>> 34 = 100010
>>>>>>> 55 = 110111
>>>>>>> 89 = 1011001
>>>>>>> 144 = 10010000
>>>>>>> 233 = 11101001
>>>>>>> 377 = 101111001
>>>>>>> 610 = 1001100010
>>>>>>> 987 = 1111011011
>>>>>>> 1597 = 11000111101
>>>>>>> 2584 = 101000011000
>>>>>>> 4181 = 1000001010101
>>>>>>>
>>>>>>> Now please explain how fibo no is coming under consideration.Both
>>>>>>> kind of no is mixed here.
>>>>>>>
>>>>>>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf <
>>>>>>> rohit.kumar.sa...@gmail.com> wrote:
>>>>>>>
>>>>>>>> Fib comes because she wants the number of such sequences
>>>>>>>>
>>>>>>>> --
>>>>>>>> --------------------------------------------------
>>>>>>>> Rohit Saraf
>>>>>>>> Second Year Undergraduate,
>>>>>>>> Dept. of Computer Science and Engineering
>>>>>>>> IIT Bombay
>>>>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>>>>>>>
>>>>>>>> --
>>>>>>>>
>>>>>>>> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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.
