I'm trying to finish up a counting problem that goes like this: There's an alphabet of 'a,b,c,d', and each letter can be put in 4 spots. From this alphabet,
a) How many strings can be made by using only 1 'a'? (Other letters can be used more than once)
b) How many strings can be made with 2 'a's?
c) How many strings can be made with no repetitions?
d) How many strings can be made with NO MORE THAN 3 of the same letter?
For a), I see that there must be a character 'a' and it can go in any of the 4 spaces that I have available. From there, I can allocate any number of the remaining 3 letters into the remaining 3 spaces. I see this as a permutation with repetitions, so I model my final expression as $4*3^3=108$.
For b), I take a similar approach. There are 2 'a's, so there are 4 spaces in which the first can be placed and 3 in which the 2nd can be placed. From there, there are 2 spaces in which 3 different letters can be placed, so I model my expression as $4*3*3^2=108$.
For c) there are no repetitions so each letter must be used once. This is a simple permutation without repetition where I have 4 letters and 4 spaces, resulting in $4!=24$.
Finally, for d), I am most uncertain. In this case, since there can be at most 3 of the same letter (meaning there can be 3, 2, or 1 of a certain letter), then I should find each individual number of permutations for each. So if there are 3 of the same letter, there is 4 possible spaces for the first, 3 for the second, 2 for the third, and the last space is occupied by one of the 3 unused letters. If there are 2 of the same letter, I have the same case as in b). If there is 1 of the same letter, I have the same case as in a). I won't calculate 0 because if I had 0 of one letter, another would have to have at least 2 of the same. So my final expression is $(4*3*2*3)+108+108=288$.
I think I am approaching this problem incorrectly, so any help is greatly appreciated!
Best Answer
Your answers to a) and c) are correct.
In b), the two a's are indistinguishable, so you must divide by 2: $$\frac{4 \cdot 3 \cdot 3^2}{2}=54.$$
You are on the right track for d). So as not to give you all the answers, I'll answer the question of counting words in which a single letter appears AT LEAST 3 times.
First of all, there are clearly 4 ways in which a single letter appears all four times.
Now let's assume the letter a appears exactly 3 times. Here you made the same mistake as in part b). These three a's are indistinguishable, so we have to divide by the number of ways in which they can rearranged, so the total number of ways to place the a's is $$\frac{4\cdot 3 \cdot 2}{3 \cdot 2 \cdot 1}.$$ Just as you said, there are 3 remaining letters, so the total words with exactly 3 a's is $$\frac{4\cdot 3 \cdot 2}{3 \cdot 2 \cdot 1} \cdot 3.$$ Now, the same argument works for b, c and d. Thus, overall, we have $$4 + 4 \cdot \frac{4\cdot 3 \cdot 2}{3 \cdot 2 \cdot 1} \cdot 3 = 52.$$