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

share|improve this question
    
Isn't $a_n = 1$ when $n=3$? –  tards Nov 4 '11 at 6:08
1  
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
2  
@tards: Zero As also counts as an even number. –  joriki Nov 4 '11 at 6:55
3  
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
show 1 more comment

4 Answers

up vote 6 down vote accepted

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

share|improve this answer
1  
+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
show 1 more comment
  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.$$

share|improve this answer
    
You might note that this argument is exactly analogous to the generating function proof. –  Phira Nov 4 '11 at 11:24
add comment

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.

share|improve this answer
    
It seems (1) and (2) are the same? –  joriki Nov 4 '11 at 17:48
add comment

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

share|improve this answer
3  
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
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.