# $a_n$ is the number of sequences with length $n$ over ${1,2,3,4,5,6}$

$a_n$ is the number of sequences with length $n$ over ${1,2,3,4,5,6}$

• It is allowed up to 2 odd numbers in a row.
• It is allowed up to 2 even numbers in a row.

Find $a_3$ and find the recursion formula.

Well, I'm familiar with easier recursion questions, and with this one I'm not kinda sure how to approach.

My thoughts:

For finding $a_3$ I need to find all the possible combinations that are legit with those 2 conditions above.

So if I get the first number as odd number, the second one must be even, third one must be odd again. and the same if I get the first number as even. which means:

For condition 1: I have 3 different options for first number, then I have 3 options for second number, and then 2 options with third number.

For condition 2: It is the same.

But I don't really know if I am right and how to step into finding the recursion formula. Any ideas would be highly appreciated as it is really important for me to understand this subject.

Edit: An addition to my thoughts, I missed the part where two odd/even numbers can be in a-row. for example $2,4,3$ , $2,6,3$, etc..

• Be careful. You are allowed to have two consecutive odd numbers or two consecutive even numbers. Therefore, there are no restrictions on sequences of length $2$. – N. F. Taussig Jan 19 '16 at 19:35
• @N.F.Taussig Thank you for the reply. I have edited my post. I forgot to mention that I can have two consecutive odd/even numbers. But I'm still not quite sure how to sum it all up and find $a_3$. – Ilan Aizelman WS Jan 19 '16 at 19:37

It is equal to $3^n$ multiplied by the number of sequences of length $n$ of $O$ and $E$ that don't have $OOO$ or $EEE$.

Let $f_n$ be the number of sequences of $O$ and $E$ of length $n$ that do not contain $OOO$ or $EEE$, we call such sequences good sequences. Then we can see that $f_1=2,f_2=4$.

We now get a recursion:

How many good sequences of length $n$ end with two equal letters? $f_{n-2}$, this is because; given any sequence of length $n-2$ there is exactly one way to make a sequence of length $n$ ending with two equal letters.

How many good sequences of length $n$ end with two different letters? Clearly $f_{n-1}$.

Our recursion is therefore $f_n=f_{n-1}+f_{n-2}$.

The final answer is therefore $3^nf_n$.

• so for finding $a_3$ I take all the options, which are $6^3$ options available, and reduce $OOO$ and $EEE$ from that. which is $6^3 - 6 = a_3$? – Ilan Aizelman WS Jan 19 '16 at 20:06
• @IlanAizelmanWS No, there are just $108$ sequences of length $3$ that fulfill the criteria. – N. F. Taussig Jan 19 '16 at 20:07
• In your second sentence, you meant that do not contain OOO or EEE. – N. F. Taussig Jan 19 '16 at 20:15
• Sorry, that was an error. The possible sequences have the form EEO, EOE, EOO, OEE, OEO, OOE. There are $3$ choices for each position for each type, giving $27$ of each type or $6 \cdot 27 = 162$ sequences of length $3$, which agrees with the formula dREaM obtained. – N. F. Taussig Jan 19 '16 at 20:46
• @IlanAizelmanWS there are $6$ sequences with $E$ and $O$, but there are $162$ sequences with $\{1,2,3,4,5,6\}$. – Jorge Fernández Hidalgo Jan 19 '16 at 21:18