Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 was marked as an exact duplicate of an existing 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
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 for some formulas to compute them and more information.

share|cite|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.