Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question

marked as duplicate by Marc van Leeuwen, William, Norbert, Arkamis, rschwieb Oct 15 '12 at 18:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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:… The exact solution is not trivial. For large $N$, there are asymptotical approximate solutions. – leonbloy Sep 8 '12 at 6:18
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

1 Answer 1

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.

share|cite|improve this answer
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
@Marc, yes, absolutely. – Gerry Myerson Sep 9 '12 at 12:28
@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.) – Login Test Sep 10 '12 at 16:00
$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… – Gerry Myerson Sep 10 '12 at 23:08
@GerryMyerson Oh... Now I got it. Thank you sir. And thanks for the meta link also. :) – Login Test Sep 11 '12 at 9:52

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