Htykuut

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 5times 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 4times (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?

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).

I will assume that the question means that no digit appears more than three times. As Austin Mohr points out, the question is badly phrased.

Since the leading digit cannot be zero, there are $9 cdot 10^5 = 900,000$ six digit positive integers. Like Soke, I will exclude those in which a digit appears four or more times.

We consider cases.

Case 1: The same digit is used six times.

Since the leading digit cannot be zero, there are $9$ of these. They are $$111 111, 222 222, 333 333, 444 444, 555 555, 666 666, 777777, 888 888, 999 999$$

Case 2: One digit is used five times, while a different digit is used once.

There are two subcases.

Subcase 1: The leading digit is repeated.

Since the leading digit cannot be zero, there are nine ways to select the leading digit. We must select four of the remaining five places to place the other occurrences of the leading digit. We then have nine choices for the other digit since we can now use zero.

$$9 cdot binom{5}{4} cdot 9 = 405$$

Subcase 2: The leading digit is not repeated.

We still have nine ways of selecting the leading digit. That leaves us with nine ways to choose the repeated digit that fills the remaining five places.

$$9 cdot 9 = 81$$

Case 3: One digit is used four times, while a different digit is used twice.

Subcase 1: The leading digit appears four times.

We have nine ways of selecting the leading digit. We have $binom{5}{3}$ ways of choosing the other three positions in which it appears. We have nine ways of choosing the digit that fills the two open positions.
$$9 cdot binom{5}{3} cdot 9 = 810$$

Subcase 2: The leading digit appears twice.

We have nine ways of selecting the leading digit and $binom{5}{1}$ ways of choosing the other position in which it appears. We have nine choices for choosing the repeated digit that fills the four open positions.
$$9 cdot binom{5}{1} cdot 9 = 405$$

Case 4: One digit is used four times, while two other digits are used once each.

Subcase 1: The leading digit is repeated.

We have nine ways of choosing the leading digit and $binom{5}{3}$ ways of choosing the other three positions in which it appears. We have nine choices for the leftmost open position and eight choices for the remaining position.
$$9 cdot binom{5}{3} cdot 9 cdot 8 = 6480$$

Subcase 2: The leading digit is not repeated.

We have nine ways of choosing the leading digit. We have nine ways of choosing the repeated digit and $binom{5}{4}$ ways of selecting four of the five open positions in which to place it. We have eight ways of filling the remaining open position.
$$9 cdot 9 cdot binom{5}{4} cdot 8 = 3240$$

That gives a total of
$$9 + 405 + 81 + 810 + 405 + 6480 + 3240 = 11,430$$
excluded cases.

Hence, there are
$$900,000 - 11,430 = 888,570$$
six-digit positive integers in which no digit appears more than three times.

This is neatly handled using exponential generating functions. Assuming first that we are allowed to have 0 as the first digit (e.g. we're talking about license plates or lock combinations): each of $10$ digits can occur up to $3$ times, and the order of the symbols matters. The answer is
$$left[frac{x^6}{6!}right]
left(1+x+frac{x^2}{2!}+frac{x^3}{3!}right)^{10} = 987,300.$$

If you want to exclude leading zeroes, you can subtract those off. You count them using the same technique. If you force the first digit to be zero, we have five remaining digits to select; there can be at most two remaining zeroes, and up to three of all other digits. So the count is
$$left[frac{x^5}{5!}right]
left(1+x+frac{x^2}{2!}+frac{x^3}{3!}right)^9left(1+x+frac{x^2}{2!}right) = 98,730.$$
Thus, the number of 6-digit numbers, not starting with zero, having no more than 3 repeated digits, is
$$987,300 - 98,730 = 888,570.$$