if the number of allowable sequences of length 5 is 13, it would appear that:
perhaps you should see if you can prove this formula.
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.
The solution to this requires a classical technique.
Let be the set of admissible strings of length n
Then let be the number of elements in .
If we take any string from and add a 0 to its end. Now we have a string in .
This time take any string from and add a 01 to its end. Now we have another string in .
Look at reply #2. You will see how that recurrence relation fits in.