Counting words with parity restrictions on the letters

Let $a_n$ be the number of words of length $n$ from the alphabet $\{A,B,C,D,E,F\}$ in which $A$ appears an even number of times and $B$ appears an odd number of times. Using generating functions I was able to prove that $$a_n=\frac{6^n-2^n}{4}\;.$$

I was wondering if the above answer is correct and in that case what could be a combinatorial proof of that formula?

-
Isn't $a_n = 1$ when $n=3$? – tards Nov 4 '11 at 6:08
If you were able to prove it, then it must be correct (or else mathematics is inconsistent). – Gerry Myerson Nov 4 '11 at 6:09
@tards: Remember that in displayed equations the punctuation at the end should go inside the double dollar signs (preferably set off by a \;); otherwise it gets placed on the next line of text. – joriki Nov 4 '11 at 6:09
@tards: Zero As also counts as an even number. – joriki Nov 4 '11 at 6:55
Please, please use good titles in the future, I know that I recently answered a similar question, but I cannot find it because the title is probably also "a combinatorial problem" or "a type of words". – Phira Nov 4 '11 at 11:31

Call $s_n$ the number of words with numbers of A and B of the same parity, and $d_n$ the number of words with numbers of A or B of different parities. Since there are as many words with an odd number of A and an even number of B than words with an even number of A and an odd number of B, one is after $a_n=\frac12d_n$.

Obviously, $s_n+d_n$ is the total number of words of length $n$, that is, $s_n+d_n=6^n$.

On the other hand, adding A or B to a word of length $n$ produces a word of the other type, and adding C, D, E or F produces a word of the same type, hence $s_{n+1}=4s_n+2d_n$ and $d_{n+1}=4d_n+2s_n$.

This yields $s_{n+1}-d_{n+1}=2(s_n-d_n)$. Since $s_1=4$ and $d_1=2$, $s_n-d_n=2^{n}$.

Finally, $a_n=\frac12d_n=\frac14(s_n+d_n)-\frac14(s_n-d_n)=\frac14(6^n-2^n)$.

Edit Here is an alternative proof of the relation $s_n-d_n=2^{n}$, based on the probabilistic method.

Draw uniformly at random a word from the $6^n$ words of length $n$ and let $X_k=-1$ if the $k$th letter is A or B and $X_k=+1$ otherwise. The random variables $(X_k)_{1\leqslant k\leqslant n}$ are independent, $X_k=-1$ with probability $\frac13$, $X_k=+1$ with probability $\frac23$, hence $\mathrm E(X_k)=1-2\frac13=\frac13=x$.

Let $Y_n=X_1X_2\cdots X_n$. Then $Y_n=+1$ if the word contains numbers of A and B of the same parity and $Y_n=-1$ otherwise, thus $6^n\mathrm P(Y_n=+1)=s_n$ and $6^n\mathrm P(Y_n=-1)=d_n$. The independence of the random variables $(X_k)_{1\leqslant k\leqslant n}$ implies that $\mathrm E(Y_n)=\mathrm E(X_1)\mathrm E(X_2)\cdots \mathrm E(X_n)=x^n$, hence $$s_n-d_n=6^n\mathrm E(Y_n)=6^nx^n=2^n.$$ This also proves that, for the same problem using an alphabet of $\color{red}{N\geqslant4}$ letters, $x=1-\frac4N$ hence $$\color{red}{a_n=\frac{N^n-(N-4)^n}4}.$$ This formula suggests that a proof by inclusion-exclusion might be available, which would yield the successive powers of $4$ in the binomial expansion of $(N-4)^n$.

