# Thread: Combinations of two-element set

1. ## Combinations of two-element set

Hey. I have to write number of combinations in two-piece set for sequence of lenght 'n'. In this way that one of this two elements will never occur next to another.

Examples:
Set = 0 and 1
Sequence of length = 2
Element which doesn't have to occur next to another = 1
Possible combinations:00 01 10
Result: 3

Set=0 and 1
Sequence of length = 3
Element which doesn't have to occur next to another = 1
Possible combinations:000 001 010 100 101
Result: 5

Set=0 and 1
Sequence of length = 4
Element which doesn't have to occur next to another = 1
Possible combinations:0000 0001 0010 0100 1000 1010 0101 1001
Result: 8

Am I able to appoint with formula or anyone knows the way how to make it?
For some time I thought that formula n+2^(n-2), where n is a length of sequence is correct but everything indicates that for large lenghts of sequences this formula isn't correct.

2. ## Re: Combinations of two-element set

if the number of allowable sequences of length 5 is 13, it would appear that:

$\displaystyle a_{n+2} = a_{n+1} + a_n$

perhaps you should see if you can prove this formula.

3. ## Re: Combinations of two-element set

Originally Posted by rout00
Hey. I have to write number of combinations in two-piece set for sequence of lenght 'n'. In this way that one of this two elements will never occur next to another.
Examples:
Set = 0 and 1
Sequence of length = 2
Element which doesn't have to occur next to another = 1
Possible combinations:00 01 10
Result: 3
The solution to this requires a classical technique.
Let $\displaystyle A_{n}$ be the set of admissible strings of length n
Then let $\displaystyle a_{n}=\|A_n\|$ be the number of elements in $\displaystyle A_{n}$.

If we take any string from $\displaystyle A_{n-1}$ and add a 0 to its end. Now we have a string in $\displaystyle A_{n}$.

This time take any string from $\displaystyle A_{n-2}$ and add a 01 to its end. Now we have another string in $\displaystyle A_{n}$.

Look at reply #2. You will see how that recurrence relation fits in.