1
$\begingroup$

I'd like to see if what I did below makes sense.


We are not allowed to have words like $ABCDE$ because the words must contain exactly three different letters, not at least three different letters. So, the possible permutations are $ABCCC, ABBCC, CDEEE, \ldots$

Now it's clear that our problem can be rewritten as

Find the number of five-letter words that use letters from the set $\{X, Y, Z\}$ where $X, Y, Z \in \{A, B, C, D, E\}$ at least once.

So, we have two sets:

Set $1$ (one of the letters repeated three times): $XYZZZ, XXXYZ, YYYXZ$

Set $2$ (two of the three letters repeated twice each): $XYYZZ, XXYZZ, XXYYZ$

Now the number of permutations of $XYZZZ$ is $\binom {5}{1, 1, 3} = \frac {5!}{1! \cdot 1! \cdot 3!} = 20.$ Since there are two more words in the set $1$, the number of all the possible permutations of this set is $3 \cdot \binom {5}{1, 1, 3} = 60.$

The number of permutations of $XYYZZ$ is $\binom {5}{1, 2, 2} = \frac{5!}{1! \cdot 2! \cdot 2!} = 30.$ Since there are two more permutations in the set $2$, the number of all the possible permutations of this set is $3 \cdot \binom {5}{1, 2, 2} = 90.$

Thus, the number of all the words with the given condition is $\binom 52 \left(3\binom {5}{1, 1, 3} + 3\binom {5}{1, 2, 2}\right) = 1500$ where the binomial coefficient is the number of places to put $X, Y, Z$

EDIT:

Here's the model problem:

Find the number of words of a given length from a given set of letters, if each letter must occur at least once in each word.

Solution: $T(m, n) = \sum_{m_i \ge 1} \binom{m}{m_1,\ldots, m_n}$ where $\sum_{i =1}^n m_i = m.$

The problem in my OP has an answer in the back of my book given as $\binom{5}{2}T(5, 3) = 1500.$

$\endgroup$
  • $\begingroup$ From your examples it seems you want the letter to appear in alphabetic order in your word. Is that a constraint in the question ? Otherwise, of course, you also have to consider words like ZXZYX, which you currently seem to leave aside. $\endgroup$ – Evargalo May 16 '17 at 15:48
  • $\begingroup$ @Evargalo, no, that's not necessary. $\endgroup$ – 4chan May 16 '17 at 15:50
  • $\begingroup$ No, your analogy is incorrect. In the problem statement, we'd count ADEEE, well as ABCCC, as distinctly different, but valid for counting. (Note that Given the above examples would, we are using 5 letters, yet in each case, the string meets the original question, but not your alternative approach. $\endgroup$ – Namaste May 16 '17 at 15:50
  • 4
    $\begingroup$ I don't get the downvote. Downvoting an incorrect approach is not a reason for downvoting. Alternatively, note the askers attempt, and effort. We should credit any question that shows effort on the part of the asker, but at the very least, not penalize them. $\endgroup$ – Namaste May 16 '17 at 15:56
  • 1
    $\begingroup$ @N.Shales, yes exactly what I am saying. Thank you! $\endgroup$ – 4chan May 16 '17 at 17:19
3
$\begingroup$

You are getting the right answer, but your explanation of it doesn't sound quite right. I would approach it this way:

First, pick two letters not to use. This can be done in ${5\choose2}$ ways. Next, with the remaining three letters, consider the two cases:

  1. Pick one letter to use three times, the other two being used just once. This can be done $3$ ways, and then the letters can be arrange in $5\choose1,1,3$ ways.

  2. Pick one letter to use just once, with the other being being used twice each. Again, there are $3$ choices for the singlet, and then $5\choose1,2,2$ ways to arrange the letters.

The total number of words with three different letters is thus

$${5\choose2}\left(3{5\choose1,1,3}+3{5\choose1,2,2}\right)=10(3\cdot20+3\cdot30)=1500$$

$\endgroup$
  • $\begingroup$ I see where I tripped up. Well, I am still glad I was able to get the main part somewhat correct :) Thank you! $\endgroup$ – 4chan May 16 '17 at 16:24
1
$\begingroup$

A solution by substraction:

  • Number of five-letter words with a five-letters alphabet: 5^5

  • Number of them with five different letters: 5!

  • Number of them with four different letters: $5!*\binom{5}{2}$ (you gotta pick the letter that doesn't appear and the one that appears twice)
  • Number of them with two different letters: $2^5*\binom{5}{2}-4*5$ (picking two letters * all the words with a 2-letters alphabet - 5 one-letter words counted 4 times each)
  • Number of them with one single letter: 5

Hence the number of five-letter words with exactly three different letters: $5^5-5!-5!*\binom{5}{2}-(2^5*\binom{5}{2}-4*5)-5=1500$

$\endgroup$
  • $\begingroup$ Good to know because I found out we can also use $n!S(k, n)$ to solve this problem. Thank you. $\endgroup$ – 4chan May 16 '17 at 16:31

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.