4
$\begingroup$

Suppose that A is a set of 8 (distinct) symbols and consider strings (i.e. sequences) over A.

How can I calculate the number of strings of length 5 which at least one symbol occurs two or more times. I started by calculating the total number of strings of length 5 by doing $8^5$ ( since we have 8 choices for each number) and then I subtracted the amount of strings of length 5 that do not have any repetition ($ 8\times 7\times 6\times 5 \times 4$) and I got the wrong answer. I think this is because my logic is wrong. Can someone help me?

$\endgroup$
  • 2
    $\begingroup$ Your logic is slightly wrong because you are still counting strings where one symbol occurs five times and strings where one symbol occurs four times and another symbol occurs once. Subtract those off and you should reach the right answer. $\endgroup$ – Robert Shore Apr 10 at 22:56
  • 2
    $\begingroup$ @Robert the string AAAAA satisfies the condition that there is at least one character (A) which occurs at least twice (five times). The answer looks correct to me for the question in the title. The question in the body on the other hand... yes I agree. So, @ Eden, which question did you actually mean to ask? Do you recognize that they are different questions? $\endgroup$ – JMoravitz Apr 10 at 22:59
  • 1
    $\begingroup$ @Robert I hadn't read the question in the body initially, only the title and the attempt. I had since edited my comment. $\endgroup$ – JMoravitz Apr 10 at 23:03
  • $\begingroup$ @JMoravitz I edited the body because there was an error in the wording. The title is the correct question. Would you be able to explain to me how to solve it? $\endgroup$ – Eden Ovadia Apr 10 at 23:51
  • 2
    $\begingroup$ Why do you think you have the wrong answer? Do you have an answer to compare to? What is that answer? Again, you appear to have the correct answer to the question as currently written $\endgroup$ – JMoravitz Apr 11 at 0:43
0
$\begingroup$

Ok so it turns out my answer was correct and my professor was mistaken. The answer is 26048. The way I got to this number is explained in my question.

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