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).
Best Answer
This claim is true only if all six digits are distinct. However, $434152$ is a six-digit number with three even and three odd digits.
Method 1: We add the number of six-digit numbers whose leading digit is odd to those whose leading digit is even.
If the leading digit is odd, two of the remaining five digits are odd. We choose their positions in $\binom{5}{2}$ ways. Each of the three odd digits can be filled in $5$ ways. Each of the three even digits can be filled in $5$ ways. Hence, there are $$\binom{5}{2} \cdot 5^3 \cdot 5^3 = \binom{5}{2}5^6$$ six-digit natural numbers whose leading digit is odd.
If the leading digit is even, it cannot be zero, so it can be filled in $4$ ways. Two of the remaining five digits are even. Their positions can be selected in $\binom{5}{2}$ ways. Each of those positions can be filled in $5$ ways, as can each of the three positions that are filled with odd digits. Hence, there are $$\binom{5}{2} 4 \cdot 5^2 \cdot 5^3 = \binom{5}{2} \cdot 4 \cdot 5^5$$
Hence, the total number of six-digit natural numbers with three even and three odd digits is $$\binom{5}{2}(5^6 + 4 \cdot 5^5) = 5^5\binom{5}{2}(4 + 4) = 9 \cdot 5^5\binom{5}{2} = 90 \cdot 5^5$$
Method 2: We count six-digit sequences with three even and three odd digits, then multiply by $9/10$ to account for the fact that the leading digit cannot be zero.
There are $\binom{6}{3}$ ways to choose the positions of the even digits. The three even digits can each be filled in $5$ ways. The three odd digits can each be filled in $5$ ways. Hence, the number of permissible sequences is $$\frac{9}{10} \binom{6}{3} \cdot 5^3 \cdot 5^3 = \frac{9}{10} \cdot 20 \cdot 5^6 = 9 \cdot 2 \cdot 5 \cdot 5^5 = 90 \cdot 5^5$$