Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $w(n)$ denote the number of words of length $n$ over the alphabet $\{1,2,3\}$ with the restrictions that in a word the parity of $1$s be even and the parity of $2$s odd.

I have written out the possible words for some small values of $n$, hoping to see a relationship which would lead to a recurrence relation, but so far this has not helped. Trying to count the $w(n)$ by considering a general word $a_1a_2...a_n$ and counting possibilites for $a_i$ also doesn't seem to be a tractable solutions because of the dependency between the $a_i$. Any suggestions?

I am not looking for an answer to this problem, only for suggestions as to how one approaches a problem of this kind or for hints.

Following Ross Millikan's suggestion:

Define the functions $OO(n),OE(n),EO(n),EE(n)$, where the first digit represents the parity of $1$ and the second the parity of $2$. Then clearly

$$w(n)=OO(n)+OE(n)+EO(n)+EE(n).$$

Furthermore, $w(n)=3^n$ since each of the $n$ letters has three possible values. Now, one can define the function $s:OE(n)\rightarrow EO(n)$ by having it switch $1$ with $2$ and $2$ with $1$. Since this map is bijective, we have $OE(n)=EO(n)$. We can now derive a recurrence for $EO(n)$. An element of $EO(n)$ can be constructed from an element of $OO(n-1)$ by adjoining a $1$, from an element of $EE(n-1)$ by adjoining a $2$ and from $EO(n-1)$ by adjoining a $3$, which gives the recurrence

$$EO(n)=OO(n-1)+EO(n-1)+EE(n-1).$$

Using the relationship between our four functions and the symmetry between $EO(n)$ and $OE(n)$ we see that \begin{align*} EO(n)&=w(n-1)-OE(n-1)\\ &=3^{n-1}-EO(n-1). \end{align*} A closed form for this recurrence can be obtain by using the formula from this question by setting $b=-1,c=1$ and $d=3$, which gives

$$EO(n)=\frac{3^n-(-1)^n}{4}.$$

share|improve this question
    
I suggest that you look at math.stackexchange.com/questions/35063/… . In particular, if you adapt my answer or yunone's equivalent generating function approach, you do not need to write recurrence relations. –  Phira May 12 '12 at 16:44
1  
Hint: write $OE(n) = OE(n-1) + OO(n-1) + EE(n-1) = 3^{n-1} - EO(n-1) = 3^{n-1} - OE(n-1)$, with the condition $OE(0)=0$. –  carlop May 13 '12 at 16:45
add comment

1 Answer

up vote 3 down vote accepted

Hint: One approach is to define four functions. Let $OE(n)$ be the number of words of length $n$ which have an odd number of $1$'s and an even number of $2$'s and three similar ones. Write the recurrence relations between these four. They stay closely balanced, so they are all just about $\frac {3^n}4$ in each one. Maybe you can find a proof of the small correction (note that this is not an integer, which the final result must be)

Added: you are right that $EO(n)=OE(n)$ by symmetry. That is a good thing to think about, as it gets you down to three functions. You need to write a recurrence for each function separately. A word where both are odd can come from a word where both are odd by adding a 3, from EO by adding a 1, or from OE by adding a 2. So $OO(n)=EO(n-1)+OE(n-1)+OO(n-1)$ Your starting condition is $EE(0)=1, \text{others}(0)=0$ because the empty word is even in both. I made a spreadsheet to calculate the first dozen values or so. You can then see a pattern in the corrections, which you can prove from the recurrences. Your final answer is then $EO(n)$

share|improve this answer
    
I'll try that now. –  Holdsworth88 May 12 '12 at 16:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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