The number of partitions of $n$ in which all parts are $1$ or $2$ is $$ \Bigl\lfloor \frac{n}{2} + 1 \Bigr\rfloor $$

Similarly how can I formulate the number of compositions formed using $1$ or $2$?

I could come up with a following series: If $n = 7$, then the number of compositions using $1$ and $2$ is $$ \binom{7}{0} + \binom{6}{1} + \binom{5}{2} + \binom{4}{3} = 21. $$

How can I form a formula to calculate the sum of this series?

Definitions: Partition, Composition


1 Answer 1


Let $F(n)$ be the number of compositions of $n$ by $1$ and $2$. A composition of $n$ can either end in $1$ or $2$. There are $F(n-1)$ that end in $1$ and $F(n-2)$ that end in $2$, so we have $F(n)=F(n-1)+F(n-2)$. Does that look familiar?

  • 1
    $\begingroup$ fibonacci series right ? And the fastest way to calculate the sum would be fibonacci exponentiation.Please correct me if I am wrong. $\endgroup$
    – g4ur4v
    Feb 2, 2013 at 21:06
  • $\begingroup$ @g4ur4v: Exactly right. You need to think a bit about how this $n$ matches up with the indices of the Fibonacci series. $\endgroup$ Feb 2, 2013 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .