[Math] Forming n-letter words from letters ABCDEF

combinatoricsdiscrete mathematics

I have a real discrete structure problem :/
Suppose you have letters ABCDEF, how many n-letter words can be formed such that the frequency of A is an odd number? The letters can be repeated.
Can somebody tell me how to solve this?

Best Answer

Let $o(n)$ be the number of such words of length $n$ with an odd number of $A$’s. We can build these words by choosing an odd $k\in\{0,1,\ldots,n\}$, picking $k$ positions in the word for $A$’s, and filling the other $n-k$ positions with letters from the set $\{B,C,D,E,F\}$; given $k$, this can be done in $\binom{n}k5^{n-k}$ ways, so

$$o(n)=\sum_{{k=0}\atop{k\text{ odd}}}^n\binom{n}k5^{n-k}\;.$$

Let $e(n)$ be the number of words of length $n$ with an even number of $A$’s; clearly

$$e(n)=\sum_{{k=0}\atop{k\text{ even}}}^n\binom{n}k5^{n-k}\;.$$

There are $6^n$ words of length $n$, so $$e(n)+o(n)=6^n\;.\tag{1}$$ On the other hand,

$$\begin{align*} e(n)-o(n)&=\sum_{{k=0}\atop{k\text{ even}}}^n\binom{n}k5^{n-k}-\sum_{{k=0}\atop{k\text{ odd}}}^n\binom{n}k5^{n-k}\\\\ &=\sum_{k=0}^n\binom{n}k(-1)^k5^{n-k}\\\\ &=(-1+5)^n\\\\ &=4^n\;. \end{align*}\tag{2}$$

Combine $(1)$ and $(2)$ to solve for $o(n)$ and $e(n)$.

Added: You can also approach it by finding a recurrence and solving it for a closed form. Let $O_n$ be the set of words of length $n$ with an odd number of $A$’s, and let $E_n$ be the set of words of length $n$ with an even number of $A$’s. Let $w\in O_n$, let $w_f$ and $w_\ell$ be respectively the first and last letters of $w$, and let $w'$ be the word of length $n-2$ obtained by deleting $w_f$ and $w_\ell$ from $w$. If exactly one of $w_f$ and $w_\ell$ is an $A$, then $w'\in E_{n-2}$; otherwise, $w'\in O_{n-2}$. Conversely, any $w'\in E_{n-2}$ can be extended to a word in $O_n$ in $10$ ways by adding an $A$ at one end and a non-$A$ at the other, and any $w'\in O_{n-2}$ can be extended to a word in $O_n$ in $26$ ways by appending an $A$ at each end or a non-$A$ at each end. It follows that

$$\begin{align*} o(n)&=10e(n-2)+26o(n-2)\\ &=10\big(o(n-2)+e(n-2)\big)+16o(n-2)\\ &=10\cdot6^{n-2}+16o(n-2)\;. \end{align*}$$

This recurrence can be solved by a variety of techniques.