1
$\begingroup$

There are n different characters namely a, b, c, d. Use them to compose n-length string. Count the number of different n-length strings which at least contain one a, one b and one c.

My previous idea is like: Set A contains strings with at least one a. Similarly we have set B and C. So |A| = |B| = |C| = n * 4^(n-1). Firstly, choose one place of n (n possibilities) to set it to character a. Then n-1 places left with 4^(n-1) possibilities.

But some guys say this is not right. He suggests that the right answer should be |A| = |B| = |C| = 4^n - 3^n. Could you guys explain why it does not work?


EDIT 1:
I think there is a rule out there that I should follow when counting this kind of permutations. I need to find it out. Otherwise, I would make similar mistake next time without consciousness. It is essential to summarize the tip when and how I avoid this kind mistake.

Could someone figure the rule out?


EDIT 2
I think there is rule somehow:
When counting elements with property P, we cannot split the counting process into pieces. That is to say we cannot split property P into P = P1 + P2 + ... + Pk. This usually repeats one element several times.

For the above problem, I split the number of at least 1 a of a n-length string into two sub-properties as 1 a and 0 and/or more a's. This will repeatedly count some strings with more than 1 a. Like n = 5, abcaa will be counted 3 times since it has 3 a's.

$\endgroup$
1
$\begingroup$

Suppose that $n=5$, and consider the string $aaabc$. You count this once as $\underline{a}aabc$, once as $a\underline{a}abc$, and yet a third time as $aa\underline{a}bc$, where in each case the underlined $a$ is the one that you chose first, and the other four characters were chosen as one of the $4^{5-1}$ possibilities for. Thus, you’ve counted the same string three times in your figure of $n\cdot4^{n-1}$. In general you’ll find that if a string has $k$ copies of the letter $a$, it gets counted $k$ times in your figure of $n\cdot4^{k-1}$. Thus, you are badly overcounting the number of strings containing at least one $a$.

There are $4^n$ strings of length $n$ altogether, and there are $3^n$ strings of length $n$ containing no $a$, so there are actually $4^n-3^n$ strings of length $n$ containing at least one $a$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Brian, you tell me! Though I am clear where I made the mistake. But I bear a little worry in mind. I still cannot master the rule I should follow next time. Maybe next time, the question was totally different background. Could you summarize the tip when and how should I avoid this kind mistake? $\endgroup$ – Zack Jun 29 '13 at 4:09
  • $\begingroup$ @Zack: I can’t give you a simple, general rule to prevent this kind of mistake: there are too many different kinds of problems. I can say, though, that overcounting is one of the most common mistakes, so you should always ask yourself whether you might be counting the same object more than once. For this specific error, notice that if you have to choose at least $k$ of something, but you can choose more than $k$, it’s a bad idea to set aside $k$ of these things and then choose the rest separately: you’ll end up counting the same collection of things several times, once for each way of ... $\endgroup$ – Brian M. Scott Jun 29 '13 at 4:15
  • $\begingroup$ ... setting aside $k$. In this problem $k$ was $1$, and you counted a string with $k$ $a$’s $k$ times, once for each one that you set aside to be counted separately. $\endgroup$ – Brian M. Scott Jun 29 '13 at 4:15
0
$\begingroup$

You will be double counting many strings. For example, suppose that (out the $n$ ways to place character a), you decide to put it at the first position. The remaining positions don't matter, so you could, for example, make the entire string all a's. That's one string. But according to your strategy, you could also have placed the initial character a at, say, the second position. Since the remaining positions don't matter, it is possible to again make the entire string all a's. Thus, you have double counted.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thx. Your explanation is precise. But I think there is a rule out there that I should follow when counting this kind of permutations. I need to find it out. Otherwise, I would make similar mistake next time without consciousness. $\endgroup$ – Zack Jun 29 '13 at 4:03
  • $\begingroup$ That rule would be the principle of inclusion-exclusion. When you are asked to count how many elements have at least one something, it is often easier to consider the complement. See Wikipedia for more details: en.wikipedia.org/wiki/Principle_of_inclusion-exclusion $\endgroup$ – Adriano Jun 29 '13 at 4:05
0
$\begingroup$

So $n=4$ and there are $4^4=256$ strings. You can either have a permutation of $abcd$, of which there are $4!=24$ or you can have two of one and one each of the others. For that, you have $3$ ways to select the duplicated letter, ${4 \choose 2}=6$ ways to choose the positions for that letter, and $2$ ways to place the other two. So we have $24+3\cdot 6 \cdot 2=60$ successes.

| cite | improve this answer | |
$\endgroup$

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.