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


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.

  • $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen Sep 9 '12 at 11:56
  • $\begingroup$ @Marc, yes, absolutely. $\endgroup$ – Gerry Myerson Sep 9 '12 at 12:28
  • $\begingroup$ @GerryMyerson Thank you sir! But I have a little question. When there are an number of arrangements with n boxes, how can there be an-1 number of arrangements for n-1 boxes?? I think, with n-1 boxes there would be an/2 number arrangements. Am I missing something?? (Sorry I don't know how to add subscripts.) $\endgroup$ – Login Test Sep 10 '12 at 16:00
  • $\begingroup$ $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/… $\endgroup$ – Gerry Myerson Sep 10 '12 at 23:08
  • $\begingroup$ @GerryMyerson Oh... Now I got it. Thank you sir. And thanks for the meta link also. :) $\endgroup$ – Login Test Sep 11 '12 at 9:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.