1
$\begingroup$

An apartment building is being divided up and converted into apartments. A large apartment takes up two stories of the building and a small apartment takes up one story of the building. Now I have given the number of stories in the building, how do I calculate the different apartment combinations?

Do I simply use the combination formula?

$\endgroup$
  • $\begingroup$ I would proceed recursively. Let $T_n$ be the answer if the building has $n$ stories. Compute the first few, then sort out how to compute $T_n$ given $T_i$ for $i<n$. $\endgroup$ – lulu May 24 at 17:17
3
$\begingroup$

Let $a_n$ be the number of ways to do this with $n$ stories. For $n$ stories, if the highest apartment has size $1$, then there are $a_{n-1}$ ways to do everything below, and if it has size $2$ there are $a_{n-2}$ ways. So we obtain $a_n = a_{n-1} + a_{n-2}$. Noting that $a_1=1, a_2=2,$ we see that $a_n$ is in fact the $(n+1)$th Fibonacci number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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