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.

given x spaces(you can fit 1 ball in 1 space) and unlimited number of identical red and white balls, find the total number of combinations in which no two red balls are adjacent to each other.

i tried this theory like lets says i have 5 spaces then i fill in the white balls like this

_W_W_ and W_W_W

then in the rest of the spaces i fill in either red or white balls but unfortunately values like RWWRW get left out, so my that theory is wrong. does any one have any idea how to solve this.

i know the number of values your are suppose to get if it helps.

for 3 spaces-->5

for 4 spaces-->8

for 5 spaces-->13

for 6 spaces-->21

share|improve this question

1 Answer 1

up vote 10 down vote accepted

Congratulations on the experimentation! That is always a good beginning. The question is an old standard, indeed, because of the connection with Fibonacci numbers, a golden oldie. Call an arrangement of balls good if there are never two red balls in a row.

Let $f(n)$ be the number of good arrangements of $n$ balls. How many good arrangements of $n$ balls end in a white? Clearly there is exactly one such good arrangement for every good arrangement of $n-1$ balls. For from every good arrangement of $n-1$ balls, we can get a good arrangement of $n$ balls ending in white by appending a white. And from every good arrangement of $n$ balls ending in white, we can get a good arrangement of $n-1$ balls by removing the last white. So the number of good arrangements of $n$ balls that end in a white is $f(n-1)$.

How many good arrangements of $n$ balls end in a red? The previous ball must be white. And by the preceding paragraph, there are just as many good arrangements of $n-1$ balls that end in white as there are good arrangements of $n-2$ balls (of course, we need $n-2\ge 0$). Since every good arrangement of $n$ balls either ends in a white or a red, we conclude that $f$ satisfies the recurrence $$f(n)=f(n-1)+f(n-2).$$ The initial conditions are $f(0)=1$ and $f(1)=2$. We get essentially the Fibonacci sequence, with slightly modified indexing. If (as in the Wikipedia article linked to) we use $F_0=0$, $F_1=1$ for the Fibonacci sequence, then $f(n)=F_{n+2}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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