2
$\begingroup$

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

  • 3
    Possible duplicate of [How to count the number of k-ary sequences of length n that use all elements](https://math.stackexchange.com/questions/2845763/how-to-count-the-number-of-k-ary-sequences-of-length-n-that-use-all-elements)2018-07-11

4 Answers 4

3

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.

  • 0
    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 for2012-10-29
1

There are $4^{12}$ possibilities if there are no restrictions.

But there are exceptions. There are $3^{12}$ possibilities that are missing a given letter, and there are 4 letters, so we want to take away $4 \cdot 3^{12}$.

However, now it gets tricky. The four sets we subtracted have overlaps and we need to figure out those overlaps. We have to consider all the ones here we have double/triple counted and "took away" more than once.

If a string is missing two letters (i.e., both A and B), it will be counted twice. There are $2^{12}$ possibilities missing both A and B, $2^{12}$ possibilities missing both A and C, $2^{12}$ possibilities missing both A and D, $2^{12}$ possibilities missing both B and C, $2^{12}$ possibilities missing both B and D, and $2^{12}$ possibilities missing both C and D. All in all, there are $6 \cdot 2^{12}$ possibilities for missing two letters.

Lastly, we have to consider the final case of strings missing three letters. There are only 4 of them (all A's, all B's, all C's, and all D's). All A's was counted three times -- once under "missing C+D", once under "missing B+D", and once under "missing B+C", so we have to take away 2 of these copies. We had mistakenly added "all A's" back three times. Same for the other 3 letters. So minus $4 \cdot2=8$ here.

Thus, the final answer is

$4^{12} - 4 \cdot 3^{12} + 6 \cdot 3^{12}-4\cdot2 = 14676020$

I probably made a mental error in there somewhere, please correct me if you see one.

-3

I think the answer is 56(24 + 32). since every letter should appear once so break the 12 letters into 8 + 4, where 4 is compulsory (a combination of A,B,C,D so 4*3*2*1 = 24 arrangements). And the rest 8 can be all A, all B , all C,all D so 4 choices for each position so 4*8 = 32.

So, total is 24 + 32 = 56. Wat Say ??

  • 1
    I think you missed ABCDABCDABCD. Also AAABBBCCCDDD, AABBCCDDDDDD, and a few million others. You would be closer to the correct answer if you said $24\times4^8$ (note: $\times$ rather than $+$, and $4^8$ rather than $4\times8$), but even that would be missing some strings since there is no set of four positions in the string that _must_ be all different letters. When looking at an old question like this with an almost equally old answer it may pay to examine the other answer carefully before posting your own.2015-04-11
-3

$4^{12} - (^4C_1.3^{12} - ^4C_2.2^{12} + ^4C_3.1^{12})$