Solution

Answer: 227485267000992000

We must count 18-digit numbers in which no digit appears more than three times.

Let the digits be $0,1,\dots,9$.

We seek the number of length-18 strings:

first digit nonzero,
each digit used at most 3 times.

This is a constrained multinomial counting problem.

1. Mathematical analysis

Suppose digit $i$ occurs $a_i$ times, where

$$0 \le a_i \le 3, \qquad \sum_{i=0}^9 a_i = 18.$$

If the counts $(a_0,\dots,a_9)$ are fixed, then:

total arrangements of the 18 digits:

$$\frac{18!}{a_0!a_1!\cdots a_9!}$$

but some begin with $0$, which are forbidden.

Counting arrangements with no leading zero

If $a_0=0$, then all arrangements are valid.

If $a_0>0$, count valid arrangements by fixing a nonzero digit first.

A cleaner method is:

$$\text{valid} = \frac{18!}{\prod a_i!} - \frac{17!}{(a_0-1)!\prod_{i=1}^9 a_i!}.$$

Factor the second term:

$$\frac{17!}{(a_0-1)!\prod_{i=1}^9 a_i!} = \frac{17!a_0}{\prod a_i!}.$$

Hence

$$\text{valid} = \frac{17!(18-a_0)}{\prod a_i!}.$$

Since there are 9 nonzero digits, $18-a_0 = a_1+\cdots+a_9$, exactly as expected.

Therefore the total answer is

$$\boxed{ \sum_{\substack{a_0+\cdots+a_9=18\0\le a_i\le3}} \frac{17!(18-a_0)}{a_0!a_1!\cdots a_9!} }$$

This is finite because each $a_i\in{0,1,2,3}$.

Generating-function viewpoint

The denominator structure suggests generating functions.

For digits $1$–$9$, define

$$f(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}.$$

For the leading-zero correction we need

$$g(x)=1+\frac{x}{1!}+\frac{x^2}{2!}.$$

Why? Because multiplying by $a_0$ converts

$$\frac{a_0}{a_0!}=\frac1{(a_0-1)!}.$$

Then

$$\sum \frac{18-a_0}{\prod a_i!} = 9 ,[x^{17}], g(x)f(x)^9.$$

Finally,

$$N = 17!\cdot 9 \cdot [x^{17}],g(x)f(x)^9.$$

This is elegant, but for implementation a direct enumeration of all count-vectors is simplest.

2. Python implementation

from math import factorial
from itertools import product

# Precompute factorials
fact = [factorial(i) for i in range(19)]

total = 0

# Each digit count can be 0,1,2,3
# Enumerate all 4^10 possibilities
for counts in product(range(4), repeat=10):

    # Total digits must be 18
    if sum(counts) != 18:
        continue

    a0 = counts[0]

    # Compute denominator product a0! a1! ... a9!
    denom = 1
    for c in counts:
        denom *= fact[c]

    # Number of valid 18-digit numbers for this count pattern
    ways = fact[17] * (18 - a0) // denom

    total += ways

print(total)

3. Code walkthrough

Imports

from math import factorial
from itertools import product

factorial computes factorials.
product(range(4), repeat=10) generates all 10-tuples where each entry is $0,1,2,3$.

Precompute factorials

fact = [factorial(i) for i in range(19)]

We need factorials up to $18!$.

Enumerating digit multiplicities

for counts in product(range(4), repeat=10):

Each tuple represents:

$$(a_0,a_1,\dots,a_9)$$

with each digit used at most three times.

Enforcing total length 18

if sum(counts) != 18:
    continue

Only keep tuples whose counts sum to 18.

Multinomial denominator

denom = 1
for c in counts:
    denom *= fact[c]

This computes

$$a_0!a_1!\cdots a_9!$$

Valid arrangements

ways = fact[17] * (18 - a0) // denom

This is exactly

$$\frac{17!(18-a_0)}{\prod a_i!}$$

derived earlier.

Accumulate total

total += ways

Summing over all allowable digit-count vectors gives the final answer.

4. Small sanity checks

For a smaller toy version:

2-digit numbers,
no digit repeated more than once,

the count should be:

first digit: 9 choices,
second digit: 9 remaining choices,

so $9\times 9=81$.

The same multinomial method reproduces this exactly.

5. Final verification

The unrestricted number of 18-digit numbers is

$$9\times10^{17}.$$

Our restriction (“no digit more than three times”) removes many numbers but still leaves a large proportion, so the answer should still be on the order of $10^{17}$.

The computed value is:

$$227485267000992000$$

which is indeed of the correct magnitude.

Answer: 227485267000992000

Project Euler Problem 172