Let $a_n$ be the number of words of length $n$ with letters from the alphabet $\{0, 1, 2, 3\}$ containing an odd number of zeros.

I have already verified that this is given by the recurrence relation: $$a_{n+1} = 2 a_n + 4^n.$$ where $a_0=0$.

I then used the method of a generating function to solve this and arrive at: $$a_n= 2^{2n-1} - 2^{n-1}.$$ Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.

This problem can also be solved alternatively, using a new sequence $B_n$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.

Another way to fi nd the same result is as follows:

1) Consider the set $B_n$ of words of length $n$ with at least one $0$ or $1$.

How many of those are there? I am not sure how to express this in terms of $a_n$

2) In this set there are exactly as many words with an even number of zeros as there are with an odd number of zeros. Just change the first occuring $0$ or $1$ with its di erence with $1$ $\dots$ (not sure what is meant here, the wording is a bit vague)

I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?


For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.

To expand on (2), let $O_n \subset B_n$ be the subset of strings with an odd number of zeros and $E_n \subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n \to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $\frac{1}{2}(4^n - 2^n)$.

| cite | improve this answer | |
  • $\begingroup$ That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you. $\endgroup$ – Wesley Strik Dec 14 '18 at 6:44

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.