2
$\begingroup$

I have a combinatorics problem that I'm struggling with. Here it is: "How many 5-digit codes have among their digits each of $3,4,5$?"

I do understand the general strategy, where we first see how we can permute $3,4,5$ with the other empty slots ($\frac{5!}{2} = 60$ ways) and then we multiply by $10^2$ (both of the other two slots can have any of the $10$ digits). However now we end up double counting, as some of those other two digits will be $3,4,5$ and will result in duplicating combinations between each other. I am struggling to come up with a formula for excluding these.

$\endgroup$
3
  • $\begingroup$ There are different approaches you could take. Are you familiar with the Inclusion-Exclusion Principle? $\endgroup$ Commented Nov 4, 2020 at 20:23
  • $\begingroup$ I am familiar with it and suspect it is applicable here, however I am not too well-versed in application of this principle besides the general formula and its use for derangements. $\endgroup$ Commented Nov 4, 2020 at 20:32
  • $\begingroup$ Welcome to Math.SE. This tutorial explains how to typeset mathematics on this site. $\endgroup$ Commented Nov 4, 2020 at 21:21

1 Answer 1

1
$\begingroup$

There are a couple of strategies we could employ here.

Method 1: We consider cases depending on how often each digit appears.

Case 1: The digits $3$, $4$, $5$ each appear exactly once.

Choose one of the positions for the $3$, one of the remaining four positions for the $4$, and one of the remaining three positions for the $5$. Then each of the remaining two positions may be filled with one of the remaining $10 - 3 = 7$ digits. Hence, there are

$$5 \cdot 4 \cdot 3 \cdot 7^2$$

such codes.

Case 2: Exactly one of the digits $3$, $4$, $5$ appears twice and each of the others appears exactly once.

Choose which of the digits $3$, $4$, $5$ appears twice. Choose two of the positions for that digit. Choose one of the remaining three positions for the smaller of the two remaining digits from the set $\{3, 4, 5\}$ and one of the remaining two positions for the remaining digit from the set $\{3, 4, 5\}$. Choose which of the remaining seven digits fills the remaining position. There are

$$\binom{3}{1}\binom{5}{2}\cdot 3 \cdot 2 \cdot 7$$

such codes.

Case 3: Exactly two of the digits $3, 4, 5$ appear twice and the other one appears once.

Choose which of the three digits $3, 4, 5$ appears exactly once. Choose which of the five positions that digit fills. Choose two of the remaining four remaining positions for the smaller of the two remaining digits from the set $\{3, 4, 5\}$, then fill the remaining two positions with the remaining digit from the set $\{3, 4, 5\}$. There are

$$\binom{3}{1}\binom{5}{1}\binom{4}{2}$$

such codes.

Case 4: Exactly one of the three digits $3, 4, 5$ appears three times and each of the others appears once. Choose which of the three digits appears three times, then choose three of the five positions for that digit. Choose one of the remaining two positions for the smaller of the remaining digits from the set $\{3, 4, 5\}$, then fill the final position with the other digit. There are

$$\binom{3}{1}\binom{5}{3}\binom{2}{1}$$

such codes.

Total: Since these positions are mutually exclusive and exhaustive, add the above cases.

Method 2: We use the Inclusion-Exclusion Principle.

There are $10^5$ codes. We wish to exclude from these those in which at least one of the digits $3, 4, 5$ is missing.

We choose which of the three digits $3, 4, 5$ to exclude, which leaves nine ways to fill each of the five positions. Thus, we subtract

$$\binom{3}{1}9^5$$

from the total.

However, if we do so, we will have subtracted each case in which two of the digits $3, 4, 5$ are missing twice, once for each way we could have designated one of those digits as the missing digit. We only want to subtract such cases once, so we must add them to the total.

We choose which two of the three digits $3, 4, 5$ to exclude, which leaves us eight ways to fill each of the five positions. Thus, we add

$$\binom{3}{2}8^5$$

to our running total.

However, if we first subtract those cases in which one of the digits $3, 4, 5$ is excluded and then add those cases in which two of the digits $3, 4, 5$ are excluded, we will not have excluded those cases in which all three digits $3, 4, 5$ are excluded at all. This is because we first subtracted them three times, once for each way we could have designated one of those three digits as the excluded digit. We then added these cases three times, once for each of the $\binom{3}{2}$ ways we could have designated two of those three digits as the excluded digits. Thus, we must them from the total.

If all three digits $3, 4, 5$ are excluded, then we have seven choices for each of the five positions. Thus, there are

$$\binom{3}{3}7^5$$

cases in which all the digits $3, 4, 5$ are excluded.

By the Inclusion-Exclusion Principle, there are

$$10^5 - \binom{3}{1}9^5 + \binom{3}{2}8^5 - \binom{3}{3}7^5$$

admissible codes.

As you can verify, the two methods yield the same answer.

$\endgroup$
1
  • 1
    $\begingroup$ Many thanks! That answer all my questions in a very intuitive manner, cheers sir. $\endgroup$ Commented Nov 5, 2020 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .