# Number of arrangements of 2 objects which contains one of them at at least “m” contiguous places. [duplicate]

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??

• I take it you are putting exactly one object in each box. Maybe you could edit that into your question. – Gerry Myerson Sep 8 '12 at 6:16
• This is essentially equivalent to this question: math.stackexchange.com/questions/59738/… The exact solution is not trivial. For large $N$, there are asymptotical approximate solutions. – leonbloy Sep 8 '12 at 6:18
• – leonbloy Sep 8 '12 at 6:28
• This problem is a generalisation (from $m=3$) of this (newer) question which was since closed as exact duplicate of the ill-titled question Summation over large values of nCr – Marc van Leeuwen Sep 9 '12 at 11:37
• Thank you all. I got my answer from there. It took a little to co-relate both problems. :) – Login Test Sep 10 '12 at 15:54

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.
• Almost correct: the inacceptable arrangement should itself end with a $B$. So I think the recurrence is $a_n=2a_{n-1}+2^{n-(m+1)}-a_{n-(m+1)}$ for $n>m$, with initial values $a_i=0$ for $0\leq i<m$ and $a_m=1$. – Marc van Leeuwen Sep 9 '12 at 11:56
• $a_n$ is a way of saying $a(n)$; all the first sentence of my answer says is that the number of arrangements with $n$ boxes is a function of $n$, and I'm going to call that function $a$, and I could choose to write it as $a(n)$, but instead I choose to write it as $a_n$. Then the number of arrangements for $n-1$ boxes is $a(n-1)$, which I choose to write as $a_{n-1}$. Subscripts are easy: for $a_{n-1}$, do a_{n-1} but with a dollar sign at each end. See also meta.math.stackexchange.com/questions/5020/… – Gerry Myerson Sep 10 '12 at 23:08