Take the 2-minute tour ×
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 there are n houses and I want to calculate the number of ways of selecting any number of houses given a condition that I have to select atleast three consecutive houses. for eg.if the total number of houses is 4,so the no of ways to do the job will be 3. No of houses(n)=4 no of ways = {1,2,3},{2,3,4},{1,2,3,4}

(note:I am can only select in increasing order of the number,so {1,3,2},etc are invalid)

I was able to find that total no of ways to do the above job follows a series

Sum=1+2+5+12+28+...(n-2) terms

so when n=4,then no of ways = 1+2=3 .When n=5,then no of ways=1+2+5=8 and so on.

Now,i am looking for the formula in terms of n to calculate the sum of this series.

share|improve this question

marked as duplicate by Brian M. Scott, William, Rudy the Reindeer, J. M., Norbert Oct 3 '12 at 20:11

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.

Please help me with the formula.I am stuck as this is the part of a programming problem that I am trying to solve. –  g4ur4v Sep 8 '12 at 14:17

1 Answer 1

up vote 0 down vote accepted

Let $f(n)$ denote the number of subsets of $\{1, \ldots,n\}$ that avoid three consecutive numbers. Then what you are looking for is simply $2^n-f(n)$.

Clearly, $f(0)=1$, $f(1)=2$, $f(2)=4$. For $n\ge3$, such an avoiding set is either

  • in fact a subset of $\{1,\ldots,n-1\}$
  • of the form $A\cup \{n\}$ where $A\subseteq \{1,\ldots,n-2\}$
  • of the form $A\cup \{n-1, n\}$ where $A\subseteq \{1,\ldots,n-3\}$

We conclude $f(n) = f(n-1) + f(n-2)+f(n-3)$ for $n\ge3$. These are the tribonacci numbers, see http://oeis.org/A000073 for some formulas to compute them and more information.

share|improve this answer
The solution you have posted it correct.But I am not able to understand how you framed f(n).Could you please elaborate it furthur. –  g4ur4v Sep 11 '12 at 17:27

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