10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Phira
    May 12, 2012 at 16:44
  • 1
    $\begingroup$ 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$. $\endgroup$
    – carlop
    May 13, 2012 at 16:45

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I'll try that now. $\endgroup$ May 12, 2012 at 16:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .