2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Hint: If the frequency of $A$ is an odd number that implies $A$ must appear in the word at least once.

Now let $f_i$ be the total $n$-letter words possible that contains exactly $i$ number of $A$'s.

So the total number of $n$-letter words with an odd number of $A$'s would be: $$f_1+f_3+\cdots+f_n,\text{ if $n$ is odd}$$

$$f_1+f_3+\cdots+f_{n-1},\text{ if $n$ is even}$$

$\endgroup$

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.