5
$\begingroup$

I'm given the question: "How many strings of five ASCII characters contain the character @ (“at” sign) at least once?"

Note: There are 128 different ASCII characters.

I realized I'd have to use rule of product and sum on this one right away. I approached it by figuring out 5 cases and summing them to get the answer.

Case I:

@ is contained once in the string

I have to pick the position of @ which can be done in 5 ways. Then I have to pick the remaining 4 characters which can be done in $127^4$ ways.

$5 * 127^4$ ways to do this case

Case II:

I have to pick the position of the first @ (5 ways to do that) then the position of the second @ (4 ways to do that) then $127^3$ ways to pick the remaining characters from the string. $5*4*127^3$ ways to do this step

Case III:

I have to pick the position of the first second and third @. Then I have to pick the remaining $2$ characters. $5*4*3*127^2$ ways to do this step.

Case IV:

I have to pick the position of first,second,third, and fourth @. Then I have to pick the last character. $5*4*3*2*127$ ways to complete this step.

Case V:

The whole string is @. Only one way to do this step.

I summed all my cases and the result was $1,342,673,846$ the back of the book gave the answer $1,321,368,961$. Where did I go wrong?

$\endgroup$
  • $\begingroup$ You'll probably need to define "ASCII characters," since this is not a standard mathematical term, so many answerers here might not know what it is. Are there really 127 ASCII characters? $\endgroup$ – Thomas Andrews Nov 4 '14 at 23:42
  • $\begingroup$ I'll edit my answer. However, I put 127 because if I used 128 that includes the possiblity of selecting "@" character again. $\endgroup$ – Dunka Nov 4 '14 at 23:43
3
$\begingroup$

In your cases $II, III, IV$ you have overcounted because swapping the $@$ signs results in the same string. So in case $II$, instead of $5 \cdot 4$ ways to choose where the $@$ signs are, there are $5 \choose 2$ The fact that you are close supports that there are $128$ total ASCII characters

Less work is to compute how many total strings there are and subtract the ones with no $@$. $128^5-127^5=1,321,368,961$

$\endgroup$
  • $\begingroup$ Does your method use the principle of inclusion-exclusion or subtraction rule? What's the name of the rule you used to get your answer(It makes sense to me intuitively but I'd like to understand the rules it uses to be true) $\endgroup$ – Dunka Nov 4 '14 at 23:48
  • $\begingroup$ @Darcy: I would say it uses the subtraction rule. Often it is easier to count too many of something, then subtract the ones you don't want. In a sense, we have two cases instead of five and less to think about for each case. $\endgroup$ – Ross Millikan Nov 4 '14 at 23:52
2
$\begingroup$

The simplest way to do this problem is to compute the number of strings $128^5$, and the number of strings with no @ character, $127^5$. So the total is $128^5-127^5$.

But $5\cdot 4$ is not the number of ways to pick two positions for the @ character, since it counts selecting position $1$ then $2$ and picking position $2$ then $1$. So it should be $\frac{5\cdot 4}{2\cdot 1}=\binom{5}2$, and the result you'll get is really going to be the binomial formula applied to $(127+1)^{5}-127^5$, or:

$$\binom{5}{1}127^4 + \binom{5}{2}127^3+\binom{5}{3}127^2 + \binom{5}4127^1+\binom{5}{5}$$

$\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.