-
+1 for both solving the problem elegantly and correctly and pointing out the basic errors in the other answers (including mine :-) – joriki Nov 4 '11 at 7:37
@joriki, thanks. (I like the revised version of your deleted post...) – Did Nov 4 '11 at 8:03
I like the probabilistic proof -- I'd be interested in any insight you have into how you came up with that. – joriki Nov 4 '11 at 17:59
@joriki, it is not so easy to answer your question. I guess the first clue was $6^n$ in a problem involving words of length $n$ over an alphabet of size $6$. This suggests a uniform distribution over this set of words. At this point the quantity to be explained is $6^{-n}a_n$. Forgetting for a moment the division by $4$, one pictures this as $1$ minus something, that is, the probability of a complement. This is a second clue. The something being $\frac26$ to the power $n$, the third clue is product hence independence. From here, there is no choice .../... – Did Nov 16 '11 at 14:47
.../... but to consider the $n$ random variables describing each letter of the word (which were later simplified into Bernoulli's) and to use them to write down the event whose probability should be $6^{-n}a_n$. When I grabbed a pencil and a piece of paper to convert these hunches into a full proof, my biggest worry was the denominator $4$, because it indicates one has to find $4$ equiprobable disjoint events whose union is product-like enough for the independence to come into play... But, well, this can be done. – Did Nov 16 '11 at 14:47
1. First regard words that contain at least an $A$ or a $C$ and at least a $B$ or a $D$.

Now use the functions "convert the first letter that is $A$ or $C$ in the other one of the two" and "convert the first letter that is $B$ or $D$ in the other one of the two".

These two functions are clearly bijections and commute, so for these words exactly a fourth has the desired property.

2. Secondly, regard words that either do not contain $A$ or $C$ or do not contain $B$ or $D$, but not both properties are true.

Words that do not contain a $B$ or a $D$ will not contain an odd number of $B$s.

Words that do not contain an $A$ or a $C$ automatically contain an even number of $A$s and the second function above shows bijectively that half of the words work.

Together, again a fourth of all the words have the desired property.

3. Finally, regard words that do not contain $A$,$B$,$C$,$D$. There are $2^n$ of them.

They do not have an odd number of $B$s.

So, in summary, we take all words $6^n$, divide by four, but we have to subtract the contribution $2^n/4$ of the last case, which gives the formula $$(6^n-2^n)/4.$$

-
You might note that this argument is exactly analogous to the generating function proof. – Phira Nov 4 '11 at 11:24

I don’t know whether you’d call them combinatorial, but here are two completely elementary arguments of a kind that I’ve presented in a sophomore-level discrete math course. Added: Neither, of course, is as nice as Didier’s, which I’d not seen when I posted this.

Let $b_n$ be the number of words of length $n$ with an odd number of $A$’s and an odd number of $B$’s, $c_n$ the number of words of length $n$ with an even number of $A$’s and an even number of $B$’s, and $d_n$ the number of words of length $n$ with an odd number of $A$’s and an even number of $B$’s. Then

$$a_{n+1}=4a_n+b_n+c_n\;.\tag{1}$$

Clearly $a_n=d_n$: interchanging $A$’s and $B$’s gives a bijection between the two types of word. $(1)$ therefore reduces to

$$a_{n+1}=4a_n+b_n+c_n\;.\tag{2}$$

But $6^n=a_n+b_n+c_n+d_n=b_n+c_n+2a_n$, so $b_n+c_n=6^n-2a_n$, and $(2)$ becomes $$a_{n+1}=2a_n+6^n,a_0=0\;.\tag{3}$$ $(3)$ can be solved by brute force:

\begin{align*} a_n&=2a_{n-1}+6^{n-1}\\ &=2(2a_{n-2}+6^{n-2})+6^{n-1}\\ &=2^2a_{n-2}+2\cdot 6^{n-2}+6^{n-1}\\ &=2^2(2a_{n-3}+6^{n-3})+2\cdot 6^{n-2}+6^{n-1}\\ &=2^3a_{n-3}+2^2\cdot 6^{n-3}+2\cdot 6^{n-2}+6^{n-1}\\ &\;\vdots\\ &=2^na_0+\sum_{k=0}^{n-1}2^k6^{n-1-k}\\ &=6^{n-1}\sum_{k=0}^{n-1}\left(\frac13\right)^k\\ &=6^{n-1}\frac{1-(1/3)^n}{2/3}\\ &=\frac{2^{n-1}3^n-2^{n-1}}{2}\\ &=\frac{6^n-2^n}4\;. \end{align*}

Alternatively, with perhaps just a little more cleverness $(1)$ can be expanded to

\begin{align*} a_{n+1}&=4a_n+b_n+c_n\\ b_{n+1}&=4b_n+2a_n\\ c_{n+1}&=4c_n+2a_n\;, \end{align*}\tag{4}

whence

\begin{align*}a_{n+1}&=4a_n+4b_{n-1}+2a_{n-1}+4c_{n-1}+2a_{n-1}\\ &=4a_n+4a_{n-1}+4(b_{n-1}+c_{n-1})\\ &=4a_n+4a_{n-1}+4(a_n-4a_{n-1})\\ &=8a_n-12a_{n-2}\;. \end{align*}

This straightforward homogeneous linear recurrence (with initial conditions $a_0=0,a_1=1$) immediately yields the desired result.

-
It seems (1) and (2) are the same? – joriki Nov 4 '11 at 17:48

There's a combinatorial method (by the way, I consider generating functions to be a combinatorial method, but never mind) using inclusion-exclusion. Count the total number of $n$-letter words, subtract off the ones with an odd number of $A$, subtract off the ones with an even number of $B$, then add back in the ones with both an odd number of $A$ and an even number of $B$. Of course, you have to work out the details....

-
Since the number of words with an odd number of A plus the number of words with an even number of B is equal to the total number of words, and the number of words with both an odd number of A and an even number of B is equal to the number of words with both an even number of A and an odd number of B, I am not sure this method leads to anything else than 1=1... – Did Nov 4 '11 at 6:58
Aargh.${}{}{}{}$ – Gerry Myerson Nov 4 '11 at 11:51