3
$\begingroup$

$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..

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – N. F. Taussig Jan 19 '16 at 19:35
  • $\begingroup$ @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$. $\endgroup$ – Ilan Aizelman WS Jan 19 '16 at 19:37
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Ilan Aizelman WS Jan 19 '16 at 20:06
  • $\begingroup$ @IlanAizelmanWS No, there are just $108$ sequences of length $3$ that fulfill the criteria. $\endgroup$ – N. F. Taussig Jan 19 '16 at 20:07
  • $\begingroup$ In your second sentence, you meant that do not contain OOO or EEE. $\endgroup$ – N. F. Taussig Jan 19 '16 at 20:15
  • 1
    $\begingroup$ 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. $\endgroup$ – N. F. Taussig Jan 19 '16 at 20:46
  • 2
    $\begingroup$ @IlanAizelmanWS there are $6$ sequences with $E$ and $O$, but there are $162$ sequences with $\{1,2,3,4,5,6\}$. $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.