4
$\begingroup$

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?

  • 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".2011-11-04

4 Answers 4

7

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

  • 0
    Interesting -- thanks!2011-11-17
4
  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.$

  • 0
    You might note that this argument is exactly analogous to the generating function proof.2011-11-04
3

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.

  • 0
    It seems (1) and (2) are the same?2011-11-04
0

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

  • 0
    Aargh.${}{}{}{}$2011-11-04