Counting problem: 5-character ASCII strings containing at least one @

[Nick O]

Homework Statement

How many strings of five ASCII characters contain the character @ ("at" sign) at least once? [Note: there are 128 different ASCII characters.]

Homework Equations

The rule of product and inclusion-exclusion principle are relevant.

The Attempt at a Solution

The correct solution is as follows:

The number of 5-character ASCII strings is 128^5. The number of 5-character ASCII strings not including at least one @ is 127^5. By the inclusion-exclusion principle, the number of 5-character ASCII strings including at least one @ is equal to 128^5 - 127^5.

I have no problem with that. What bothers me is that I can't find out where I go wrong with the following "solution", which yields a different answer.

Incorrect solution:

At least one of the five characters is an @. There are 5 ways to place this character, because the string has a length of 5. The remaining characters may or may not be an @ symbol. Each of the four remaining characters can be chosen in 128 different ways.

By the rule of product, there are 5 * 128 * 128 * 128 * 128 = 5*128^4 such strings.

Query:

128^5 - 127^5 is a much larger number than 5*128^4. Which assumption in my incorrect solution is unjustified?

 

[Dick]

Homework Statement

How many strings of five ASCII characters contain the character @ ("at" sign) at least once? [Note: there are 128 different ASCII characters.]

Homework Equations

The rule of product and inclusion-exclusion principle are relevant.

The Attempt at a Solution

The correct solution is as follows:

The number of 5-character ASCII strings is 128^5. The number of 5-character ASCII strings not including at least one @ is 127^5. By the inclusion-exclusion principle, the number of 5-character ASCII strings including at least one @ is equal to 128^5 - 127^5.

I have no problem with that. What bothers me is that I can't find out where I go wrong with the following "solution", which yields a different answer.

Incorrect solution:

At least one of the five characters is an @. There are 5 ways to place this character, because the string has a length of 5. The remaining characters may or may not be an @ symbol. Each of the four remaining characters can be chosen in 128 different ways.

By the rule of product, there are 5 * 128 * 128 * 128 * 128 = 5*128^4 such strings.

Query:

128^5 - 127^5 is a much larger number than 5*128^4. Which assumption in my incorrect solution is unjustified?

No, 5*128^4 is larger than 128^5-127^5. It's because you are overcounting strings that contain more than one @.

 

[xiavatar]

In the incorrect solution your over counting.

Example:
Suppose we fix the first element with @.
then our string is of the form @0000. where the 0 can be any other ASCII character. But note we have @@000 as being one such character. But if we fix the second character so we have the set of strings of the form 0@000. Clearly if we let the first character be @, then we again have a string of the form @@000.

 

[Nick O]

Sorry, I somehow got that inequality backwards when translating it to a forum post.

That makes perfect sense. The devil is in the detail, particularly where combinations are involved. Thank you both!