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
    Thank you all. I got my answer from there. It took a little to co-relate both problems. :)2012-09-10

1 Answers 1

2

Let $a_n$ be the number of arrangements with $n$ boxes. There are $a_{n-1}$ such arrangements with $n-1$ boxes, each of which gives rise to 2 arrangements with $n$. But there are also arrangements of $n-1$ boxes that don't have $m$ contiguous $A$ that become good arrangements when you fill that last box. Each of these is an unacceptable arrangement of $n-m$ boxes, followed by $m-1$ copies of $A$, so they are $2^{n-m}-a_{n-m}$ in number. Thus, $a_n=2a_{n-1}+2^{n-m}-a_{n-m}$ and there are standard techniques for handling such a linear recurrence.

  • 0
    @GerryMyerson Oh... Now I got it. Thank you sir. And thanks for the meta link also. :)2012-09-11