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

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
    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$a_m=1$. – 2012-09-09
  • 0
    @Marc, yes, absolutely.2012-09-09
  • 0
    @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.)2012-09-10
  • 0
    $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 http://meta.math.stackexchange.com/questions/5020/tex-latex-mathjax-basic-tutorial-and-quick-reference2012-09-10
  • 0
    @GerryMyerson Oh... Now I got it. Thank you sir. And thanks for the meta link also. :)2012-09-11