How to obtain the number of sequences given a number?

[ChPravin]

Hello All,

I had this question asked to me in one of the interviews and I wasn't able to figure it out.I need to write a method CountUniqueSequences(int sum) which returns the number of unique sequences that consist of only 1's and 2's and have an element summation equal to a given N.
For example, below are all unique sequences consisting of 1's and 2's with element summation of N=4:

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

So, CountUniqueSequences(4) should return 5.

I figured out that the frequency of occurrences of 1 in case of even nos. consist of only even nos. and in case of odd nos. consist of only odd nos.Correspondingly, the frequency of occurrence of 2 gets incremented each time the frequency of occurrence of 1 decreases.

For instance,to obtain 4:
1 can be used 2 times or 4 times and 2 can be used 1 time or 0 time.

To obtain 5: 1 can be used 1,3 or 5 times and correspondingly 2 can be used 2,1 or 0 times.

Although,it's not required in the problem I know that I can permute the number to obtain all possibilities but I do not know how to form a number.
Any suggestions would be greatly appreciated.

[mrnutty]

First correct me in this if I'm wrong.

For sum = 0 , return 0;
For sum = 1 , return 1;
For sum = 2 , return 2;
For sum = 3 , return 3;
For sum = 4 , return 5;
For sum = 5 , return 8;
For sum = 6 , return 13;

It looks like its defined by :

F(n) =
{ 0 if n = 0 }
{ 1 if n = 1 }
{ 2 if n = 2 }
{ F(n-1) + F(n-2) for n > 2 }
{ else not defined }

Thats just a guess.

[Rashakil Fol]

This is clearly (n choose 0) + (n-1 choose 1) + (n-2 choose 2) + ... which is well known to be the fibonacci function.

[ChPravin]

Thanks for the replies! I should've figured that out :(