0
$\begingroup$

I need to find the number of different strings that need to be formed from {a,b,c} in which there needs to be at least one from each letter. The question is to find the number of strings with length 5. So in my opinion i think i need to answer this with recurrent relations like a b c _ _ or b a c _ _ or c a b _ _ (n-2) ? but i don't know how to continue!

Thanks!

$\endgroup$
  • 1
    $\begingroup$ You cannot assume the first three letters are different. $\endgroup$ – N. F. Taussig May 25 at 15:00
  • $\begingroup$ Yeah i thought that also there are other acceptable answers such as: a a b c c and so on.. $\endgroup$ – Blaze May 25 at 15:03
1
$\begingroup$

Method 1: Observe that there are two ways to write $5$ as a sum of three positive integers. \begin{align*} 5 & = 3 + 1 + 1\\ & = 2 + 2 + 1 \end{align*}

$3 + 1 + 1$: Choose which of the three letters appears in the string three times. Choose three of the five positions for that letter in the string. Arrange the remaining two letters in the remaining two positions.

$2 + 2 + 1$: Choose which letter appears once. Choose in which of the five positions that letter appears. That leaves four positions to be filled with the two remaining letters. Choose which two of the remaining four positions will be occupied by the remaining letter that appears first in an alphabetical list. The remaining two positions must be filled with the remaining letter.

Method 2: We use the Inclusion-Exclusion Principle.

If there were no restrictions, there would be three ways to fill each of the five positions. From these $3^5$ sequences, we must exclude those in which not all three letters are used.

There are three ways to exclude one of the letters. For each such choice, the remaining positions can be filled in two ways.

However, if we subtract these cases from the total, we will have subtracted each case in which only one letter is used twice, once for each of the two ways we could designate one of the other letters as the excluded letter. Since we only want to subtract these sequences once, we must add these three sequences to the total.

$\endgroup$
  • $\begingroup$ Thank you for the lengthy and detailed answer! $\endgroup$ – Blaze May 25 at 15:17
1
$\begingroup$

Hint: compute the total number of strings and subtract those which use only two letters. Then think about what has happened to ones that have all one letter. See the inclusion-exclusion principle.

$\endgroup$
  • $\begingroup$ Thank you for your answer! $\endgroup$ – Blaze May 25 at 15:09

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.