What is a recurrence relation for the number of sequences

Joyce Smith

Joyce Smith

Answered question

2022-01-06

What is 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

Piosellisf

Piosellisf

Beginner2022-01-07Added 40 answers

So,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 n1 stones must not have 2 adjacent purples.
Thus, 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 N2 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. Hence, 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?