1
$\begingroup$

I've been practising some combinatorics questions but am finding this one a bit difficult.

I recognise that we can split the question into 2 i.e.

  • Find how many strings have three 3's
  • Find how many strings have exactly 2 digits
  • Add the totals together

My initial approach for the first part was to essentially remove 3 characters from the string (these represent the three 3's) and then remove the digit 3 from the selectable digits.

I'm using the formula $\binom{n + k -1}{k - 1}$ for this so $\binom{5 + 9 - 1}{9 - 1} = 1287$ but I feel like this is the incorrect approach.

For the second part, I believe we can just do $$\binom {10}{2} = 45$$

If these totals were correct, I would expect the final total to be $1287 + 45 = 1332$ but again I feel like my calculation for the first part is incorrect.

$\endgroup$
1
  • $\begingroup$ Compensatory upvote. $\endgroup$ – Brian Tung May 30 '20 at 4:08
2
$\begingroup$

Strings of $8$ digits with exactly $3\ 3$s are ${8 \choose 3}9^5$ because you choose the places for the $3$s and then the rest can be any digit.

Strings with exactly two digits are ${10 \choose 2}(2^8-2)$ because you choose the two digits, then each position has to be one of the two, but you can't allow all of them the be the same.

Now you have counted the ones with three $3$s and five of something else twice, so subtract them once and the result is

$${8 \choose 3}9^5+{10 \choose 2}(2^8-2)-{8 \choose 3}9$$

$\endgroup$
4
  • $\begingroup$ I don't understand the part where you say we have counted the ones with three 3's and five of something else twice. Wouldn't that mean we just change the original (8 choose 3) * 9^5 to (8 choose 3) * 9^4 $\endgroup$ – Kermitty May 30 '20 at 4:05
  • $\begingroup$ @Kermitty: No. Let's suppose we consider just those numbers that have the three $3$'s at the beginning. There are $9^5$ five-digit sequences that can fill the remaining positions and leave the whole sequence containing exactly three $3$'s. However, of those $9^5$ five-digit sequences, exactly $9$ of them contain just one digit repeated five times, and therefore qualify under the second condition. Those must be subtracted out to keep from recounting them, leaving $9^5-9$. This must be repeated for each of the $C(8, 3)$ ways to pick three positions of the $3$'s, yielding the final result. $\endgroup$ – Brian Tung May 30 '20 at 4:07
  • $\begingroup$ I see what you mean thanks for clarifying this! $\endgroup$ – Kermitty May 30 '20 at 4:10
  • $\begingroup$ No. Consider $33311111$. It has exactly $3\ 3$s and only two digits so it gets counted twice. The $8 \choose 3$ picked where the $3$s go. You can't do $9^4$ for the rest because they each have $9$ choices as long as they don't all choose the same one. Look up inclusion-exclusion principle. $\endgroup$ – Ross Millikan May 30 '20 at 4:12

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.