1

Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's?

I know that you need to break it down into cases where the sequence starts with either a 0 OR a 1 or a 2 and based on that you determine the expression for a sequence of length n based on the subsequences of length n-1. However, I'm stuck in breaking it down into the cases and going forward from there.

Thanks for any help in advance!

user2565148
  • 111
  • 1
    Welcome to Math.SE! Please, consider updating your question with a bit more context, such as what you've tried and where you're getting stuck. This will help us get a better sense of how we can help! – Nick Peterson Apr 30 '14 at 02:48
  • Thanks! I've updated my question to be more specific. – user2565148 Apr 30 '14 at 05:20

1 Answers1

3

Here is an answer using generating functions. With the digits $0,1$ and $2$ represented by $u,v$ and $w$ your sequences have the generating function $$(u+v+w)^n.$$

Therefore sequences with even count of zero digits have the generating function $$\frac{1}{2} \left((u+v+w)^n + (-u+v+w)^n\right).$$ We also have an even number of one digits, which gives $$\frac{1}{4} \left((u+v+w)^n + (-u+v+w)^n\right) + \frac{1}{4} \left((u-v+w)^n + (-u-v+w)^n\right).$$ We are only interested in the count so we put $u=v=w=1$ to obtain $$\frac{1}{4} 3^n + \frac{1}{2} + \frac{1}{4} (-1)^n.$$ This is the following sequence: $$1, 1, 3, 7, 21, 61, 183, 547, 1641, 4921, 14763,\ldots$$ which is OEIS A122983.

Marko Riedel
  • 61,317