In this answer I presume that all digits $1,2,5,6$ must be present in the number.
There are $4!=24$ such numbers.
We can index them with $i=1,\dots,24$
and write each of them as $$n_{i}=a_{i}+10b_{i}+100c_{i}+1000d_{i}$$
where $\left\{ a_{i},b_{i},c_{i},d_{i}\right\}=\{1,2,5,6\} $
Then $$\sum_{i=1}^{24}n_{i}=\sum_{i=1}^{24}a_{i}+10\sum_{i=1}^{24}b_{i}+100\sum_{i=1}^{24}c_{i}+1000\sum_{i=1}^{24}d_{i}$$
$\left\{ i\mid a_{i}=1\right\} $, $\left\{ i\mid a_{i}=2\right\} $,
$\left\{ i\mid a_{i}=5\right\} $ and $\left\{ i\mid a_{i}=6\right\} $
have equal cardinality $\frac{24}4=6$ so: $$\sum_{i=1}^{24}a_{i}=6.1+6.2+6.5+6.6=6(1+2+5+6)=84$$
This can also be applied for $b,c$ and $d$ and finally we find:
$$\sum_{i=1}^{24}n_{i}=84+10.84+100.84+1000.84=1111.84=93324$$
Does this really answers your question? If not, then please let me know.
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
Well, There are $900$ three digit numbers. So if we find out how many $3$ digit number have the digits add up to $9$ or less we just subtract those.
Now consider this:
Suppose the three digit number is $abc$.
Suppose you are given $9$ stars and $3$ bars and you want to represent you number this way.
From left to right: Put down $a$ stars to represent the first digit. But down $1$ bar to represent a place holder. Put down $b$ more stars to represent the second digit. Put down a second bar to represent a $2$nd place holder. Put down $c$ stars. Put a bar as the $3$rd place holder. You have $a+b+c \le 9$ so you may have some stars remaining. Put them down.
Every three digit number where the sum is $9$ or less can be represented by a unique combination of stars and bars and each combination represents a unique three digit number where the sums of the digits is $9$ or less.
THis is a line of $12$ items and you must choose $3$ positions for where the bars go.
So there are ${12\choose 3}$ such numbers.
But notice we can't have the first digit be $0$. That is, we can't start with a bar.
So given we start with a star we have $11$ more items and we must choose $3$ position for where the bars go.
So there are ${11 \choose 3}$ such number that have three digits, the first digit is not zero, and the digits add to $9$ or less.
SO there are $900-{11\choose 3}$ three digit numbers where the digits add up to $10$ or more.