Let $N^{(k)}_{a,b,c}$ be the number of possible unnumbered layouts of the last $k$ columns, given that there are $a$ numbers left to assign in the first row, $b$ in the second row, and $c$ in the third row. Given the rules (at least one number per column), you have the recursion
$$
\begin{eqnarray}
N^{(k)}_{a,b,c}&=&N^{(k-1)}_{a-1,b-1,c-1}+N^{(k-1)}_{a-1,b-1,c}+N^{(k-1)}_{a-1,b,c-1}+N^{(k-1)}_{a,b-1,c-1} + N^{(k-1)}_{a-1,b,c}+N^{(k-1)}_{a,b-1,c}+N^{(k-1)}_{a,b,c-1},
\end{eqnarray}
$$
with the boundary conditions that $N^{(0)}_{0,0,0}=1$ and $N^{(k)}_{a,b,c}=0$ unless all indices are between $0$ and $k$. You want to find $N^{(9)}_{5,5,5}$. The following Python function performs the calculation:
def N(a,b,c,k,cache={(0,0,0,0):1}):
if min(a,b,c)<0 or max(a,b,c)>k:
return 0
if not cache.has_key((a,b,c,k)):
val = N(a-1,b-1,c-1,k-1)
val += N(a-1,b-1,c,k-1) + N(a-1,b,c-1,k-1) + N(a,b-1,c-1,k-1)
val += N(a-1,b,c,k-1) + N(a,b-1,c,k-1) + N(a,b,c-1,k-1)
cache[(a,b,c,k)] = val
return cache[(a,b,c,k)]
N(5,5,5,9)
> 735210
The result is below the upper bound of ${{9}\choose{5}}^3=126^3=2000376$ obtained by allowing all-blank columns, as it should be.
For numbered layouts, the recursion is slightly different, because the number of ways to choose the numbers depends on the column. Here, let $m_k$ be the number of allowed numbers in the $k$-th column from the end: $m_1=11$, $m_9=9$, and $m_k=10$ otherwise. In a column with no blanks, there are ${m_k}\choose{3}$ ways to choose the numbers; with one blank, ${m_k}\choose{2}$; and with two blanks, $m_k$. The recursion is therefore
$$
\begin{eqnarray}
M^{(k)}_{a,b,c}&=&{{m_k}\choose{3}}M^{(k-1)}_{a-1,b-1,c-1}+ {{m_k}\choose{2}}\left(M^{(k-1)}_{a-1,b-1,c}+M^{(k-1)}_{a-1,b,c-1}+M^{(k-1)}_{a,b-1,c-1}\right) \\ && + m_k\left(M^{(k-1)}_{a-1,b,c}+M^{(k-1)}_{a,b-1,c}+M^{(k-1)}_{a,b,c-1}\right).
\end{eqnarray}
$$
Not unexpectedly, the result here is much larger:
$$
M^{(9)}_{5,5,5} = 3669688706217187500.
$$
As a sanity check on this result, one might consider the average branching factor for the $15$ numbers in an average unnumbered layout:
$$
\left(\frac{M^{(9)}_{5,5,5}}{N^{(9)}_{5,5,5}}\right)^{\frac{1}{15}} \approx 7.023.
$$
Since in a typical row (with $m_k=10$) the possible outcomes have average branching factors ${{10}\choose{3}}^{1/3}\approx 4.93$, ${{10}\choose{2}}^{1/2}\approx 6.71$, and $10$, this seems very reasonable.
Note that we can also enumerate the possible unnumbered layouts in an entirely different way, using inclusion-exclusion. The basic idea is to count all the ways of placing $5$ numbers in each of the three rows, then remove the cases with an all-blank column, then add back in the cases with two all-blank columns, and so on:
$$
\begin{eqnarray}
N^{(9)}_{5,5,5} &=& {{9}\choose{5}}^3 - {{9}\choose{1}}{{8}\choose{5}}^3 + {{9}\choose{2}}{{7}\choose{5}}^3 - {{9}\choose{3}}{{6}\choose{5}}^3 + {{9}\choose{4}} \\
&=& 735210,
\end{eqnarray}
$$
as above. This is an elegant solution to the unnumbered case, but I do not see a way to extend it to the numbered layouts.
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
We can have two $5$ and one from $\{4,8\}$; gives $2\cdot3=6$ triples.
We can have one $5$ and two from $\{2,4,6,8\}$. We can chose two different ones in ${4\choose2}=6$ ways, and this gives $6\cdot3!=36$ triples of three different digits. When we choose the same even number two times we obtain $4\cdot3=12$ more triples.
We can have one $5$, one from $\{4,8\}$ and one from $\{1,3,7,9\}$. This gives $2\cdot4\cdot3!=48$ triples.
In all there appear $6+36+12+48=102$ admissible triples.