Few Repeated Digits

How many $18$-digit numbers $n$ (without leading zeros) are there such that no digit occurs more than three times in $n$?

This is a rather complex combinatorics problem. We’ll go step by step.

Given that we’re looking for $18$-digit numbers where no digit repeats more than $3$ times, we first need to analyze the digits we’re dealing with from $0-9$ (total $10$ digits).

1) We cannot have all $18$ digits be distinct (there are only $10$ to choose from).
2) We cannot have one or more digits repeated $4$ times, and others only once (as that would require more than $10$ total choices)

So, we need to look at combinations of duplicate/repeated digits. The following combinations of digit repetitions exist such that they sum up to $18: (3, 3, 3, 3, 3, 3)$, $(3, 3, 3, 3, 2, 2, 2)$, $(3, 3, 3, 2, 2, 2, 2, 1)$, $(3, 3, 2, 2, 2, 2, 2, 2)$, and $(3, 2, 2, 2, 2, 2, 2, 2, 1)$.

**Case 1: $(3, 3, 3, 3, 3, 3)$**

Choose $6$ digits from $10$ in $\binom{10}{6}$ ways. Each of these $6$ digits will appear $3$ times thus fixing all $18$ digits in place for a total of $18!/(3!)^6$ arrangements.

**Cases 2 to 5: $(3, 3, 3, 3, 2, 2, 2)$, $(3, 3, 3, 2, 2, 2, 2, 1)$, $(3, 3, 2, 2, 2, 2, 2, 2)$, and $(3, 2, 2, 2, 2, 2, 2, 2, 1)$**

In each case:

– Choose digits that will appear $3$ times.
– Choose digits that will appear $2$ times.
– Choose digits that will appear $1$ time.
– Arrange them.

e.g., in the second case $(3, 3, 3, 3, 2, 2, 2)$, we have to choose which $4$ digits will be repeated $3$ times, which $3$ digits will be repeated $2$ times out of the remaining $6$ digits. Then arrange them in $18!/(3!)^4 * (2!)^3$ ways.

But in every case except for the first, we’re going to have to discard the numbers that start with $0$ (since they’re not $18$-digit numbers). For the first case, none of the numbers will start with zero since we’re repeating $6$ digits $3$ times each.

For the rest of the cases, we have to discard those which start with $0$. For example, in the second case, we can choose the $4$ digits that are repeated thrice, $3$ digits that are repeated twice and arrange them. However the digit $0$ can take any of the $17$ spots other than the $1^{st}$ position, resulting in $17!/((3!)^4 * (2!)^3)$ arrangements starting with $0$.

Sum them all, and that gives the final count.

More Answers: