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.

The number of partitions of n in which all parts are 1 or 2 is

enter image description here

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 are 21 and are given by series

enter image description here

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

Partition , Composition

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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?

share|improve this answer
    
fibonacci series right ? And the fastest way to calculate the sum would be fibonacci exponentiation.Please correct me if I am wrong. –  g4ur4v Feb 2 '13 at 21:06
    
@g4ur4v: Exactly right. You need to think a bit about how this $n$ matches up with the indices of the Fibonacci series. –  Ross Millikan Feb 2 '13 at 21:42

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.