Find a recurrence relation for the number of sequences of yellow and purple stones of length N, where each sequence has the property that no two adjacent stones are purple.

FizeauV

FizeauV

Answered question

2021-01-19

Find a recurrence relation for the number of sequences of yellow and purple stones of length N, where each sequence has the property that no two adjacent stones are purple.

Answer & Explanation

unett

unett

Skilled2021-01-20Added 119 answers

Consider the provided question,
We have to find a recurrence relation for the number of sequences of yellow and purple stones of length N.
Where, each sequence has the property that no two adjacent stones are purple.
Let aN be the number of such sequences of length N.
There are two cases.
1) The last stone is yellow.
In this case, the first n-1 stones must not have 2 adjacent purples.
So, there are aN1 such sequences.
2) The last stone is purple.
In this case, the last 2 stones must be yellow and purple.
So, the first N-2 stones must not have 2 adjacent purples.
thus, there are aN2 such sequences.
In total, there are aN1+aN2 sequences.
therefore, aN=aN1+aN2
here, a0=1,a1=2
Thus, the required recurrence relation is aN=aN1+aN2

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?