Take the 2-minute tour ×

How many strings of length 12 can we compose using letters A,B,C, and D if every letter should appear at least once?

can someone walk me through this? I believe using the concept of the sieve formula is what i am supposed to use but I can't figure out where to start, my first thought is that 12! is the total number of permutations but then I know i have to take into account that each letter must be used once but I can't get any farther

EDIT: total number of strings with no restrictions is 4^12

please if someone can walk me through that would be great

share|improve this question
add comment

1 Answer

Hint: you need the inclusion-exclusion principle. How many total strings are there? How many strings using only A, B, C are there? It is easier to approach it this way, by removing the ones that have only three letters. There are four times as many missing one letter, but the ones that have only A, B are overcounted in the subtraction.

share|improve this answer
so the total number of strings is 12! correct? and then from there its something like this: 12! - (total of strings with only A B C) - (total of strings with only A B D) - (total of strings with only B C D)....etc? –  kfem Oct 29 '12 at 4:09
No, as you take each character with replacement, the number of strings is $4^{12}$. At each point you have four choices. You are right that you then deduct the ones that have only three different letters, but then you deducted the ones in AB twice, as part of ABC and ABD. –  Ross Millikan Oct 29 '12 at 4:11
Oh ok that makes sense. But when I subtract the ones that only have A B C, what about the ones say that only have A or only have B or only have C or D? –  kfem Oct 29 '12 at 4:22
@qwerty: first you deal with the ones that have two letters. You subtracted them twice when thinking about those with only three letters, so now you put them back in. Now how may times is the string of all A's counted? You need to fix that problem, then you are done. –  Ross Millikan Oct 29 '12 at 4:24
im sorry I guess I am just a little confused about adding and subtracting from the total number of strings and how many times we are over counting that we have to account for –  kfem Oct 29 '12 at 5:13
add comment

Your Answer


