How many 5 letter words can we make subject to the following conditions:
-
We can use the letters a, b, c, d, e.
-
Any letter can be used more than once or not at all.
-
No letter can be adjacent to itself anywhere within the sequence. (The first and last letters aren't considered to be adjacent.)
-
No letter can be used more than twice.
Showing my work. Let's go through the cases:
- 1 of each letter. This is just 5! = 120 possibilities.
- 2 of one letter, 1 of each of the remaining 3 letters. The possible configurations are: xoxoo, xooxo, xooox, oxoxo, oxoox, ooxox. There are 6 of them, hence 6(5 * 4 * 3 * 2) = 720 possibilities.
- 2 of two letters, 1 of the remaining letter. The possible configurations are: xyxyo, xyxoy, xyoxy, xoyxy, xyoyx, oxyxy. There are 6 of them, hence 6(5 * 4 * 3) = 320 possibilities.
So there should be a total of 120 + 720 + 360 = 1200 such 5 letter words. Is this correct?
Update in response to comment:
Are these four separate problems or do we wish to count the number of five-letter words that satisfy all four of the stated conditions?
I want to count the number of five-letter words that satisfy all four of the stated conditions.
Best Answer
Your strategy is sound, but your result is not correct since you overlooked possible configurations in the case where two letters each appear twice and a third letter appears once.
Five distinct letters: There are indeed $5!$ arrangements in which each letter is used once.
One letter appears twice, with three other letters each appearing once: There are five ways to select the letter that appears twice. If there were no adjacency restriction, there would be $\binom{5}{2}$ ways to select two positions for that letter. Of these placements, there are four in which the letter that appears twice would appear in adjacent positions since the first of those letters would have to occur in one of the first four positions. Hence, there are $\binom{5}{2} - 4$ admissible ways to place the letters that appears twice. There are $\binom{4}{3}$ ways to select which three of the other four letters will each appear once. There are $3!$ ways to arrange those distinct letters in the remaining three positions. Hence, there are $$\binom{5}{1}\left[\binom{5}{2} - 4\right]\binom{4}{3}3!$$ arrangements in which one letter appears twice, three other letters each appear once, and no letter is adjacent to itself. This agrees with your calculation.
Two letters each appear twice and a third letter appears once: There are $\binom{5}{2}$ ways to select the two letters that each appear twice and $\binom{3}{1}$ ways to select the letter that appears once.
If there were no adjacency restrictions, there would be $\binom{5}{2}\binom{3}{2}$ possible arrangements of the selected letters: pick two of the five positions for the letter that appears twice which appears first in an alphabetical list, pick two of the remaining three positions for the other letter that appears twice, and place the letter that appears once in the remaining position.
From these arrangements, we must those arrangements in which a letter is adjacent to itself.
A letter is adjacent to itself: There are two ways to select the letter which appears adjacent to itself. Then we have four objects to arrange: the double letter, two copies of the other letter that appears twice, and the letter that appears once. There are $\binom{4}{2}$ ways to select two of the four positions for the letter that appears twice and $2!$ ways to arrange the double letter and the single letter in the remaining two positions. The single letter must fill the remaining position. Hence, there are $$\binom{2}{1}\binom{4}{2}2!$$ arrangements in which a letter appears adjacent to itself.
However, if we subtract that amount from the total, we will have subtracted too much since we will have subtracted each arrangement in which two letters are each adjacent to themselves twice. We only want to subtract those cases once, so we must add them to the total.
If two letters are each adjacent to themselves, we have three objects to arrange: two double letters and one single letter. The three distinct objects can be arranged in $3!$ ways.
Hence, by the Inclusion-Exclusion Principle, there are $$\binom{5}{3}\binom{3}{2} - \binom{2}{1}\binom{4}{2}2! + 3!$$ placements of two letters that each appear twice and a letter that appears once in which no letter is adjacent to itself.
Therefore, the number of arrangements in which two letters each appear twice, a third letter appears once, and no letter is adjacent to itself is $$\binom{5}{2}\binom{3}{1}\left[\binom{5}{3}\binom{3}{2} - \binom{2}{1}\binom{4}{2}2! + 3!\right]$$
Total: Since the three cases are mutually exclusive and exhaustive, the number of five-letter words that satisfy the four conditions is $$5! + \binom{5}{1}\left[\binom{5}{2} - 4\right]\binom{4}{3}3! + \binom{5}{2}\binom{3}{1}\left[\binom{5}{3}\binom{3}{2} - \binom{2}{1}\binom{4}{2}2! + 3!\right]$$