0
$\begingroup$

Possible Duplicate:
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Suppose we have large number of two types of objects $A$ and $B$. Now lets say we have $N$ boxes. So if we try to arrange these two objects ($A$'s and $B$'s) in these $N$ boxes, we can arrange in $2^N$ possible ways. I want to count the number of arrangements in which there are at least $m$ contiguous $A$'s.

My approach was:

Lets combine those $m$ contiguous boxes containing $A$'s into 1 box. Now we are left with $n-m+1$ box. These boxes can be arranged in $(n-m+1)*2^{(n-m)}$ possible ways. But later I realized that it contains lots of repetitions (arrangements which are not unique). How can I remove these repetitions?? Or am I following a wrong approach entirely??

  • 0
    I take it you are putting exactly one object in each box. Maybe you could edit that into your question.2012-09-08
  • 0
    This is essentially equivalent to this question: http://math.stackexchange.com/questions/59738/probability-for-the-length-of-the-longest-run-in-n-bernoulli-trials/59744 The exact solution is not trivial. For large $N$, there are asymptotical approximate solutions.2012-09-08
  • 0
    See also http://mathworld.wolfram.com/Fibonaccin-StepNumber.html2012-09-08
  • 0
    This problem is a generalisation (from $m=3$) of [this (newer) question](http://math.stackexchange.com/questions/192693) which was since closed as exact duplicate of the ill-titled question [Summation over large values of nCr](http://math.stackexchange.com/questions/191702)2012-09-09
  • 0
    Thank you all. I got my answer from there. It took a little to co-relate both problems. :)2012-09-10

1 Answers 1