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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
