@another approach..
Lets say,
F(n) -> basically represents of ways n 'H' and 'T''s can be placed
such that there are no consecutive 'H''s.
1) Now, say the sequence of 'H' and 'T' ends with 'T'. Now, 'T' is at
nth position, hence it doesn't matter whether (n-1) th position has
'H' or 'T'.
But then the first (n-1) positions shouldn't have consecutive 'H''s.
Therefore, if nth position has 'T' then the no. of ways of getting to
it is same as F(n-1)..
2) Now, say the sequence ends with 'H'. As we know that we can't have
consecutive heads therefore, the (n-1) position needs to have 'T' for
it to be valid sequence.
Therefore if the sequence ends with 'H' that implies that it ends
with 'TH'.
Now the no. of ways, wherein the sequence ends with 'TH' = Now the
no. of ways, wherein the sequence ends with 'T'
= F(n-2) // from point 1..
Hence, total no. of ways we can generate a n-length sequence such that
it doesn't have consecutive 'H's:
F(n) = F(n-1) { when ends with 'T'} + F(n-2) { when ends with 'H'}
F(0) = 1,
F(1) = 2,
On Jan 23, 3:19 pm, Piyush Kapoor <pkjee2...@gmail.com> wrote:
> Use Combinatorics.
> The Question is equivalent to ---> To find the number of ways to place 'H'
> such that no two are adjacent to each other
> Now we have following possibilities ::
> 1)Using exactly 0 'H' 's :: ==> 1
> 2)Using exactly 1 'H's ::==> NC1
> 3)Using exactly 2 'H's ::==>
> For this case , the arrangement would be something like this::
> (tt...tt) H (tt..tt) H (tt.....tt)
> --X---- ---Y-- ---Z-----
> Let the number of 'T' s on the left side be X,middle be Y,and right be Z,
> then X+Y+Z=N-2 ,also Y>=1 for H to not to be adjacent
> so X+(Y-1) +Z=N-3 the number of solutions ==> (N-3)+(3-1) C (3-1) ==>
> (N-1)C2
> 4)Using exactly 3 'H's::==> (N-2)C3
> and so on..
> Answer = => 1+NC1 + (N-1)C2 + (N-2)C3 + ..... (till N-r >=r)
> which is same as fibonacci series.
> So the answer was the fibonacci number divided by (2^n)
> --
> *Regards,*
> *Piyush Kapoor,*
> *2nd year,CSE
> IT-BHU*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
