Detailed mathematical approach

Problem Summary

For each \(k\)-digit integer \(n\), let \(P(n)\) be the number of larger \(k\)-digit integers that can be formed by permuting the digits of \(n\). We want

$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$

where \(\mathcal{D}_k\) is the set of all \(k\)-digit numbers, so leading zeros are forbidden. The key observation is that the exact order of the digits is not the right unit of work. What matters is how many times each digit appears. Once numbers are grouped by digit multiplicities, the whole problem becomes a clean combinatorial sum.

Mathematical Approach

Write the digit-count vector of a number as

$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$

Two \(k\)-digit numbers belong to the same class exactly when they have the same vector \(c\). Every valid number in that class is a permutation of the same multiset of digits, so the contribution of the class depends only on \(c\).

Step 1: Enumerate Digit-Multiplicity Classes

Choosing the vector \(c\) is a stars-and-bars problem: we distribute \(k\) digit slots among the ten digit values \(0,1,\dots,9\). Therefore the number of possible classes is

$\binom{k+9}{9}.$

The implementations do not enumerate actual numbers. They enumerate these count vectors, because one vector summarizes an entire permutation class at once.

Step 2: Count All Rearrangements of One Class

For a fixed vector \(c\), the number of length-\(k\) digit strings obtained by rearranging that multiset is the multinomial count

$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$

This counts every arrangement, including those that begin with \(0\). Such strings are not valid \(k\)-digit integers, so one more correction is needed.

Step 3: Remove the Leading-Zero Arrangements

If \(c_0=0\), every arrangement counted by \(A(c)\) is already valid. If \(c_0>0\), then the arrangements with a leading zero are obtained by fixing one zero in the first position and permuting the remaining \(k-1\) places:

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

Using \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\), this simplifies to

$Z(c)=A(c)\frac{c_0}{k}.$

Hence the number of valid \(k\)-digit integers in the class is

$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$

This formula also works when \(c_0=0\), because then the correction term vanishes automatically.

Step 4: Turn a Class Size into a Contribution to \(S(k)\)

List the valid numbers in one class in increasing order:

$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$

For the \(i\)-th number, the quantity \(P(x_i)\) is exactly the number of later elements in the same sorted list, namely \(V(c)-i\). Summing over the whole class gives

$\sum_{j=1}^{V(c)} P(x_j)=\sum_{i=1}^{V(c)} (V(c)-i)=\frac{V(c)(V(c)-1)}{2}=\binom{V(c)}{2}.$

So each class contributes the number of unordered pairs of distinct valid permutations in that class.

Step 5: Final Summation Formula

Adding the contribution of every digit-count vector yields

$\boxed{S(k)=\sum_{\substack{c_0,\dots,c_9\ge 0\\ c_0+\cdots+c_9=k}} \binom{V(c)}{2},\qquad V(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}\frac{k-c_0}{k}.}$

This is the exact formula implemented by the program: it never compares permutations explicitly, because the entire contribution of one class is available from its multiplicities alone.

Worked Example: \(S(3)=1701\)

The implementations use \(S(3)=1701\) as a small checkpoint. For \(k=3\), the relevant pattern families are

$\begin{aligned} 000&:&&1,\ V=0,\ \binom{V}{2}=0,\\ 00a&:&&9,\ V=1,\ \binom{V}{2}=0,\\ aa0&:&&9,\ V=2,\ \binom{V}{2}=1,\\ aab&:&&72,\ V=3,\ \binom{V}{2}=3,\\ 0ab&:&&36,\ V=4,\ \binom{V}{2}=6,\\ abc&:&&84,\ V=6,\ \binom{V}{2}=15. \end{aligned}$

Here \(a,b,c\) denote nonzero digits, with the obvious distinctness conditions. The class counts are \(9\), \(9\), \(72=9\cdot 8\), \(36=\binom{9}{2}\), and \(84=\binom{9}{3}\). Therefore the total class contributions are \(0\), \(0\), \(9\), \(216\), \(216\), and \(1260\), so

$S(3)=9+216+216+1260=1701.$

How the Code Works

The C++, Python, and Java implementations all follow the same combinatorial plan. First they precompute factorials up to \(k\), because every class evaluation needs the multinomial denominator \(c_0!\cdots c_9!\). Then they run a depth-first enumeration over the ten digit counts: counts are assigned for digits \(0\) through \(8\), and the remaining amount is forced onto digit \(9\), so every admissible vector is visited exactly once.

At each leaf of that search, the implementation computes \(A(c)=k!/\prod c_d!\), converts it to the valid class size \(V(c)=A(c)(k-c_0)/k\), and adds \(\binom{V(c)}{2}\) to the running total. The three implementations differ only in language-specific integer handling; the algorithmic steps are the same in all of them.

Complexity Analysis

There are exactly \(\binom{k+9}{9}\) digit-count vectors, and each one is processed with \(O(10)\) arithmetic operations. The factorial precomputation costs \(O(k)\) time. Therefore the overall running time is

$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$

for the fixed ten-digit alphabet. The memory usage is \(O(k)\) for the factorial table and \(O(10)\) for the count array and recursion state.

Footnotes and References

1. Problem page: Project Euler 862: Larger Digit Permutation
2. Multiset permutations: Wikipedia — Permutations of multisets
3. Stars and bars: Wikipedia — Stars and bars
4. Binomial coefficient: Wikipedia — Binomial coefficient
5. Leading zero in positional notation: Wikipedia — Leading zero