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.
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\).
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.
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.
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.
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.
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.
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.$$
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.
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.
Für jede \(k\)-stellige Zahl \(n\) sei \(P(n)\) die Anzahl größerer \(k\)-stelliger Zahlen, die durch Umordnung derselben Ziffern entstehen. Gesucht ist
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
wobei \(\mathcal{D}_k\) die Menge aller \(k\)-stelligen Zahlen ist, also ohne führende Null. Die entscheidende Beobachtung lautet: Nicht die konkrete Reihenfolge der Ziffern ist die richtige Arbeitseinheit, sondern ihre Häufigkeiten. Sobald man Zahlen nach ihren Ziffernmultiplikitäten gruppiert, wird die Aufgabe zu einer sauberen kombinatorischen Summe.
Schreibe den Ziffernvektor einer Zahl als
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$$
Zwei \(k\)-stellige Zahlen gehören genau dann zur selben Klasse, wenn sie denselben Vektor \(c\) besitzen. Alle gültigen Zahlen dieser Klasse sind Permutationen derselben Ziffernmultimenge, also hängt der Beitrag der Klasse nur von \(c\) ab.
Die Wahl des Vektors \(c\) ist ein Stars-and-Bars-Problem: \(k\) Stellen werden auf die zehn Ziffern \(0,1,\dots,9\) verteilt. Daher gibt es insgesamt
$$\binom{k+9}{9}$$
mögliche Klassen. Die Implementierungen erzeugen deshalb nicht einzelne Zahlen, sondern diese Häufigkeitsvektoren, denn ein einziger Vektor beschreibt sofort eine ganze Permutationsklasse.
Für einen festen Vektor \(c\) ist die Anzahl aller Länge-\(k\)-Ziffernfolgen dieser Multimenge durch den Multinomialkoeffizienten gegeben:
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
Darin sind auch Anordnungen mit führender Null enthalten. Diese sind keine gültigen \(k\)-stelligen Zahlen und müssen deshalb separat entfernt werden.
Falls \(c_0=0\), ist jede von \(A(c)\) gezählte Anordnung bereits gültig. Falls \(c_0>0\), erhält man die Anordnungen mit führender Null, indem man eine Null an die erste Stelle setzt und die verbleibenden \(k-1\) Plätze permutiert:
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
Mit \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\) vereinfacht sich das zu
$$Z(c)=A(c)\frac{c_0}{k}.$$
Somit ist die Anzahl gültiger \(k\)-stelliger Zahlen in der Klasse
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$$
Auch für \(c_0=0\) bleibt diese Formel korrekt, weil dann der Korrekturterm automatisch verschwindet.
Ordne die gültigen Zahlen einer Klasse aufsteigend:
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
Für die \(i\)-te Zahl ist \(P(x_i)\) genau die Anzahl späterer Elemente in dieser Liste, also \(V(c)-i\). Summiert man über die ganze Klasse, erhält man
$$\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}.$$
Jede Klasse trägt also genau die Anzahl ungeordneter Paare verschiedener gültiger Permutationen dieser Klasse bei.
Durch Summation über alle Ziffernvektoren folgt
$$\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}.}$$
Genau diese Formel setzt das Programm um. Es vergleicht Permutationen also nie direkt, sondern verwendet nur die Multiplikitäten der Ziffern.
Die Implementierungen verwenden \(S(3)=1701\) als kleinen Prüfwert. Für \(k=3\) ergeben sich die relevanten Musterfamilien
$$\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}$$
Dabei bezeichnen \(a,b,c\) von Null verschiedene Ziffern mit den jeweils naheliegenden Verschiedenheitsbedingungen. Die Klassenzahlen sind also \(9\), \(9\), \(72=9\cdot 8\), \(36=\binom{9}{2}\) und \(84=\binom{9}{3}\). Damit lauten die Gesamtbeiträge \(0\), \(0\), \(9\), \(216\), \(216\) und \(1260\), also
$$S(3)=9+216+216+1260=1701.$$
Die C++-, Python- und Java-Implementierungen folgen alle demselben kombinatorischen Plan. Zuerst werden Fakultäten bis \(k\) vorab berechnet, weil für jede Klasse der multinomiale Nenner \(c_0!\cdots c_9!\) benötigt wird. Danach wird per Tiefensuche über die zehn Ziffernanzahlen iteriert: Für die Ziffern \(0\) bis \(8\) werden Werte gesetzt, und der verbleibende Rest wird der Ziffer \(9\) zugewiesen. So wird jeder zulässige Vektor genau einmal besucht.
An jedem Blatt dieser Suche berechnet die Implementierung \(A(c)=k!/\prod c_d!\), wandelt das in die gültige Klassengröße \(V(c)=A(c)(k-c_0)/k\) um und addiert \(\binom{V(c)}{2}\) zur Gesamtsumme. Die drei Implementierungen unterscheiden sich nur in sprachspezifischen Zahlentypen; algorithmisch sind sie identisch.
Es gibt genau \(\binom{k+9}{9}\) Ziffernvektoren, und jeder davon wird mit \(O(10)\) arithmetischen Operationen verarbeitet. Die Vorberechnung der Fakultäten kostet \(O(k)\) Zeit. Damit ergibt sich insgesamt
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
für das feste Zehnersystem. Der Speicherbedarf beträgt \(O(k)\) für die Fakultätstabelle sowie \(O(10)\) für Zählerarray und Rekursionszustand.
Her \(k\) basamaklı \(n\) sayısı için \(P(n)\), \(n\)'in rakamları permüte edilerek elde edilen ve \(n\)'den büyük olan \(k\) basamaklı sayıların adedi olsun. Aranan değer
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
burada \(\mathcal{D}_k\), başında sıfır olmayan tüm \(k\) basamaklı sayılar kümesidir. Temel gözlem şudur: Asıl önemli olan rakamların sırası değil, her rakamın kaç kez geçtiğidir. Sayıları rakam çokluklarına göre grupladığımız anda problem tek tek permütasyonları incelemek yerine temiz bir kombinatorik toplam haline gelir.
Bir sayının rakam sayım vektörünü
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k$$
şeklinde yazalım. İki \(k\) basamaklı sayı ancak ve ancak aynı \(c\) vektörüne sahipse aynı sınıfa aittir. Bu sınıftaki tüm geçerli sayılar aynı rakam çoklu-kümesinin permütasyonları olduğundan sınıfın katkısı yalnızca \(c\)'ye bağlıdır.
\(c\) vektörünü seçmek bir stars-and-bars problemidir: \(k\) adet basamak yuvasını \(0,1,\dots,9\) rakamları arasında dağıtırız. Bu yüzden olası sınıf sayısı
$$\binom{k+9}{9}$$
olur. Uygulamalar tek tek sayıları üretmez; bunun yerine bu sayım vektörlerini üretir. Çünkü tek bir vektör bütün bir permütasyon sınıfını özetler.
Sabit bir \(c\) vektörü için, bu rakam çoklu-kümesinin tüm uzunluk-\(k\) dizilim sayısı multinom katsayısı ile verilir:
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
Bu sayı başta \(0\) olan dizilimleri de içerir. O tür dizilimler geçerli \(k\) basamaklı sayılar değildir; dolayısıyla ayrıca çıkarılmaları gerekir.
Eğer \(c_0=0\) ise, \(A(c)\) ile sayılan her dizilim zaten geçerlidir. Eğer \(c_0>0\) ise, başta sıfır olan dizilimler bir sıfırı ilk konuma sabitleyip kalan \(k-1\) yeri permüte ederek elde edilir:
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
\(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\) yazılırsa bu ifade
$$Z(c)=A(c)\frac{c_0}{k}$$
şeklinde sadeleşir. Böylece sınıftaki geçerli \(k\) basamaklı sayı sayısı
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}$$
olur. Bu formül \(c_0=0\) iken de geçerlidir; çünkü düzeltme terimi kendiliğinden sıfır olur.
Bir sınıftaki geçerli sayıları küçükten büyüğe sıralayalım:
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
\(i\). sayı için \(P(x_i)\), aynı listede ondan sonra gelen eleman sayısıdır; yani \(V(c)-i\). Sınıfın tamamında toplarsak
$$\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}$$
elde edilir. Demek ki her sınıfın katkısı, o sınıftaki farklı geçerli permütasyon çiftlerinin sayısıdır.
Tüm rakam sayım vektörlerinin katkılarını toplarsak
$$\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}.}$$
Programın uyguladığı formül tam olarak budur. Tek tek permütasyon karşılaştırması yapmaya gerek yoktur; bir sınıfın tüm katkısı rakam çokluklarından doğrudan çıkar.
Uygulamalar küçük bir kontrol noktası olarak \(S(3)=1701\) değerini kullanır. \(k=3\) için ilgili desen aileleri şunlardır:
$$\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}$$
Burada \(a,b,c\) sıfır olmayan rakamları gösterir ve gereken yerlerde birbirlerinden farklıdır. Sınıf sayıları sırasıyla \(9\), \(9\), \(72=9\cdot 8\), \(36=\binom{9}{2}\) ve \(84=\binom{9}{3}\) olur. Dolayısıyla toplam katkılar \(0\), \(0\), \(9\), \(216\), \(216\) ve \(1260\) olup
$$S(3)=9+216+216+1260=1701$$
sonucuna ulaşılır.
C++, Python ve Java uygulamalarının üçü de aynı kombinatorik planı izler. Önce \(k\)'ya kadar faktöriyeller önceden hesaplanır; çünkü her sınıf değerlendirmesinde multinom paydasındaki \(c_0!\cdots c_9!\) çarpımı gerekir. Ardından on rakamın sayıları üzerinde derinlik öncelikli bir dolaşım yapılır: \(0\) ile \(8\) arasındaki rakamların adetleri tek tek atanır, kalan miktar da otomatik olarak \(9\) rakamına verilir. Böylece her uygun vektör tam bir kez ziyaret edilir.
Aramanın her yaprağında uygulama \(A(c)=k!/\prod c_d!\) değerini hesaplar, bunu geçerli sınıf büyüklüğü \(V(c)=A(c)(k-c_0)/k\) biçimine çevirir ve \(\binom{V(c)}{2}\) terimini toplama ekler. Diller arasında değişen tek nokta tamsayı türlerinin ayrıntılarıdır; algoritmik adımlar aynıdır.
Toplam \(\binom{k+9}{9}\) adet rakam sayım vektörü vardır ve her biri \(O(10)\) aritmetik işlemle işlenir. Faktöriyel ön hesabı \(O(k)\) zaman alır. Dolayısıyla toplam çalışma süresi
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
olur; burada on rakamlı alfabe sabittir. Bellek kullanımı faktöriyel tablosu için \(O(k)\), sayım dizisi ve özyineleme durumu için \(O(10)\)'dur.
Para cada entero de \(k\) dígitos \(n\), sea \(P(n)\) la cantidad de enteros mayores, también de \(k\) dígitos, que se obtienen al permutar las cifras de \(n\). Queremos calcular
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
donde \(\mathcal{D}_k\) es el conjunto de todos los números de \(k\) dígitos, así que no se permiten ceros iniciales. La observación clave es que el orden exacto de las cifras no es la unidad natural del problema. Lo que importa es cuántas veces aparece cada cifra. Al agrupar por multiplicidades de dígitos, la suma entera se convierte en un conteo combinatorio directo.
Escribamos el vector de conteos de cifras como
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$$
Dos números de \(k\) dígitos pertenecen a la misma clase exactamente cuando tienen el mismo vector \(c\). Todos los números válidos de esa clase son permutaciones del mismo multiconjunto de cifras, de modo que la contribución de la clase depende solo de \(c\).
Elegir el vector \(c\) es un problema de stars and bars: repartimos \(k\) posiciones entre los diez valores \(0,1,\dots,9\). Por tanto, el número total de clases posibles es
$$\binom{k+9}{9}.$$
Las implementaciones no recorren números concretos. Recorren estos vectores de conteo, porque un solo vector resume de una vez toda una clase de permutaciones.
Para un vector fijo \(c\), la cantidad de cadenas de longitud \(k\) que se obtienen al reordenar ese multiconjunto viene dada por el coeficiente multinomial
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
Este valor cuenta todas las disposiciones, incluidas las que empiezan con \(0\). Esas cadenas no representan enteros válidos de \(k\) dígitos, así que hay que corregirlas aparte.
Si \(c_0=0\), todo lo contado por \(A(c)\) ya es válido. Si \(c_0>0\), las disposiciones con cero inicial se obtienen fijando un cero en la primera posición y permutando los \(k-1\) lugares restantes:
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
Usando \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\), esto se simplifica a
$$Z(c)=A(c)\frac{c_0}{k}.$$
Así, el número de enteros válidos de \(k\) dígitos en la clase es
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$$
La misma fórmula sigue siendo correcta cuando \(c_0=0\), porque entonces el término de corrección desaparece automáticamente.
Ordenemos los números válidos de una clase en forma creciente:
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
Para el \(i\)-ésimo número, la cantidad \(P(x_i)\) es exactamente el número de elementos posteriores en esa lista, es decir, \(V(c)-i\). Al sumar sobre toda la clase obtenemos
$$\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}.$$
En otras palabras, cada clase aporta exactamente el número de pares no ordenados de permutaciones válidas distintas dentro de esa misma clase.
Al sumar la contribución de todos los vectores de conteo llegamos a
$$\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}.}$$
Ésa es exactamente la fórmula que implementa el programa. No hace falta comparar permutaciones una por una, porque toda la contribución de una clase se obtiene directamente de sus multiplicidades.
Las implementaciones usan \(S(3)=1701\) como comprobación pequeña. Para \(k=3\), las familias de patrones relevantes son
$$\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}$$
Aquí \(a,b,c\) representan cifras no nulas, con las condiciones naturales de distinción en cada caso. Las cantidades de clases son \(9\), \(9\), \(72=9\cdot 8\), \(36=\binom{9}{2}\) y \(84=\binom{9}{3}\). Por tanto, las contribuciones totales son \(0\), \(0\), \(9\), \(216\), \(216\) y \(1260\), y así
$$S(3)=9+216+216+1260=1701.$$
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan combinatorio. Primero precalculan los factoriales hasta \(k\), porque cada clase necesita el denominador multinomial \(c_0!\cdots c_9!\). Después realizan una enumeración en profundidad sobre los diez conteos de cifras: se fijan los valores para las cifras \(0\) hasta \(8\), y la cantidad restante queda determinada para la cifra \(9\). Así se visita cada vector admisible exactamente una vez.
En cada hoja de esa búsqueda, la implementación calcula \(A(c)=k!/\prod c_d!\), lo transforma en el tamaño válido de la clase \(V(c)=A(c)(k-c_0)/k\), y añade \(\binom{V(c)}{2}\) al acumulado. Las tres versiones solo difieren en detalles de tipos enteros propios del lenguaje; el algoritmo es el mismo en todas.
Hay exactamente \(\binom{k+9}{9}\) vectores de conteo, y cada uno se procesa con \(O(10)\) operaciones aritméticas. El precálculo de factoriales cuesta \(O(k)\) tiempo. Por lo tanto, el tiempo total es
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
para el alfabeto fijo de diez dígitos. La memoria utilizada es \(O(k)\) para la tabla de factoriales y \(O(10)\) para el vector de conteos y el estado de la recursión.
对每个 \(k\) 位整数 \(n\)，记 \(P(n)\) 为用 \(n\) 的数字重新排列后得到的、仍然是 \(k\) 位且严格大于 \(n\) 的整数个数。我们要求
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
其中 \(\mathcal{D}_k\) 表示所有 \(k\) 位整数，因此不允许前导零。这个问题如果按具体数字逐个处理，会陷入大量重复工作。真正决定答案的不是数字的原始顺序，而是 \(0\) 到 \(9\) 每个数字各出现了多少次。把所有数字按这种“数字重数向量”分组后，问题就变成了一个有限的组合计数。
把一个数的数字计数写成向量
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$$
两个 \(k\) 位数当且仅当拥有相同的向量 \(c\) 时，才属于同一个重排类。因为同一类中的所有有效数字都来自同一个数字多重集，所以这一类对总和的贡献只取决于 \(c\)，与类中某个具体排列无关。
选择向量 \(c\) 本质上就是一个 stars and bars 问题：把 \(k\) 个位置分配给十个数字 \(0,1,\dots,9\)。因此可能的类总数是
$$\binom{k+9}{9}.$$
实现并不枚举所有 \(k\) 位数，而是枚举这些计数向量。这样做的原因很直接：一个向量就代表了一整类互为重排的数字，能一次性处理整类贡献。
固定一个向量 \(c\) 后，这个数字多重集能够形成的长度为 \(k\) 的字符串总数由多项式系数给出：
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
这里统计的是所有排列方式，其中包括首位是 \(0\) 的情况。那类字符串并不是合法的 \(k\) 位整数，所以还需要再做一次修正。
如果 \(c_0=0\)，那么 \(A(c)\) 统计到的每一种排列都已经合法。如果 \(c_0>0\)，那么首位为零的排列可以这样数：先固定一个 \(0\) 在第一位，再对剩下的 \(k-1\) 个位置进行排列，于是
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
再利用 \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\)，可化简为
$$Z(c)=A(c)\frac{c_0}{k}.$$
因此，这一类真正对应的合法 \(k\) 位整数个数为
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$$
当 \(c_0=0\) 时，这个公式仍然成立，因为修正项自然为零。
把某一类中的所有合法数字按从小到大排列：
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
对于第 \(i\) 个数字 \(x_i\)，比它大的同类数字恰好就是后面的那些，因此
$$P(x_i)=V(c)-i.$$
把整个类的贡献加总，得到
$$\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}.$$
这说明：一个类对 \(S(k)\) 的贡献，恰好等于这个类内部不同合法排列能组成的无序数字对数量。
把所有数字重数向量的贡献加在一起，就得到
$$\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}.}$$
程序实现的正是这个公式。它完全不需要把同一类中的排列两两比较，因为整类的总贡献已经能从数字出现次数直接算出来。
实现把 \(S(3)=1701\) 当作一个小规模校验。对于 \(k=3\)，相关的模式族可以整理为
$$\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}$$
这里 \(a,b,c\) 表示非零数字，并在需要时互不相同。对应的类数分别是 \(9\)、\(9\)、\(72=9\cdot 8\)、\(36=\binom{9}{2}\) 和 \(84=\binom{9}{3}\)。于是各模式族的总贡献分别为 \(0\)、\(0\)、\(9\)、\(216\)、\(216\) 和 \(1260\)，从而
$$S(3)=9+216+216+1260=1701.$$
C++、Python 和 Java 实现遵循完全相同的组合思路。第一步先预计算到 \(k\) 为止的阶乘，因为每个类都要用到多项式系数分母中的 \(c_0!\cdots c_9!\)。接着用深度优先搜索枚举十个数字的出现次数：先给数字 \(0\) 到 \(8\) 分配数量，剩余的数量自动归到数字 \(9\)。这样每个满足总和为 \(k\) 的向量都会被访问且只访问一次。
在搜索树的每个叶子上，实现先计算 \(A(c)=k!/\prod c_d!\)，再转成合法类大小 \(V(c)=A(c)(k-c_0)/k\)，最后把 \(\binom{V(c)}{2}\) 加入总答案。三种语言版本的差别只在整数类型的细节处理上，核心算法步骤完全一致。
数字计数向量一共有 \(\binom{k+9}{9}\) 个，每个向量只需要 \(O(10)\) 次算术操作。阶乘预处理需要 \(O(k)\) 时间。因此总时间复杂度为
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
这里利用了十个数字的字母表是固定常数这一事实。空间复杂度为 \(O(k)\) 的阶乘表，再加上 \(O(10)\) 的计数数组和递归状态。
Для каждого \(k\)-значного числа \(n\) обозначим через \(P(n)\) количество больших \(k\)-значных чисел, которые получаются перестановкой цифр числа \(n\). Нужно вычислить
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
где \(\mathcal{D}_k\) — множество всех \(k\)-значных чисел, то есть ведущий ноль запрещен. Главная идея состоит в том, что важен не исходный порядок цифр, а только то, сколько раз встречается каждая цифра. После группировки по таким кратностям задача превращается в аккуратный комбинаторный подсчет.
Запишем вектор количеств цифр в числе:
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$$
Два \(k\)-значных числа принадлежат одному и тому же классу тогда и только тогда, когда у них одинаковый вектор \(c\). Все допустимые числа внутри такого класса являются перестановками одного и того же мультимножества цифр, поэтому вклад класса зависит только от \(c\).
Выбор вектора \(c\) — это задача типа stars and bars: нужно распределить \(k\) позиций между десятью цифрами \(0,1,\dots,9\). Поэтому число возможных классов равно
$$\binom{k+9}{9}.$$
Реализации не перебирают сами числа. Они перебирают именно такие векторы счетчиков, потому что один вектор сразу описывает целый класс взаимных перестановок.
Для фиксированного вектора \(c\) число строк длины \(k\), которые можно получить перестановкой этого мультимножества, задается мультиномиальным коэффициентом
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
Это число включает и варианты, начинающиеся с \(0\). Такие строки не являются допустимыми \(k\)-значными числами, поэтому требуется отдельная поправка.
Если \(c_0=0\), то все перестановки, учтенные в \(A(c)\), уже допустимы. Если \(c_0>0\), то варианты с ведущим нулем получаются так: один ноль фиксируется на первой позиции, а оставшиеся \(k-1\) мест переставляются:
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
Используя \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\), получаем упрощение
$$Z(c)=A(c)\frac{c_0}{k}.$$
Следовательно, количество допустимых \(k\)-значных чисел в классе равно
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$$
Эта же формула корректна и при \(c_0=0\), потому что поправочный член тогда автоматически равен нулю.
Упорядочим допустимые числа данного класса по возрастанию:
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
Для \(i\)-го числа величина \(P(x_i)\) — это просто количество более поздних элементов того же списка, то есть \(V(c)-i\). Сумма по всему классу равна
$$\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}.$$
Итак, вклад класса равен числу неупорядоченных пар различных допустимых перестановок внутри этого класса.
Складывая вклады всех векторов количеств, получаем
$$\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}.}$$
Именно эта формула реализована в программе. Она вовсе не сравнивает перестановки попарно, потому что весь вклад класса выражается напрямую через кратности цифр.
В реализациях значение \(S(3)=1701\) используется как небольшой контрольный пример. Для \(k=3\) важные семейства шаблонов таковы:
$$\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}$$
Здесь \(a,b,c\) обозначают ненулевые цифры с естественными условиями различия там, где это требуется. Числа классов равны \(9\), \(9\), \(72=9\cdot 8\), \(36=\binom{9}{2}\) и \(84=\binom{9}{3}\). Поэтому суммарные вклады равны \(0\), \(0\), \(9\), \(216\), \(216\) и \(1260\), а значит
$$S(3)=9+216+216+1260=1701.$$
Реализации на C++, Python и Java следуют одному и тому же комбинаторному плану. Сначала они заранее вычисляют факториалы до \(k\), потому что при обработке каждого класса нужен мультиномиальный знаменатель \(c_0!\cdots c_9!\). Затем запускается поиск в глубину по десяти счетчикам цифр: значения назначаются для цифр от \(0\) до \(8\), а оставшееся количество автоматически достается цифре \(9\). Тем самым каждый допустимый вектор посещается ровно один раз.
В каждом листе этого перебора вычисляется \(A(c)=k!/\prod c_d!\), затем из него получается число допустимых элементов класса \(V(c)=A(c)(k-c_0)/k\), после чего в ответ добавляется \(\binom{V(c)}{2}\). Различия между версиями касаются только деталей работы с целыми числами; сам алгоритм везде один и тот же.
Всего существует \(\binom{k+9}{9}\) векторов количеств цифр, и каждый обрабатывается за \(O(10)\) арифметических операций. Предварительный расчет факториалов занимает \(O(k)\) времени. Следовательно, полное время работы равно
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
для фиксированного алфавита из десяти цифр. Память составляет \(O(k)\) для таблицы факториалов и \(O(10)\) для массива счетчиков и состояния рекурсии.
لكل عدد \(n\) مكوّن من \(k\) خانات، نرمز بـ \(P(n)\) إلى عدد الأعداد الأكبر منه والتي لها أيضًا \(k\) خانات ويمكن الحصول عليها بإعادة ترتيب أرقامه. المطلوب هو حساب
$$S(k)=\sum_{n\in\mathcal{D}_k} P(n),$$
حيث تمثل \(\mathcal{D}_k\) مجموعة جميع الأعداد ذات \(k\) خانات، ولذلك لا يُسمح بصفر ابتدائي. الفكرة الأساسية هنا أن ترتيب الأرقام نفسه ليس ما ينبغي عده مباشرة، بل عدد مرات ظهور كل رقم. وعندما نُجَمِّع الأعداد بحسب هذه التكرارات، تتحول المسألة إلى عدّ تركيبي واضح.
لنكتب متجه أعداد مرات ظهور الأرقام على الصورة
$$c=(c_0,c_1,\dots,c_9),\qquad c_d\ge 0,\qquad \sum_{d=0}^{9} c_d = k.$$
ينتمي عددان من \(k\) خانات إلى الفئة نفسها إذا وفقط إذا امتلكا المتجه نفسه \(c\). فجميع الأعداد الصحيحة الصالحة داخل هذه الفئة هي تبديلات للمجموعة المتعددة نفسها من الأرقام، ولذلك فإن مساهمة الفئة تعتمد على \(c\) وحده.
اختيار المتجه \(c\) هو مسألة من نوع stars and bars: نوزع \(k\) خانات على القيم العشر \(0,1,\dots,9\). لذلك يكون عدد الفئات الممكنة مساويًا لـ
$$\binom{k+9}{9}.$$
التنفيذات لا تستعرض الأعداد واحدًا واحدًا، بل تستعرض متجهات العد هذه، لأن متجهًا واحدًا يصف دفعة واحدة فئة كاملة من الأعداد المتبادلة بالترتيب.
عند تثبيت متجه معين \(c\)، فإن عدد السلاسل ذات الطول \(k\) التي يمكن تكوينها من هذا المتعدد من الأرقام يُعطى بالمعامل متعدد الحدود
$$A(c)=\frac{k!}{\prod_{d=0}^{9} c_d!}.$$
هذا العدد يشمل كل الترتيبات الممكنة، ومنها الترتيبات التي تبدأ بصفر. وتلك الترتيبات ليست أعدادًا صحيحة صالحة من \(k\) خانات، لذا نحتاج إلى طرحها لاحقًا.
إذا كان \(c_0=0\)، فكل ما يعده \(A(c)\) صالح أصلًا. أما إذا كان \(c_0>0\)، فإن الترتيبات التي تبدأ بصفر تُحسب بتثبيت صفر واحد في الخانة الأولى، ثم إعادة ترتيب الخانات \(k-1\) المتبقية:
$$Z(c)=\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^{9} c_d!}.$$
وباستخدام العلاقة \(A(c)=\dfrac{k!}{c_0!\prod_{d=1}^{9} c_d!}\) نحصل على التبسيط
$$Z(c)=A(c)\frac{c_0}{k}.$$
ومن ثم فإن عدد الأعداد الصحيحة الصالحة ذات \(k\) خانات داخل الفئة هو
$$V(c)=A(c)-Z(c)=A(c)\frac{k-c_0}{k}.$$
وتظل هذه الصيغة صحيحة حتى عندما يكون \(c_0=0\)، لأن حد التصحيح يساوي الصفر تلقائيًا.
لنرتب الأعداد الصالحة داخل فئة واحدة ترتيبًا تصاعديًا:
$$x_1\lt x_2\lt\cdots\lt x_{V(c)}.$$
بالنسبة إلى العدد \(x_i\)، فإن \(P(x_i)\) يساوي تمامًا عدد العناصر التي تأتي بعده في هذه القائمة، أي \(V(c)-i\). وعند جمع ذلك على كامل الفئة نحصل على
$$\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}.$$
إذن مساهمة كل فئة هي عدد الأزواج غير المرتبة من التبديلات الصالحة المختلفة داخل هذه الفئة.
بجمع مساهمات جميع متجهات العد نحصل على
$$\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}.}$$
وهذه هي الصيغة نفسها التي تطبقها الشيفرة. فلا توجد حاجة إلى مقارنة التبديلات واحدًا واحدًا، لأن مساهمة الفئة كلها معروفة مباشرة من تكرارات الأرقام.
تستخدم التنفيذات القيمة \(S(3)=1701\) كنقطة تحقق صغيرة. عندما يكون \(k=3\)، تكون عائلات الأنماط المهمة كما يلي:
$$\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}$$
هنا تمثل \(a,b,c\) أرقامًا غير صفرية، مع شروط الاختلاف المعتادة عند الحاجة. أعداد الفئات المقابلة هي \(9\) و\(9\) و\(72=9\cdot 8\) و\(36=\binom{9}{2}\) و\(84=\binom{9}{3}\). لذلك تكون المساهمات الكلية \(0\) و\(0\) و\(9\) و\(216\) و\(216\) و\(1260\)، ومن ثم
$$S(3)=9+216+216+1260=1701.$$
تتبع تنفيذات C++ وPython وJava الخطة التركيبية نفسها. أولًا تُحسب القيم العاملية حتى \(k\) مسبقًا، لأن تقييم كل فئة يحتاج إلى المقام متعدد الحدود \(c_0!\cdots c_9!\). بعد ذلك يجري تعداد بعمق أول لمقادير الأرقام العشرة: تُسند القيم للأرقام من \(0\) إلى \(8\)، ثم تُعطى الكمية المتبقية تلقائيًا للرقم \(9\). وبهذا تُزار كل حالة مسموحة مرة واحدة فقط.
عند كل ورقة في هذا التعداد، تحسب الشيفرة \(A(c)=k!/\prod c_d!\)، ثم تحوله إلى حجم الفئة الصالح \(V(c)=A(c)(k-c_0)/k\)، وبعدها تضيف \(\binom{V(c)}{2}\) إلى المجموع الكلي. الفروق بين اللغات هنا تقتصر على تفاصيل أنواع الأعداد الصحيحة، أما الخطوات الخوارزمية نفسها فهي واحدة.
يوجد بالضبط \(\binom{k+9}{9}\) متجهًا ممكنًا للعد، ويُعالج كل واحد منها باستخدام \(O(10)\) عمليات حسابية. أما الحساب المسبق للعوامل فيكلف \(O(k)\) زمنًا. لذلك يكون الزمن الكلي
$$O\left(k + 10\binom{k+9}{9}\right)=O\left(\binom{k+9}{9}\right)$$
مع اعتبار أن مجموعة الأرقام العشر ثابتة. ويبلغ استهلاك الذاكرة \(O(k)\) لجدول العوامل و\(O(10)\) لمصفوفة العد وحالة الاستدعاء العودي.