1
$\begingroup$

This question has two parts. The first part was easy.

a) How many four-letter words w using an n-letter alphabet satisfy $w_i \neq w_{i+1}$ for $i=1,2,3$

Simple. Choose the first letter in $n$ ways. Because no consecutive letter can have the same letter as the previous, we have $n-1$ ways for the last three for a total:

$$n \times (n-1) \times (n-1) \times (n-1) = n(n-1)^3$$


b) How many of the words in (a) also satisfy $w_4 \neq w_1$?

I'm struggling here. I thought of the possibilites, but I'm having trouble counting them.

Consider when $w_3 = w_1$ and when $w_3 \neq w_1$. Obviously, if $w_3 = w_1$, $w_4$ can be chosen in $n-1$ ways. Why? Take for example the standard alphabet. If we have the incomplete word:

A E A _

$w_4$ can be every letter except "A" to satisfy $w_4 \neq w_1$. Hence, $w_4$ has $n-1$ possibilities.

If $w_3 \neq w_1$ there are $n-2$ ways to choose $w_4$ by the same reasoning. Certainly, if we have the incomplete word:

A E C _

$w_4$ can be every letter except "A" and "C." $n-2$ ways.

But how can I count this? I thought it would be:

$$n \times (n-1)^2 \times (n-2)$$

But that doesn't take into account the special cases I considered above, does it?

$\endgroup$
4
$\begingroup$

Your answer to the first question is correct.

You have also correctly identified the cases in the second question.

Case 1: The third letter is the same as the first letter.

We have $n$ ways to select the first letter. Since the second letter must be different from the first, we can select it in $n - 1$ ways. We have only one choice for the third letter since it must be the same as the first letter. Since the last letter is different from the third letter, it must also be different from the first letter. Thus, there are $n - 1$ choices for the fourth letter. Hence, there are $$n \cdot (n - 1) \cdot 1 \cdot (n - 1) = n(n - 1)^2$$ such words.

Case 2: The third letter is different from the first letter.

We have $n$ ways to select the first letter. Since the second letter must be different from the first, we can select it in $n - 1$ ways. Since the third letter must be different from both the first letter and the second letter, the third letter can be selected in $n - 2$ ways. Since the fourth letter must be different from both the third letter and the first letter, we can select the fourth letter in $n - 2$ ways. Hence, there are $$n(n - 1)(n - 2)(n - 2) = n(n - 1)(n - 2)^2$$ such words.

Total: Since the cases are mutually exclusive, there are $$n(n - 1)^2 + n(n - 1)(n - 2)^2$$
four letter words in which each letters differs from the preceding letter and the last letter is different from the first letter.

$\endgroup$
  • $\begingroup$ Ah thank you. This clears everything up! $\endgroup$ – Kenneth Worden Mar 14 '17 at 23:50
2
$\begingroup$

The answer is $n(n-1)^2 + n(n-1)(n-2)^2$. Maybe a tree chart makes this clear but a don't know how to use tikz here :(

However I describe what I mean. You already figured out that there a two different cases: Either $w_3 = w_1$ or $w_3 \neq w_1$.

Case 1: In the first case that $w_3 = w_1$ you already know that $w_3 = w_1$ so you don't have a choice for the third latter which gives $$n\cdot (n-1) \cdot 1 \cdot (n-1) \quad \text{Opportunities}$$

Case 2: In the other case you know $w_3 \neq w_1$ and $w_3 \neq w_2$ so you have $(n-2)$ opportunities for $w_3$ and you also have $w_4 \neq w_3$ and $w_4 \neq w_1$ which gives altogether (in this case) $$n\cdot (n-1) \cdot (n-2) \cdot (n-2) \quad \text{Opportunities}$$

When you sum all opportunities together you receive what I already mentioned in the beginning.

$\endgroup$
  • $\begingroup$ You can insert diagrams by selecting the button that looks like the image of a mountain. In case 2, note that the fourth letter must be different from both the first letter and the third letter. $\endgroup$ – N. F. Taussig Mar 14 '17 at 23:50
  • $\begingroup$ Your answer was basically the same, however I can only choose one. Thank you! $\endgroup$ – Kenneth Worden Mar 14 '17 at 23:50
  • $\begingroup$ @N.F.Taussig lol I had that on my paper and then I forgot about the question and corrected that to $n-1$. facepalm... I will edit it $\endgroup$ – Nathanael Skrepek Mar 14 '17 at 23:54

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.