Detailed mathematical approach

Problem Summary

Project Euler 172 asks for the number of 18-digit decimal numbers in which no digit appears more than three times. The first digit cannot be 0, so the leading position is the only asymmetric part of the count; after that, the ten digits \(0,1,\dots,9\) are handled uniformly.

The implementations are written around the slightly more general parameters \(L\) for the length and \(R\) for the repetition cap. For this problem, \(L=18\) and \(R=3\).

Mathematical Approach

The key move is to stop thinking about concrete 18-digit strings and instead count how many times each digit is used. Once those multiplicities are fixed, the remaining work is a multinomial count with a correction for leading zero.

The Right State Space: Bounded Digit Counts

Let \(c_d\) denote the number of occurrences of digit \(d\). Every valid number determines a vector

$c=(c_0,c_1,\dots,c_9)$

such that

$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$

For Euler 172 this becomes

$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$

So the problem is really a sum over all bounded compositions of 18 into 10 parts. The recursion in the implementations enumerates exactly these vectors, one digit at a time.

Counting One Multiplicity Vector

Fix one admissible vector \(c\). If leading zeros were allowed, the number of arrangements of the multiset would be the multinomial coefficient

$\frac{L!}{\prod_{d=0}^{9} c_d!}.$

If \(c_0=0\), this is already the correct contribution. If \(c_0 \gt 0\), some arrangements begin with 0 and must be removed. Fixing a zero in the first position leaves \(L-1\) places and the reduced count vector \((c_0-1,c_1,\dots,c_9)\), so the illegal arrangements are

$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$

Therefore the contribution of \(c\) is

$N(c)=\frac{L!}{\prod_{d=0}^{9} c_d!}-\mathbf{1}_{c_0 \gt 0}\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$

After simplifying, the same quantity can be written in a uniform form that also works when \(c_0=0\):

$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$

The full answer is the sum of \(N(c)\) over every admissible digit-count vector.

Worked Example

A small 4-digit example shows exactly why the leading-zero subtraction is necessary. Suppose the digit counts are

$c_0=2,\qquad c_1=1,\qquad c_2=1,$

and all other counts are 0. The multiset is \(\{0,0,1,2\}\), so the total number of permutations is

$\frac{4!}{2!}=12.$

Among them, the illegal ones with leading zero are obtained by fixing one 0 at the front and permuting \(\{0,1,2\}\):

$\frac{3!}{1!}=6.$

Hence the number of valid 4-digit numbers is \(12-6=6\). The compact formula gives the same result:

$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$

This is exactly the same combinatorial correction applied in the 18-digit problem; only the number of admissible count vectors is larger.

The DFS Invariant

When the recursion has already assigned counts to digits \(0,1,\dots,d-1\), it keeps three pieces of state:

$\text{current digit }d,\qquad \text{remaining slots},\qquad \prod_{e=0}^{d-1} c_e!.$

The product of factorials is the important invariant. Once the search reaches digit 10 and the remaining number of slots is 0, that running product has become the full denominator \(\prod_{d=0}^{9} c_d!\), so the leaf contribution can be evaluated in constant time from the formulas above. No actual 18-digit strings are constructed.

How the Code Works

Factorials and Recursive Enumeration

The C++, Python, and Java implementations first precompute factorials up to the required length. They also maintain a 10-entry array of digit counts. The recursive search chooses a count for the current digit from \(0\) up to \(\min(R,\text{remaining})\), stores it, multiplies the running denominator by the corresponding factorial, and moves to the next digit.

One implementation exposes \(L\) and \(R\) as parameters and includes small checkpoint cases such as the 3-digit and 4-digit counts; the other two are fixed directly to the Euler 172 parameters. Mathematically, all three do the same search.

Leaf Evaluation and Leading-Zero Correction

At a valid leaf, the implementation computes the multinomial term \(L!/\prod c_d!\). If at least one zero was used, it also computes the leading-zero term by replacing \(c_0!\) with \((c_0-1)!\) in the denominator, which corresponds to fixing a zero in the first position. The difference of those two integers is added to the global total.

This is why the programs are short: once the correct count-vector formula is known, the implementation is just a bounded DFS together with an \(O(1)\) arithmetic evaluation at each admissible leaf.

Complexity Analysis

Let

$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$

be the number of admissible digit-count vectors. The recursion visits exactly those vectors, plus the corresponding internal nodes, so the running time is \(O(B(L,R))\) up to a constant factor from the fixed set of ten digits.

For Euler 172, this is vastly smaller than the naive \(10^{18}\) search space. Memory usage is \(O(L)\) for the factorial table and \(O(10)\) for the count array and recursion stack. All arithmetic remains exact because every contribution is an integer multinomial count.

Footnotes and References

1. Project Euler problem page: Project Euler 172
2. Multinomial coefficient: Wikipedia - Multinomial theorem
3. Permutations of multisets: Wikipedia - Permutation of a multiset
4. Generating functions: Wikipedia - Generating function