[Math] How many 6 digit numbers are possible with no digit appearing more than thrice

combinationscombinatoricspermutations

How many 6 digit numbers are possible with at most three digits repeated?

My attempt:

The possibilities are:

A)(3,2,1) One set of three repeated digit, another set of two repeated digit and another digit (Like, 353325, 126161)

B)(3,1,1,1) One set of three repeated digit, and three different digits.(Like 446394, 888764)

C)(2,2,1,1) Two sets of two repeated digits and two different digits (Like, 363615, 445598)

D)(2,2,2) Three sets of two repeated digits (Like, 223344, 547547)

E)(2,1,1,1,1,1) One set of two repeated digit and four different digits (Like 317653, 770986)

F)(1,1,1,1,1,1) Six Different digits (like 457326, 912568)

G)(3,3) Two pairs of three repeated digits.
Let's try to calculate each possibilities separately.

F) is the easiest calculate.

Let us try to workout Case E)

Let's divide the case into two parts:

Case E(1) Zero is not one of the digit

We can choose any $5$ numbers form $9$ numbers $(1,2,3,\cdot, 9)$ in $\binom{9}{5}$ ways , the digit which one is repeated can be chosen in 5 ways, and you can permute the digits in $\frac{6!}{2!}$ ways. The total number of ways$=\binom{9}{5}\times 5\times \frac{6!}{2!} $

Case E(2) Zero is one of the digit.

Case E(2)(a) Zero is the repeated digit We need to choose four other numbers which can be done in $\binom{9}{4}$ ways, the digits can be permuted in $\frac{6!}{2!}$ ways, but we need to exclude the once which starts with zero ($5!$ many). The total number of ways =$=\binom{9}{4}\times (\frac{6!}{2!} -5!)$.

Case E(2)(b) Zero is not the repeated digit We need to choose four other numbers which can be done in $\binom{9}{4}$ ways, the repeated digit can be chosen in 4 ways, the digits can be permuted in $\frac{6!}{2!}$ ways, but we need to exclude the once which starts with zero ($5!$ many). The total number of ways =$=\binom{9}{4}\times 4\times (\frac{6!}{2!} -5!)$.

Before, proceeding to workout the other cases, I want to know

  1. Is my attempt correct?
  2. If it is correct, it is too lengthy, is there any other way to solve this?

Best Answer

A start: Here it is easier to count the complementary number: the number of 6 digit positive integers with four or more of one digit repeated.

This reduces to only four cases: (4, 1, 1), (4, 2), (5, 1), (6).

The rest:

(6) is simply $9$. These are $(111111, 222222, \dots, 999999)$.

(5, 1) is a little trickier. First there are $9 * 8$ ways to choose two distinct digits that aren't either zero and assign each to $5$ or $1$. Then there are ${6 \choose 1}$ ways to permute the order.

Now there's case where one is zero. There are $9$ ways to choose the other digit (it can't be zero or else the entire number is zero). For each combination, there are similarly ${6 \choose 1}$ ways to permute the order. In particular, there are ${6 \choose 1}$ ways to permute five zeros and one of the other digit and another ${6 \choose 1}$ ways to permute one zero and five of the other digit. Exactly half of these are valid by symmetry.

Indeed, the bijection that flips each digit demonstrates this property: if we map, e.g., $aaaa0a \mapsto 0000a0$, exactly one of these will be valid for each pair. In this case, we have $a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$ as valid strings. In total this gives

$$(9 * 8 + 9) * {6 \choose 1} = 486.$$

(4, 2) is similar. There are $9*8$ ways to initially choose and then ${6 \choose 2}$ ways to permute the order.

If one is zero, again there are $9$ ways to choose the other digit and for each combination the number of ways to permute the order is ${6 \choose 2}$. This is

$$(9 * 8 + 9) {6 \choose 2} = 1215.$$

Finally (4, 1, 1). There are $9 * {8 \choose 2}$ ways to choose non-zero digits and assign them to a frequency. There are then $6! / 4!$ permutations. This gives

$$9 * {8 \choose 2} * 6! / 4! = 7560.$$

Now choose a triplet of unique digits $(a, b, c)$ where one is zero. There are ${9 \choose 2}$ ways of doing so. Now, consider the ${6 \choose 4}$ ways to make a string from four $r$'s (r for repeated) and two $s$'s (s for single). If we are given $rsrrrs$, for example, there are now $3!$ ways to choose one of the digits as the repeated and the other two each into one $s$ spot. Of these, two are invalid, namely when we choose the repeated digit to be zero. You can convince yourself this holds for any string. Thus, this gives

$$4{9 \choose 2}{6 \choose 4} = 2160$$

The grand total is $11430$. There are $900000$ six digit numbers in total, so the desired number is $\boxed{888570}$.

Verified solution on computer in Python:

def get_frequencies(cycle):
    result = 0
    for num in range(10**5, 10**6):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        digit_cycle = sorted([x for x in digit_freq if x != 0], reverse=True)
        if digit_cycle == cycle:
            result += 1
    return result

def get_digits(num):
    r = []
    while num > 0:
        r.append(num % 10)
        num /= 10
    return r

Running with the following main function:

def main():
    print get_frequencies([6], 6)
    print get_frequencies([5, 1], 6)
    print get_frequencies([4, 2], 6)
    print get_frequencies([4, 1, 1], 6)

Outputs the following lines:

9
486
1215
9720

Or, more directly, we can use this program:

def get_frequency_atmost(max_freq, n):
    result = 0
    for num in range(10**(n-1), 10**n):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        if max(digit_freq) > max_freq:
            result += 1
    return 10**n - 10**(n-1) - result

which prints $888570$ on input get_frequency_atmost(3, 6).

Related Question