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\).
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.
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.
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.
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.
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.
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.
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.
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.
Bei Project Euler 172 soll die Anzahl der 18-stelligen Dezimalzahlen bestimmt werden, in denen keine Ziffer öfter als dreimal vorkommt. Die erste Stelle darf nicht 0 sein; genau diese Führungsstelle erzeugt die einzige Asymmetrie, während die Ziffern \(0,1,\dots,9\) ansonsten völlig gleichbehandelt werden.
Die Implementierungen sind leicht allgemeiner formuliert und verwenden \(L\) für die Länge und \(R\) für die maximale Wiederholungszahl. Im eigentlichen Problem gilt \(L=18\) und \(R=3\).
Der entscheidende Gedanke ist, nicht konkrete 18-stellige Zahlen zu erzeugen, sondern nur zu zählen, wie oft jede Ziffer verwendet wird. Sind diese Häufigkeiten festgelegt, bleibt nur noch eine Multimengen-Permutation mit einer Korrektur für führende Nullen.
Sei \(c_d\) die Anzahl der Vorkommen der Ziffer \(d\). Jede gültige Zahl liefert dann einen Vektor
$$c=(c_0,c_1,\dots,c_9)$$
mit
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$
Für Euler 172 bedeutet das konkret
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$
Damit reduziert sich das Problem auf eine Summe über alle beschränkten Zerlegungen von 18 in 10 Teile. Genau diese Vektoren erzeugt die Rekursion in den Implementierungen, Ziffer für Ziffer.
Fixiere einen zulässigen Vektor \(c\). Wenn führende Nullen erlaubt wären, dann wäre die Anzahl der Anordnungen der Multimenge gleich dem Multinomialkoeffizienten
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
Falls \(c_0=0\), ist das bereits der korrekte Beitrag. Falls \(c_0 \gt 0\), müssen die Anordnungen mit führender 0 entfernt werden. Setzt man eine 0 an die erste Stelle fest, bleiben \(L-1\) Positionen und der reduzierte Vektor \((c_0-1,c_1,\dots,c_9)\). Die ungültigen Fälle sind also
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
Der Beitrag von \(c\) ist damit
$$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!}.$$
Nach einer Vereinfachung erhält man eine einheitliche Form, die sogar für \(c_0=0\) funktioniert:
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
Die gesuchte Gesamtzahl ist die Summe von \(N(c)\) über alle zulässigen Ziffernvektoren.
Ein kleines 4-stelliges Beispiel zeigt unmittelbar, warum die Korrektur für führende Nullen nötig ist. Angenommen, die Ziffernanzahlen seien
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
während alle übrigen Ziffern 0-mal vorkommen. Die Multimenge ist also \(\{0,0,1,2\}\), und die Gesamtzahl aller Permutationen beträgt
$$\frac{4!}{2!}=12.$$
Davon beginnen genau die ungültigen Anordnungen mit 0, bei denen vorne eine 0 festgehalten und \(\{0,1,2\}\) permutiert wird:
$$\frac{3!}{1!}=6.$$
Somit bleiben \(12-6=6\) gültige 4-stellige Zahlen. Die kompakte Formel liefert denselben Wert:
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
Genau dieselbe Korrektur wird im 18-stelligen Problem für jeden zulässigen Häufigkeitsvektor durchgeführt.
Wenn die Rekursion bereits Häufigkeiten für die Ziffern \(0,1,\dots,d-1\) festgelegt hat, speichert sie drei Dinge:
$$\text{aktuelle Ziffer }d,\qquad \text{verbleibende Plätze},\qquad \prod_{e=0}^{d-1} c_e!.$$
Gerade dieses laufende Fakultätsprodukt ist die zentrale Invariante. Sobald die Suche die Ziffer 10 erreicht und keine Plätze mehr offen sind, ist daraus der vollständige Nenner \(\prod_{d=0}^{9} c_d!\) geworden, und der Blattbeitrag lässt sich in konstanter Zeit berechnen. Es werden also niemals konkrete 18-stellige Zeichenketten erzeugt.
Die C++-, Python- und Java-Implementierungen berechnen zuerst die Fakultäten bis zur benötigten Länge vor. Zusätzlich halten sie ein Array mit 10 Ziffernhäufigkeiten. Die Rekursion wählt für die aktuelle Ziffer eine Zahl zwischen \(0\) und \(\min(R,\text{verbleibend})\), speichert sie, multipliziert den laufenden Nenner mit der passenden Fakultät und geht zur nächsten Ziffer weiter.
Eine Implementierung erlaubt \(L\) und \(R\) als Eingabeparameter und enthält kleine Kontrollfälle wie die 3-stellige und 4-stellige Variante; die beiden anderen sind direkt auf Euler 172 festgelegt. Inhaltlich führen alle drei dieselbe Suche aus.
An einem gültigen Blatt berechnet die Implementierung zunächst den Multinomialterm \(L!/\prod c_d!\). Wenn mindestens eine 0 verwendet wurde, wird zusätzlich der Beitrag mit führender Null bestimmt, indem im Nenner \(c_0!\) durch \((c_0-1)!\) ersetzt wird. Genau das entspricht dem Festhalten einer 0 an der ersten Stelle. Die Differenz dieser beiden ganzzahligen Werte wird zum Gesamtergebnis addiert.
Darum sind die Programme so kompakt: Ist die richtige Formel für die Häufigkeitsvektoren einmal gefunden, besteht die gesamte Lösung nur noch aus einer beschränkten Tiefensuche und einer \(O(1)\)-Auswertung pro zulässigem Blatt.
Sei
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
die Anzahl der zulässigen Ziffernvektoren. Die Rekursion besucht genau diese Vektoren sowie die dazugehörigen inneren Knoten; damit beträgt die Laufzeit \(O(B(L,R))\), bis auf einen konstanten Faktor durch die festen zehn Ziffern.
Für Euler 172 ist dieser Zustandsraum winzig im Vergleich zur naiven Suche über \(10^{18}\) Möglichkeiten. Der Speicherbedarf liegt bei \(O(L)\) für die Fakultätstabelle und \(O(10)\) für das Häufigkeitsarray samt Rekursionstiefe. Die Rechnungen bleiben exakt, weil jeder Beitrag ein ganzzahliger Multinomialwert ist.
Project Euler 172, hiçbir rakamın üçten fazla görünmediği 18 basamaklı onluk sayıların sayısını ister. İlk basamak 0 olamaz; dolayısıyla sayımın tek asimetrik noktası baştaki basamaktır, geri kalan yerde \(0,1,\dots,9\) rakamları aynı şekilde ele alınır.
Uygulamalar, uzunluk için \(L\) ve tekrar üst sınırı için \(R\) kullanan biraz daha genel bir çerçeveyle yazılmıştır. Bu problemde \(L=18\) ve \(R=3\) alınır.
Asıl fikir, somut 18 basamaklı sayıları üretmek yerine her rakamın kaç kez kullanıldığını saymaktır. Bu çokluklar sabitlenince geriye, başta 0 gelme durumunu çıkaran bir multinom sayımı kalır.
\(c_d\), rakam \(d\)'nin kaç kez geçtiğini göstersin. O zaman her geçerli sayı
$$c=(c_0,c_1,\dots,c_9)$$
vektörünü üretir ve bu vektör
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R$$
koşullarını sağlar. Euler 172 özelinde bu
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3$$
demektir. Yani problem aslında 18'in, her parçası en fazla 3 olan 10 parçalı tüm sınırlı dağılımlarını toplamaktır. Kodlardaki özyineleme de tam olarak bu vektörleri, rakam rakam dolaşır.
Şimdi bir \(c\) vektörü sabitlensin. Baştaki 0 yasağı olmasaydı, bu çoklu kümenin tüm diziliş sayısı multinom katsayısı olurdu:
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
Eğer \(c_0=0\) ise bu zaten doğru katkıdır. Eğer \(c_0 \gt 0\) ise, 0 ile başlayan dizilişleri çıkarmak gerekir. İlk basamağa bir 0 yerleştirilirse geriye \(L-1\) yer ve \((c_0-1,c_1,\dots,c_9)\) sayıları kalır; dolayısıyla geçersiz diziliş sayısı
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}$$
olur. Böylece \(c\) vektörünün katkısı
$$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!}$$
şeklindedir. Bu ifade sadeleştirilince, \(c_0=0\) durumunda da geçerli olan tek biçimli form elde edilir:
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
Aranan toplam, bütün geçerli rakam çokluk vektörleri üzerinde bu \(N(c)\) değerlerinin toplamıdır.
Küçük bir 4 basamaklı örnek, baştaki 0 düzeltmesini çok net gösterir. Şu çoklukları alalım:
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
ve diğer tüm rakamların çokluğu 0 olsun. Çoklu küme \(\{0,0,1,2\}\) olduğu için toplam permütasyon sayısı
$$\frac{4!}{2!}=12$$
olur. Bunların içinde, başa bir 0 sabitlenip \(\{0,1,2\}\) permüte edilerek elde edilen
$$\frac{3!}{1!}=6$$
adet diziliş geçersizdir. Dolayısıyla geçerli 4 basamaklı sayı sayısı \(12-6=6\) olur. Kısa formül de aynı sonucu verir:
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
18 basamaklı asıl problemde yapılan düzeltme de birebir budur; yalnızca geçerli çokluk vektörlerinin sayısı çok daha fazladır.
Özyineleme, \(0,1,\dots,d-1\) rakamlarının çokluklarını belirlemiş olduğunda üç bilgi taşır:
$$\text{geçerli rakam }d,\qquad \text{kalan yer sayısı},\qquad \prod_{e=0}^{d-1} c_e!.$$
Kritik değişmez, bu akan faktöriyel çarpımıdır. Arama 10. rakama ulaşıp kalan yer sayısı 0 olduğunda bu çarpım tam olarak \(\prod_{d=0}^{9} c_d!\) paydasına dönüşmüş olur; böylece yaprak katkısı sabit zamanda hesaplanır. Kod hiçbir zaman gerçek 18 basamaklı sayıları üretmez.
C++, Python ve Java uygulamaları önce gerekli uzunluğa kadar faktöriyelleri önceden hesaplar. Ayrıca 10 elemanlı bir rakam sayacı tutarlar. Özyinelemeli arama, o anki rakam için \(0\) ile \(\min(R,\text{kalan})\) arasında bir çokluk seçer, bunu kaydeder, koşan paydayı ilgili faktöriyel ile çarpar ve bir sonraki rakama geçer.
Uygulamalardan biri \(L\) ve \(R\) parametrelerini dışarıdan alabilir ve 3 basamaklı, 4 basamaklı küçük kontrol durumları içerir; diğer ikisi Euler 172 değerlerine doğrudan sabitlenmiştir. Matematiksel olarak üçü de aynı aramayı yapar.
Geçerli bir yaprakta önce \(L!/\prod c_d!\) multinom terimi hesaplanır. Eğer en az bir tane 0 kullanılmışsa, paydada \(c_0!\) yerine \((c_0-1)!\) konarak başta 0 bulunan terim de hesaplanır; bu, ilk basamağa bir 0 sabitlemenin tam karşılığıdır. İki tamsayının farkı toplam sonuca eklenir.
Programların kısa olmasının sebebi budur: doğru kombinatorik formül kurulduktan sonra geriye yalnızca sınırlı bir DFS ve her geçerli yaprakta \(O(1)\) maliyetli aritmetik kalır.
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
ile geçerli rakam çokluk vektörlerinin sayısını gösterelim. Özyineleme tam olarak bu vektörleri ve onlara karşılık gelen iç düğümleri ziyaret ettiği için çalışma süresi, sabit olan 10 rakam faktörü dışında, \(O(B(L,R))\) olur.
Euler 172 için bu durum uzayı, saf kuvvet yaklaşımındaki \(10^{18}\) olasılıkla kıyaslanamayacak kadar küçüktür. Bellek kullanımı faktöriyel tablosu için \(O(L)\), sayaç dizisi ve çağrı yığını için \(O(10)\) düzeyindedir. Her katkı tam sayılı bir multinom sayımı olduğu için bütün aritmetik hatasızdır.
Project Euler 172 pide contar cuántos números decimales de 18 cifras existen si ningún dígito aparece más de tres veces. La primera cifra no puede ser 0, de modo que la posición inicial es la única fuente de asimetría; fuera de eso, los diez dígitos \(0,1,\dots,9\) se tratan de la misma manera.
Las implementaciones están escritas con una formulación un poco más general, usando \(L\) para la longitud y \(R\) para el máximo de repeticiones. En este problema concreto, \(L=18\) y \(R=3\).
La idea central es no enumerar cadenas concretas de 18 cifras, sino contar cuántas veces se usa cada dígito. Una vez fijadas esas multiplicidades, lo único que queda es un conteo multinomial con una corrección por cero inicial.
Sea \(c_d\) el número de apariciones del dígito \(d\). Entonces cada número válido determina un vector
$$c=(c_0,c_1,\dots,c_9)$$
que satisface
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$
Para Euler 172, esto se especializa en
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$
Por tanto, el problema real es una suma sobre todas las composiciones acotadas de 18 en 10 partes. La recursión de las implementaciones enumera exactamente esos vectores, dígito por dígito.
Fijemos un vector admisible \(c\). Si se permitieran ceros iniciales, el número de ordenaciones del multiconjunto sería el coeficiente multinomial
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
Si \(c_0=0\), esa ya es la contribución correcta. Si \(c_0 \gt 0\), hay que restar las ordenaciones que empiezan con 0. Al fijar un 0 en la primera posición quedan \(L-1\) lugares y el vector reducido \((c_0-1,c_1,\dots,c_9)\), así que el número de casos inválidos es
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
La contribución de \(c\) es entonces
$$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!}.$$
Tras simplificar, se obtiene una expresión uniforme que también funciona cuando \(c_0=0\):
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
La respuesta final es la suma de \(N(c)\) sobre todos los vectores de conteo permitidos.
Un ejemplo pequeño de 4 cifras deja clara la corrección por cero inicial. Supongamos que las multiplicidades son
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
y que todas las demás son 0. El multiconjunto es \(\{0,0,1,2\}\), así que el número total de permutaciones es
$$\frac{4!}{2!}=12.$$
Entre ellas, las inválidas son las que empiezan por 0; se obtienen fijando un 0 al principio y permutando \(\{0,1,2\}\):
$$\frac{3!}{1!}=6.$$
Por tanto, el número de números válidos de 4 cifras es \(12-6=6\). La fórmula compacta da el mismo resultado:
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
En el problema completo de 18 cifras se aplica exactamente la misma corrección, solo que sobre un conjunto mayor de vectores admisibles.
Cuando la recursión ya fijó las multiplicidades de los dígitos \(0,1,\dots,d-1\), conserva tres datos:
$$\text{dígito actual }d,\qquad \text{posiciones restantes},\qquad \prod_{e=0}^{d-1} c_e!.$$
El producto de factoriales es la invariante esencial. Cuando la búsqueda alcanza el dígito 10 y ya no quedan posiciones por asignar, ese producto se ha convertido en el denominador completo \(\prod_{d=0}^{9} c_d!\), y la contribución de la hoja se evalúa en tiempo constante con las fórmulas anteriores. Nunca se construyen números de 18 cifras uno por uno.
Las implementaciones en C++, Python y Java precalculan primero los factoriales hasta la longitud necesaria. También mantienen un arreglo de 10 posiciones con los conteos de los dígitos. La búsqueda recursiva elige para el dígito actual un valor entre \(0\) y \(\min(R,\text{restante})\), lo guarda, multiplica el denominador acumulado por el factorial correspondiente y pasa al siguiente dígito.
Una implementación deja \(L\) y \(R\) como parámetros e incluye pequeños casos de comprobación como los conteos para 3 y 4 cifras; las otras dos fijan directamente los valores de Euler 172. Desde el punto de vista matemático, las tres realizan la misma exploración.
En una hoja válida, la implementación calcula el término multinomial \(L!/\prod c_d!\). Si se usó al menos un cero, también calcula el término de cero inicial sustituyendo \(c_0!\) por \((c_0-1)!\) en el denominador, que es exactamente lo que corresponde a fijar un 0 en la primera posición. La diferencia entre ambos enteros se suma al total acumulado.
Por eso los programas son breves: una vez identificada la fórmula correcta sobre vectores de conteo, la implementación se reduce a una DFS acotada y a una evaluación aritmética de costo \(O(1)\) en cada hoja válida.
Sea
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
el número de vectores de conteo admisibles. La recursión visita exactamente esos vectores, además de sus nodos internos asociados, de modo que el tiempo de ejecución es \(O(B(L,R))\), salvo por un factor constante procedente del conjunto fijo de diez dígitos.
Para Euler 172, este espacio de estados es diminuto comparado con la búsqueda ingenua sobre \(10^{18}\) cadenas decimales. El uso de memoria es \(O(L)\) para la tabla de factoriales y \(O(10)\) para el arreglo de conteos y la pila recursiva. Toda la aritmética es exacta porque cada aporte es un conteo multinomial entero.
Project Euler 172 要求统计这样的 18 位十进制数：任何一个数字都不能出现超过 3 次，并且首位不能是 0。整个计数里唯一不对称的地方就是首位限制；除此之外，十个数字 \(0,1,\dots,9\) 的地位完全相同。
实现代码实际上围绕更一般的参数 \(L\) 和 \(R\) 来写，其中 \(L\) 表示位数，\(R\) 表示单个数字允许出现的最大次数。在本题中，\(L=18\)，\(R=3\)。
真正有效的对象不是具体的 18 位数字，而是每个数字用了多少次。一旦这些重数固定下来，问题就变成了一个多重集合排列计数，再额外减掉首位为 0 的非法情况。
设 \(c_d\) 表示数字 \(d\) 出现的次数，那么每个合法数字都对应一个向量
$$c=(c_0,c_1,\dots,c_9)$$
并满足
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$
对 Euler 172 而言，这就是
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$
因此，这道题本质上是在所有满足上界约束的 10 维计数向量上求和。代码中的深度优先搜索并不枚举具体数字，而是按数字 \(0,1,\dots,9\) 依次决定这些计数。
先固定一个可行向量 \(c\)。如果允许前导 0，那么由这些数字组成的不同排列总数就是多项式系数
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
如果 \(c_0=0\)，这已经是最终贡献；因为没有 0，自然不存在首位为 0 的非法排列。若 \(c_0 \gt 0\)，则必须减去所有以 0 开头的排列。把一个 0 固定在最前面以后，还剩下 \(L-1\) 个位置，数字重数变成 \((c_0-1,c_1,\dots,c_9)\)，所以非法排列数为
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
于是，向量 \(c\) 的合法贡献是
$$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!}.$$
把式子整理一下，还可以得到一个统一写法，而且在 \(c_0=0\) 时也同样成立：
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
整道题的答案，就是把所有可行计数向量的 \(N(c)\) 全部加起来。
看一个 4 位数的缩小版例子。设
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
其余数字都不出现。此时多重集合是 \(\{0,0,1,2\}\)，如果不考虑首位限制，总排列数是
$$\frac{4!}{2!}=12.$$
其中非法的排列恰好是首位放了 0 的那些。把一个 0 固定在最前面之后，剩余 \(\{0,1,2\}\) 的排列数为
$$\frac{3!}{1!}=6.$$
所以真正合法的 4 位数只有 \(12-6=6\) 个。统一公式也给出同样的结果：
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
18 位原题所做的事情完全一样，只不过需要遍历的可行计数向量更多而已。
当递归已经为数字 \(0,1,\dots,d-1\) 指定好出现次数时，它维护三项信息：
$$\text{当前处理到的数字 }d,\qquad \text{还剩多少位置},\qquad \prod_{e=0}^{d-1} c_e!.$$
其中最关键的是最后那个阶乘乘积。等递归走到数字 10 且剩余位置数为 0 时，这个乘积就正好变成完整分母 \(\prod_{d=0}^{9} c_d!\)，于是叶子结点的贡献可以直接用上面的公式在常数时间内算出。整个过程中根本不需要构造任何具体的 18 位整数。
C++、Python 和 Java 实现都会先预计算到目标长度为止的阶乘值，同时维护一个长度为 10 的数组记录每个数字当前被分配了多少次。递归在处理某个数字时，会尝试从 \(0\) 到 \(\min(R,\text{剩余位置})\) 的所有可行次数，把对应的阶乘乘进运行中的分母，然后继续处理下一个数字。
其中一个实现把 \(L\) 和 \(R\) 暴露为参数，并额外带有 3 位数、4 位数等小规模检查；另外两个实现则直接固定在 Euler 172 的参数上。虽然外层写法略有不同，但三者执行的是同一个组合计数过程。
当递归到达一个合法叶子时，实现先计算 \(L!/\prod c_d!\)，即允许前导 0 时的全部多重排列数。若 \(c_0 \gt 0\)，它再把分母中的 \(c_0!\) 改成 \((c_0-1)!\)，得到首位固定为 0 的非法排列数。两者相减后加入总和。
这也解释了为什么代码本身相当短：真正的数学工作是找到正确的计数对象和公式，一旦这一点明确，实现层面只需要一个受限的 DFS，再加上每个合法叶子上的 \(O(1)\) 整数运算。
记
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
为所有可行计数向量的个数。递归恰好遍历这些向量以及与之对应的内部结点，因此时间复杂度可以写成 \(O(B(L,R))\)，固定的 10 个数字只带来常数因子。
对 Euler 172 来说，这个状态空间与朴素地检查全部 \(10^{18}\) 个十进制串相比要小得多。空间复杂度是阶乘表的 \(O(L)\) 加上计数数组和递归栈的 \(O(10)\)。由于每一项都是整数形式的多项式系数，整个计算过程保持精确整数运算。
В задаче Project Euler 172 нужно посчитать количество 18-значных десятичных чисел, в которых ни одна цифра не встречается более трёх раз. Первая цифра не может быть нулём, поэтому единственная асимметрия возникает из-за ведущего разряда; во всём остальном цифры \(0,1,\dots,9\) рассматриваются одинаково.
Реализации построены вокруг чуть более общей постановки с параметрами \(L\) для длины и \(R\) для максимального числа повторений. Для самой задачи берутся \(L=18\) и \(R=3\).
Главный шаг состоит в том, чтобы не перебирать сами 18-значные числа, а считать, сколько раз используется каждая цифра. Как только эти кратности зафиксированы, остаётся обычный мультиномиальный подсчёт перестановок мультимножества с поправкой на ведущий ноль.
Пусть \(c_d\) обозначает число вхождений цифры \(d\). Тогда каждому допустимому числу соответствует вектор
$$c=(c_0,c_1,\dots,c_9)$$
такой, что
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$
В задаче Euler 172 это означает
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$
Значит, задача сводится к суммированию по всем ограниченным разбиениям числа 18 на 10 частей. Именно эти векторы рекурсивно перечисляют реализации, двигаясь по цифрам от 0 до 9.
Зафиксируем допустимый вектор \(c\). Если бы ведущие нули разрешались, число перестановок мультимножества было бы равно мультиномиальному коэффициенту
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
Если \(c_0=0\), это уже и есть правильный вклад. Если же \(c_0 \gt 0\), нужно вычесть перестановки, начинающиеся с нуля. При фиксированном нуле на первом месте остаются \(L-1\) позиций и уменьшенный вектор \((c_0-1,c_1,\dots,c_9)\), поэтому число недопустимых вариантов равно
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
Следовательно, вклад вектора \(c\) равен
$$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!}.$$
После упрощения получается единая формула, которая работает и при \(c_0=0\):
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
Итоговый ответ получается суммированием \(N(c)\) по всем допустимым векторам кратностей.
Небольшой пример для 4-значных чисел хорошо показывает, зачем нужна поправка на ведущий ноль. Пусть
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
а все остальные кратности равны нулю. Тогда мультимножество цифр имеет вид \(\{0,0,1,2\}\), и общее число перестановок равно
$$\frac{4!}{2!}=12.$$
Недопустимые варианты начинаются с 0; они получаются фиксацией одного нуля в первом разряде и перестановкой \(\{0,1,2\}\):
$$\frac{3!}{1!}=6.$$
Значит, корректное число 4-значных чисел равно \(12-6=6\). Компактная формула даёт тот же результат:
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
В исходной 18-значной задаче выполняется ровно та же поправка, только допустимых векторов кратностей намного больше.
Когда рекурсия уже выбрала кратности для цифр \(0,1,\dots,d-1\), она хранит три величины:
$$\text{текущая цифра }d,\qquad \text{сколько позиций осталось},\qquad \prod_{e=0}^{d-1} c_e!.$$
Именно произведение факториалов является ключевым инвариантом. Когда поиск доходит до цифры 10 и свободных позиций уже нет, это произведение превращается в полный знаменатель \(\prod_{d=0}^{9} c_d!\), и вклад листа можно вычислить за константное время по формулам выше. Сами 18-значные строки никогда не строятся явно.
Реализации на C++, Python и Java сначала предварительно вычисляют факториалы до нужной длины. Также они поддерживают массив из 10 элементов с текущими кратностями цифр. Рекурсивный обход выбирает для текущей цифры значение от \(0\) до \(\min(R,\text{остаток})\), сохраняет его, умножает накопленный знаменатель на соответствующий факториал и переходит к следующей цифре.
Одна реализация позволяет передавать \(L\) и \(R\) параметрами и содержит небольшие контрольные случаи для 3- и 4-значных чисел; две другие жёстко зафиксированы на параметрах Euler 172. Но математически все три программы делают одно и то же.
В допустимом листе сначала вычисляется мультиномиальный член \(L!/\prod c_d!\). Если ноль использовался хотя бы один раз, отдельно вычисляется поправка для ведущего нуля: в знаменателе \(c_0!\) заменяется на \((c_0-1)!\), что точно соответствует фиксации нуля в первом разряде. Разность двух целых чисел добавляется к общему ответу.
Именно поэтому код остаётся коротким: после нахождения правильной комбинаторной формулы реализация сводится к ограниченному DFS и \(O(1)\)-арифметике на каждом допустимом листе.
Обозначим через
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
число допустимых векторов кратностей. Рекурсия посещает ровно эти векторы и соответствующие внутренние узлы, поэтому время работы равно \(O(B(L,R))\) с точностью до постоянного множителя, связанного с фиксированными десятью цифрами.
Для Euler 172 это пространство состояний ничтожно по сравнению с наивным перебором всех \(10^{18}\) десятичных строк. Память расходуется как \(O(L)\) на таблицу факториалов и \(O(10)\) на массив кратностей и стек рекурсии. Все вычисления точны, потому что каждый вклад является целым мультиномиальным количеством.
تطلب مسألة Project Euler 172 عدّ الأعداد العشرية ذات 18 خانة التي لا يظهر فيها أي رقم أكثر من ثلاث مرات. الخانة الأولى لا يجوز أن تكون صفراً، ولذلك فعدم التناظر الوحيد في العد يأتي من القيد على البداية، أما بقية الأرقام \(0,1,\dots,9\) فتُعامل بالطريقة نفسها.
التنفيذات مكتوبة بصياغة أعم قليلاً تستخدم \(L\) لطول العدد و\(R\) للحد الأقصى لتكرار الرقم. في هذه المسألة تحديداً نأخذ \(L=18\) و\(R=3\).
الفكرة الحاسمة هي ألّا نعدّد الأعداد ذات 18 خانة نفسها، بل نعدّ كم مرة استُخدم كل رقم. بعد تثبيت هذه المضاعفات يتحول كل شيء إلى عدّ ترتيبات لمتعدد مجموعة مع طرح الحالات التي تبدأ بصفر.
ليكن \(c_d\) عدد مرات ظهور الرقم \(d\). عندئذٍ يقابل كل عدد صالح متجه
$$c=(c_0,c_1,\dots,c_9)$$
يحقق الشرطين
$$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$
وفي مسألة Euler 172 يصبح ذلك
$$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$
إذن فالمسألة الحقيقية هي جمع المساهمات على جميع التوزيعات المقيدة للعدد 18 على 10 خانات عدّ. والبحث العودي في التنفيذات يمر على هذه المتجهات بالضبط، رقماً بعد رقم.
ثبّت متجهاً صالحاً \(c\). لو كان الصفر في البداية مسموحاً، لكان عدد الترتيبات الممكنة لمتعدد المجموعة هو المعامل متعدد الحدود
$$\frac{L!}{\prod_{d=0}^{9} c_d!}.$$
إذا كان \(c_0=0\) فهذه هي المساهمة الصحيحة مباشرة. أما إذا كان \(c_0 \gt 0\)، فيجب طرح الترتيبات التي تبدأ بصفر. عند تثبيت صفر في الخانة الأولى تبقى \(L-1\) خانات، وتصبح أعداد التكرار \((c_0-1,c_1,\dots,c_9)\)، ومن ثم يكون عدد الحالات غير الصالحة
$$\frac{(L-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
لذلك تكون مساهمة المتجه \(c\) مساوية لـ
$$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!}.$$
وبعد التبسيط نحصل على صيغة موحّدة تعمل حتى عندما يكون \(c_0=0\):
$$N(c)=\frac{(L-c_0)(L-1)!}{\prod_{d=0}^{9} c_d!}.$$
والجواب النهائي هو مجموع \(N(c)\) على جميع متجهات التكرار المسموح بها.
يوضح مثال صغير من 4 خانات لماذا يلزم طرح الحالات ذات الصفر البادئ. لنفرض أن
$$c_0=2,\qquad c_1=1,\qquad c_2=1,$$
وجميع الأرقام الأخرى تكرارها صفر. عندئذ يكون متعدد المجموعة هو \(\{0,0,1,2\}\)، وعدد جميع ترتيباته
$$\frac{4!}{2!}=12.$$
أما الترتيبات غير الصالحة فهي التي تبدأ بصفر، ويمكن عدّها بتثبيت صفر في البداية ثم ترتيب \(\{0,1,2\}\):
$$\frac{3!}{1!}=6.$$
إذن عدد الأعداد الصحيحة ذات 4 خانات هو \(12-6=6\). وتعطي الصيغة المختصرة النتيجة نفسها:
$$N(c)=\frac{(4-2)\cdot 3!}{2!}=6.$$
وفي المسألة الأصلية ذات 18 خانة تُطبَّق الفكرة نفسها تماماً، لكن على عدد أكبر من متجهات التكرار الممكنة.
عندما تكون العودية قد حددت أعداد التكرار للأرقام \(0,1,\dots,d-1\)، فإنها تحتفظ بثلاث معلومات:
$$\text{الرقم الحالي }d,\qquad \text{عدد الخانات المتبقية},\qquad \prod_{e=0}^{d-1} c_e!.$$
هذا الجداء المتراكم للعوامل هو الثابت الأهم. فعندما تصل العودية إلى الرقم 10 ولا تبقى أي خانات غير مملوءة، يكون هذا الجداء قد أصبح المقام الكامل \(\prod_{d=0}^{9} c_d!\)، وبذلك يمكن حساب مساهمة الورقة مباشرة في زمن ثابت من الصيغ السابقة. لا يتم إنشاء أي عدد ذي 18 خانة بشكل صريح.
تبدأ التنفيذات في C++ وPython وJava بحساب المضاريب حتى الطول المطلوب. كما تحتفظ بمصفوفة من 10 خانات تمثل عدد مرات استخدام كل رقم. في كل خطوة من البحث العودي يُختار للرقم الحالي عدد تكرارات بين \(0\) و\(\min(R,\text{المتبقي})\)، ثم يُسجَّل هذا العدد ويُضرب المقام التراكمي في المضروب الموافق له، وبعد ذلك ينتقل البحث إلى الرقم التالي.
إحدى التنفيذات تسمح بتمرير \(L\) و\(R\) كوسيطين وتتضمن حالات تحقق صغيرة مثل العدّ لثلاث خانات وأربع خانات، بينما التنفيذان الآخران مثبتان مباشرة على قيم Euler 172. لكن من الناحية الرياضية كلها تنفذ العدّ نفسه.
عند الوصول إلى ورقة صالحة يحسب التنفيذ أولاً الحد متعدد الحدود \(L!/\prod c_d!\). وإذا كان الصفر قد استُخدم مرة واحدة على الأقل، فإنه يحسب أيضاً حد الصفر البادئ باستبدال \(c_0!\) في المقام بـ \((c_0-1)!\)، وهو بالضبط ما يقابل تثبيت صفر في الخانة الأولى. بعد ذلك تُضاف فروق هذه القيم الصحيحة إلى المجموع الكلي.
ولهذا تبدو البرامج قصيرة: ما إن تُعرف الصيغة التوافقية الصحيحة لمتجهات التكرار حتى يصبح التنفيذ مجرد DFS مقيد مع تقييم حسابي \(O(1)\) في كل ورقة صالحة.
إذا رمزنا بـ
$$B(L,R)=[x^L](1+x+\cdots+x^R)^{10}$$
إلى عدد متجهات التكرار المسموح بها، فإن العودية تزور هذه المتجهات نفسها مع العقد الداخلية المرتبطة بها، ولذلك يكون زمن التنفيذ \(O(B(L,R))\) حتى عامل ثابت ناتج عن مجموعة الأرقام العشرة الثابتة.
في Euler 172 يبقى هذا الفضاء صغيراً جداً مقارنة بالبحث الساذج في جميع السلاسل العشرية وعددها \(10^{18}\). أما الذاكرة فهي \(O(L)\) لجدول المضاريب و\(O(10)\) لمصفوفة العدّ ومكدس الاستدعاء. وتبقى الحسابات كلها صحيحة تماماً لأن كل مساهمة هي عدد صحيح ناتج من معامل متعدد الحدود.