Let \(p(n)\) be the number of length-\(n\) strings formed from an ordered alphabet of size \(26\), with no repeated letters, such that there is exactly one index \(i\) for which the next character is larger: \(s_i \lt s_{i+1}\).
The task is to determine
$$\max_{1 \le n \le 26} p(n).$$
The implementations use a closed counting formula rather than generating strings. For the standard \(26\)-letter alphabet, the maximum occurs at \(n=18\) and equals \(409511334375\).
The problem separates naturally into two pieces: choose which letters appear, then count how many relative orders of those letters contain exactly one ascent.
Suppose we choose any \(n\) distinct letters from the alphabet and list them in increasing order as \(L_1 \lt L_2 \lt \cdots \lt L_n\). Replacing \(L_j\) by \(j\) preserves every comparison between adjacent characters, so the actual letter names are irrelevant once the set of letters is fixed.
Therefore, if \(a(n)\) denotes the number of permutations \(\pi_1\pi_2\cdots\pi_n\) of \(\{1,2,\dots,n\}\) with exactly one ascent, then
$$p(n)=\binom{26}{n}a(n).$$
The entire problem is now reduced to finding \(a(n)\).
Assume the unique ascent occurs between positions \(k\) and \(k+1\), so
$$\pi_k \lt \pi_{k+1}.$$
Then every adjacent pair before position \(k\) must be decreasing, and every adjacent pair after position \(k+1\) must also be decreasing. Otherwise we would create a second ascent. So every valid permutation has the shape
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Equivalently, the permutation is obtained by splitting the set \(\{1,\dots,n\}\) into two nonempty parts:
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
then writing all elements of \(A\) in decreasing order, followed by all elements of \(B\) in decreasing order. Inside each block the order is forced, so the only remaining question is whether the boundary between the two blocks is really an ascent.
There are \(2^n-2\) ways to choose a nonempty proper subset \(A\), with \(B\) determined as its complement. For a given split, the boundary comparison is
$$\min(A) \lt \max(B).$$
This fails exactly when every element of \(A\) is larger than every element of \(B\). In that case the permutation is globally decreasing and has no ascent at all. The only such bad splits are
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1,$$
so there are precisely \(n-1\) of them. Hence
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
This is also the Eulerian count for permutations with exactly one ascent.
Take \(n=4\). Choose \(A=\{4,2\}\) and \(B=\{3,1\}\). Writing both blocks in decreasing order gives
$$4,2,3,1,$$
and the adjacent comparisons are \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\), so there is exactly one ascent.
By contrast, if \(A=\{4,3\}\) and \(B=\{2,1\}\), the resulting permutation is
$$4,3,2,1,$$
which has no ascent. This is one of the \(n-1\) excluded splits. For \(n=3\), the formula gives \(a(3)=2^3-3-1=4\), so
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
which is exactly the checkpoint value used by the implementation.
Putting the two factors together gives the formula actually evaluated by the code:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
More generally, for an ordered alphabet of size \(m\),
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
The last step is not another combinatorial derivation: the implementations simply evaluate this expression for every admissible \(n\) and keep the largest value. For \(m=26\), the maximizing length is \(18\).
The C++, Python, and Java implementations all follow the same short pipeline. For each \(n\) from \(1\) to \(26\), they compute the binomial factor \(\binom{26}{n}\), compute the one-ascent factor \(2^n-n-1\), multiply the two to obtain \(p(n)\), and update a running maximum.
None of the implementations generate strings or permutations explicitly. The whole point of the mathematical reduction is that the exponential search space collapses to \(26\) direct evaluations of a closed form.
The C++ and Java versions build the binomial coefficient multiplicatively and use the symmetry \(\binom{n}{k}=\binom{n}{n-k}\) to keep the loop short. The Python version relies on exact integer binomial arithmetic from the standard library. The C++ version also allows the alphabet size to be overridden and includes the sanity check \(p(3)=10400\).
For a general alphabet size \(m\), evaluating one value \(p(n)\) with a multiplicative binomial computation costs \(O(\min(n,m-n))\) time and \(O(1)\) extra space. Sweeping over all \(n=1,2,\dots,m\) therefore costs \(O(m^2)\) time in the direct implementation strategy used here.
For the actual problem size \(m=26\), this is tiny. The important qualitative point is that the algorithm never touches the \(\binom{26}{n}n!\) candidate strings themselves; it counts them symbolically.
Sei \(p(n)\) die Anzahl der Strings der Länge \(n\), die aus einem geordneten Alphabet mit \(26\) Buchstaben gebildet werden, keine Wiederholungen enthalten und genau eine Stelle \(i\) besitzen, an der der nächste Buchstabe größer ist: \(s_i \lt s_{i+1}\).
Gesucht ist also
$$\max_{1 \le n \le 26} p(n).$$
Die Implementierungen erzeugen keine Strings direkt, sondern verwenden eine geschlossene Zählformel. Für das Standardalphabet mit \(26\) Buchstaben liegt das Maximum bei \(n=18\) und hat den Wert \(409511334375\).
Die Zählung zerfällt in zwei klar getrennte Teile: Zuerst wählt man die vorkommenden Buchstaben aus, danach zählt man die relativen Anordnungen dieser Buchstaben mit genau einem Anstieg.
Wähle beliebige \(n\) verschiedene Buchstaben und ordne sie als \(L_1 \lt L_2 \lt \cdots \lt L_n\). Wenn man \(L_j\) durch \(j\) ersetzt, bleiben alle Vergleichsaussagen zwischen benachbarten Zeichen erhalten. Sobald also die Menge der verwendeten Buchstaben feststeht, spielt ihre konkrete Bezeichnung keine Rolle mehr.
Bezeichne mit \(a(n)\) die Anzahl der Permutationen \(\pi_1\pi_2\cdots\pi_n\) von \(\{1,2,\dots,n\}\), die genau einen Anstieg besitzen. Dann gilt sofort
$$p(n)=\binom{26}{n}a(n).$$
Damit bleibt nur noch die Bestimmung von \(a(n)\).
Liegt der eindeutige Anstieg zwischen den Positionen \(k\) und \(k+1\), dann ist
$$\pi_k \lt \pi_{k+1}.$$
Vor dieser Stelle dürfen keine weiteren Anstiege auftreten, also muss \(\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k\) gelten. Genauso muss nach der Stelle \(k+1\) alles streng fallen. Jede gültige Permutation hat daher die Form
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Das bedeutet: Man zerlegt die Menge \(\{1,\dots,n\}\) in zwei nichtleere Teile
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
schreibt die Elemente von \(A\) in absteigender Reihenfolge und danach die Elemente von \(B\) ebenfalls in absteigender Reihenfolge. Innerhalb der beiden Blöcke ist die Reihenfolge also vollständig festgelegt; offen bleibt nur, ob an der Blockgrenze wirklich ein Anstieg entsteht.
Für die linke Blockmenge \(A\) gibt es \(2^n-2\) nichtleere echte Teilmengen. Zu jeder davon gehört \(B\) als Komplement. Die Grenzbedingung lautet
$$\min(A) \lt \max(B).$$
Sie schlägt genau dann fehl, wenn jedes Element aus \(A\) größer ist als jedes Element aus \(B\). Dann ist die gesamte Permutation streng fallend und besitzt überhaupt keinen Anstieg. Die einzigen verbotenen Fälle sind deshalb
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
Davon gibt es genau \(n-1\). Also folgt
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
Dieser Wert ist zugleich die Euler-Zahl für Permutationen mit genau einem Anstieg.
Nimm \(n=4\). Wähle \(A=\{4,2\}\) und \(B=\{3,1\}\). Die erzwungene Anordnung lautet dann
$$4,2,3,1.$$
Die Nachbarvergleiche sind \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\); also gibt es genau einen Anstieg.
Wählt man dagegen \(A=\{4,3\}\) und \(B=\{2,1\}\), erhält man
$$4,3,2,1,$$
und damit keinen Anstieg. Das ist einer der \(n-1\) verbotenen Fälle. Für \(n=3\) liefert die Formel \(a(3)=2^3-3-1=4\), also
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
genau der Kontrollwert, den die Implementierung überprüft.
Setzt man beide Faktoren zusammen, erhält man genau den Ausdruck, den der Code auswertet:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
Allgemeiner gilt für ein geordnetes Alphabet der Größe \(m\):
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
Der letzte Schritt ist dann rein numerisch: Für alle zulässigen \(n\) wird dieser Wert berechnet und das Maximum gespeichert. Beim Fall \(m=26\) wird das Maximum bei \(n=18\) erreicht.
Die C++-, Python- und Java-Implementierungen folgen demselben einfachen Ablauf. Für jedes \(n\) von \(1\) bis \(26\) berechnen sie zunächst den Binomialfaktor \(\binom{26}{n}\), dann den Faktor \(2^n-n-1\) für genau einen Anstieg, multiplizieren beides zu \(p(n)\) und aktualisieren anschließend das bisherige Maximum.
Es werden also weder alle Strings noch alle Permutationen erzeugt. Gerade darin liegt der entscheidende Vorteil der mathematischen Herleitung: Ein kombinatorisches Problem mit riesigem Suchraum wird auf nur \(26\) direkte Auswertungen einer geschlossenen Formel reduziert.
Die C++- und Java-Versionen berechnen den Binomialkoeffizienten multiplikativ und nutzen die Symmetrie \(\binom{n}{k}=\binom{n}{n-k}\), um möglichst wenige Schleifendurchläufe zu benötigen. Die Python-Version verwendet eine exakte Standardbibliotheksfunktion für Kombinationen. Zusätzlich kann die C++-Version die Alphabetgröße als Eingabe übernehmen und prüft den Sanity-Check \(p(3)=10400\).
Für eine allgemeine Alphabetgröße \(m\) kostet die Auswertung eines einzelnen \(p(n)\) bei multiplikativer Berechnung von \(\binom{m}{n}\) eine Laufzeit von \(O(\min(n,m-n))\) und \(O(1)\) zusätzlichen Speicher. Der vollständige Durchlauf über alle \(n=1,2,\dots,m\) benötigt damit in dieser direkten Implementationsform \(O(m^2)\) Zeit.
Für die eigentliche Aufgabenstellung mit \(m=26\) ist das praktisch sofort erledigt. Inhaltlich wichtiger ist: Der Algorithmus berührt nie die \(\binom{26}{n}n!\) konkreten Kandidatenstrings, sondern zählt sie symbolisch.
\(p(n)\), \(26\) harfli sıralı bir alfabeden seçilen, tekrar içermeyen uzunluk-\(n\) diziler arasında tam olarak bir tane \(s_i \lt s_{i+1}\) koşulu sağlayanların sayısı olsun. Yani komşu iki harf arasında yalnızca bir kez soldan sağa artış görülür.
Aranan değer
$$\max_{1 \le n \le 26} p(n)$$
ifadesidir. Uygulamalar bu değeri dizileri tek tek üretmeden bulur. Standart \(26\) harfli durumda maksimum \(n=18\) için oluşur ve değer \(409511334375\) olur.
Sayımı iki doğal adıma ayırmak mümkündür: önce hangi harflerin kullanılacağını seçeriz, sonra seçilen bu harflerin göreli sıraları arasından tam bir yükseliş içerenleri sayarız.
Diyelim ki seçilen \(n\) harf artan sırada
$$L_1 \lt L_2 \lt \cdots \lt L_n$$
olsun. Her \(L_j\) harfini \(j\) sayısına eşlersek komşu öğeler arasındaki tüm büyüklük karşılaştırmaları aynen korunur. Demek ki kullanılan harf kümesi sabitlendikten sonra asıl önemli olan harflerin isimleri değil, göreli sıralarıdır.
Bu nedenle \(\{1,2,\dots,n\}\) kümesinin tam olarak bir yükseliş içeren permütasyonlarının sayısını \(a(n)\) ile gösterirsek
$$p(n)=\binom{26}{n}a(n)$$
olur. Sorunun özü artık \(a(n)\) değerini bulmaktır.
Tek yükselişin \(k\) ile \(k+1\). konumlar arasında olduğunu varsayalım:
$$\pi_k \lt \pi_{k+1}.$$
Bundan önce başka yükseliş olamaz; dolayısıyla sol tarafta
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k$$
olmalıdır. Aynı şekilde sağ tarafta da
$$\pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n$$
geçerlidir. Yani her geçerli permütasyon aslında iki azalan koşunun birleşimidir:
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Bu da şu eşdeğer yorumu verir: \(\{1,\dots,n\}\) kümesini iki boş olmayan parçaya ayırırız,
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
sonra \(A\)'yı azalan, ardından \(B\)'yi azalan yazarız. Blokların iç sırası otomatik olarak belirlenmiştir; denetlenmesi gereken tek şey sınırdaki karşılaştırmadır.
Sol blok için seçilebilecek boş olmayan gerçek altküme sayısı \(2^n-2\)'dir. \(A\) seçildiğinde \(B\) tamamlayanı olarak belirlenir. Sınırda gerçekten bir yükseliş olması için gereken koşul
$$\min(A) \lt \max(B)$$
şeklindedir. Bu koşul yalnızca \(A\)'daki her eleman \(B\)'deki her elemandan büyük olduğunda bozulur. O durumda oluşan permütasyon bütünüyle azalan olur ve hiç yükseliş içermez.
Bu kötü durumlar tam olarak şunlardır:
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
Bunlardan \(n-1\) tane vardır. Dolayısıyla
$$a(n)=(2^n-2)-(n-1)=2^n-n-1$$
elde edilir. Bu sayı aynı zamanda tam bir yükseliş içeren permütasyonların Eulerian sayısıdır.
\(n=4\) için \(A=\{4,2\}\) ve \(B=\{3,1\}\) seçelim. Azalan blokları birleştirince
$$4,2,3,1$$
elde edilir. Karşılaştırmalar \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\) olduğundan tam bir yükseliş vardır.
Buna karşılık \(A=\{4,3\}\), \(B=\{2,1\}\) seçilirse
$$4,3,2,1$$
oluşur ve hiç yükseliş kalmaz. Bu, çıkarılan \(n-1\) kötü bölmeden biridir. Ayrıca \(n=3\) için \(a(3)=2^3-3-1=4\) bulunduğundan
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
ki bu da uygulamadaki kontrol değeridir.
İki çarpanı birleştirince kodun doğrudan kullandığı formül çıkar:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
Daha genel olarak alfabetik boyut \(m\) ise
$$p_m(n)=\binom{m}{n}(2^n-n-1)$$
olur. Bundan sonrası yeni bir türetim değil, basit bir taramadır: izin verilen tüm \(n\) değerleri için bu ifade hesaplanır ve en büyüğü tutulur. \(m=26\) için en iyi uzunluk \(18\)'dir.
C++, Python ve Java uygulamaları aynı kısa akışı izler. \(1\) ile \(26\) arasındaki her \(n\) için önce \(\binom{26}{n}\) hesaplanır, sonra tek yükseliş faktörü olan \(2^n-n-1\) bulunur, bu iki değer çarpılarak \(p(n)\) elde edilir ve eldeki maksimum güncellenir.
Hiçbir uygulama dizileri ya da permütasyonları tek tek üretmez. Matematiksel indirgeme sayesinde üstel büyüklükte bir arama uzayı, kapalı formülün sadece \(26\) kez değerlendirilmesine dönüşür.
C++ ve Java sürümleri binom katsayısını çarpımsal biçimde hesaplar ve \(\binom{n}{k}=\binom{n}{n-k}\) simetrisini kullanarak döngüyü kısaltır. Python sürümü ise standart kütüphanedeki tam sayı kombinasyon hesabını kullanır. C++ sürümünde ayrıca alfabe boyutu isteğe bağlı olarak değiştirilebilir ve \(p(3)=10400\) eşitliğiyle küçük bir doğrulama yapılır.
Genel alfabe boyutu \(m\) için, tek bir \(p(n)\) değerini çarpımsal binom hesabıyla bulmak \(O(\min(n,m-n))\) zaman ve \(O(1)\) ek bellek gerektirir. \(n=1,2,\dots,m\) aralığının tamamını taramak bu nedenle burada kullanılan doğrudan yaklaşımda \(O(m^2)\) zaman alır.
Gerçek problemde \(m=26\) olduğu için bu maliyet çok küçüktür. Asıl önemli nokta, algoritmanın \(\binom{26}{n}n!\) kadar aday diziyi dolaşmak yerine onları sembolik olarak saymasıdır.
Sea \(p(n)\) el número de cadenas de longitud \(n\) tomadas de un alfabeto ordenado de \(26\) letras, sin repeticiones, tales que existe exactamente un índice \(i\) con
$$s_i \lt s_{i+1}.$$
Es decir, entre todos los pares adyacentes hay una sola subida lexicográfica. Se pide calcular
$$\max_{1 \le n \le 26} p(n).$$
Las implementaciones no generan las cadenas una por una, sino que usan una fórmula cerrada. Para el alfabeto usual de \(26\) letras, el máximo aparece en \(n=18\) y vale \(409511334375\).
La cuenta se separa de forma natural en dos preguntas: qué letras aparecen y, fijadas esas letras, en cuántos órdenes relativos hay exactamente una subida.
Supongamos que las \(n\) letras elegidas son
$$L_1 \lt L_2 \lt \cdots \lt L_n.$$
Si sustituimos \(L_j\) por \(j\), todas las comparaciones entre caracteres vecinos se conservan. Por tanto, una vez fijado el conjunto de letras, sus nombres concretos ya no importan: solo importa el orden relativo.
Si llamamos \(a(n)\) al número de permutaciones \(\pi_1\pi_2\cdots\pi_n\) de \(\{1,2,\dots,n\}\) con exactamente una subida, entonces
$$p(n)=\binom{26}{n}a(n).$$
El problema se reduce así a calcular \(a(n)\).
Supongamos que la única subida está entre las posiciones \(k\) y \(k+1\):
$$\pi_k \lt \pi_{k+1}.$$
Antes de esa frontera no puede haber ninguna otra subida, así que debe cumplirse
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k.$$
Después de la frontera ocurre lo mismo:
$$\pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Toda permutación válida tiene entonces la forma
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Dicho de otra manera: partimos \(\{1,\dots,n\}\) en dos subconjuntos no vacíos,
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
escribimos todos los elementos de \(A\) en orden decreciente y luego todos los de \(B\), también en orden decreciente. Dentro de cada bloque no hay libertad; la única cuestión es si en la frontera aparece realmente la subida deseada.
Hay \(2^n-2\) maneras de escoger un subconjunto propio y no vacío \(A\); el conjunto \(B\) queda determinado como complemento. La condición de que la frontera sea una subida es
$$\min(A) \lt \max(B).$$
Esta condición falla exactamente cuando todo elemento de \(A\) es mayor que todo elemento de \(B\). En ese caso la permutación completa queda totalmente decreciente y no contiene ninguna subida. Los únicos casos prohibidos son
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
Hay exactamente \(n-1\) particiones de ese tipo. Por lo tanto,
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
Este valor coincide con el número euleriano que cuenta permutaciones con una sola subida.
Tomemos \(n=4\). Si elegimos \(A=\{4,2\}\) y \(B=\{3,1\}\), la construcción forzada produce
$$4,2,3,1.$$
Las comparaciones adyacentes son \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\), así que aparece exactamente una subida.
En cambio, si \(A=\{4,3\}\) y \(B=\{2,1\}\), obtenemos
$$4,3,2,1,$$
que no tiene ninguna subida. Ese es uno de los \(n-1\) casos excluidos. Para \(n=3\), la fórmula da \(a(3)=2^3-3-1=4\), y por tanto
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
justo el valor de comprobación usado por la implementación.
Al reunir los dos factores aparece exactamente la expresión que evalúa el código:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
Más generalmente, si el alfabeto ordenado tiene tamaño \(m\), entonces
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
El último paso ya no requiere ninguna idea adicional: se evalúa esta fórmula para todos los \(n\) posibles y se conserva el mayor valor. En el caso \(m=26\), el mejor \(n\) es \(18\).
Las implementaciones en C++, Python y Java siguen la misma estrategia. Recorren \(n=1,2,\dots,26\), calculan \(\binom{26}{n}\), calculan el factor \(2^n-n-1\) correspondiente a una única subida, multiplican ambos términos para obtener \(p(n)\) y actualizan un máximo acumulado.
No se construyen ni las cadenas ni las permutaciones de forma explícita. Ese es el beneficio central de la derivación matemática: un espacio de búsqueda enorme queda reemplazado por \(26\) evaluaciones exactas de una fórmula cerrada.
Las versiones en C++ y Java calculan el coeficiente binomial de forma multiplicativa y aprovechan la simetría \(\binom{n}{k}=\binom{n}{n-k}\) para reducir el número de iteraciones. La versión en Python usa aritmética exacta de combinaciones de la biblioteca estándar. Además, la versión en C++ permite cambiar el tamaño del alfabeto y verifica el caso de control \(p(3)=10400\).
Para un alfabeto general de tamaño \(m\), calcular un solo valor \(p(n)\) con un binomio multiplicativo cuesta \(O(\min(n,m-n))\) tiempo y \(O(1)\) memoria extra. Recorrer todos los valores \(n=1,2,\dots,m\) conduce por tanto a \(O(m^2)\) tiempo en el enfoque directo usado por estas implementaciones.
Para el tamaño real del problema, \(m=26\), el coste es minúsculo. Lo importante es que el algoritmo nunca toca los \(\binom{26}{n}n!\) candidatos de forma explícita; los cuenta de manera simbólica.
设 \(p(n)\) 表示这样一类长度为 \(n\) 的字符串数量：它们从一个有序的 \(26\) 字母字母表中取出，字符互不重复，并且在所有相邻位置里，恰好只有一个位置满足后一个字符比前一个字符大，也就是
$$s_i \lt s_{i+1}.$$
题目要求计算
$$\max_{1 \le n \le 26} p(n).$$
实现并不会枚举所有字符串，而是先把问题化成一个封闭公式再逐个 \(n\) 计算。对于标准的 \(26\) 字母情形，最大值在 \(n=18\) 处取得，结果为 \(409511334375\)。
这个问题最自然的拆分方式是：先决定用了哪些字母，再统计这些字母的相对排列中，恰好只有一次“上升”的情况有多少种。
假设选出的 \(n\) 个不同字母按字典序排列为
$$L_1 \lt L_2 \lt \cdots \lt L_n.$$
如果把 \(L_j\) 统一替换成数字 \(j\)，那么任意两个相邻字符之间的大小关系都完全不变。因此，一旦字母集合已经选定，真正影响计数的并不是字母本身，而只是它们的相对次序。
于是可以定义 \(a(n)\) 为集合 \(\{1,2,\dots,n\}\) 的所有排列中，恰好有一次上升的排列数。那么原题就变成
$$p(n)=\binom{26}{n}a(n).$$
换句话说，问题的核心只剩下：如何求 \(a(n)\)。
设唯一的一次上升发生在位置 \(k\) 和 \(k+1\) 之间，也就是
$$\pi_k \lt \pi_{k+1}.$$
那么在位置 \(k\) 之前绝不允许再出现上升，否则总上升次数就会超过 \(1\)。因此左半段必须严格递减：
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k.$$
同理，在位置 \(k+1\) 之后也不能再出现上升，所以右半段也必须严格递减：
$$\pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
这说明每一个合法排列都具有统一的形状：
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
也可以换一种更适合计数的说法：把 \(\{1,\dots,n\}\) 划分成两个非空部分
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
然后把 \(A\) 中元素按降序写出来，再把 \(B\) 中元素按降序写出来。因为每个块内部都必须下降，所以块内顺序已经被唯一确定；唯一需要检查的，就是两个块交界处到底是不是上升。
左块 \(A\) 可以是任意非空真子集，所以一共有 \(2^n-2\) 种选择，右块 \(B\) 自动就是补集。对某一个固定划分来说，边界处是上升当且仅当
$$\min(A) \lt \max(B).$$
什么时候这个条件会失败？只有当 \(A\) 中每个元素都比 \(B\) 中每个元素大时才会失败。那样拼出来的排列整体就是完全递减的，因此根本没有上升。
而这种坏划分恰好只有下面这些：
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
它们的数量正好是 \(n-1\)。因此，合法排列数为
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
这个数也正是“恰好一次上升”对应的 Eulerian 数。
取 \(n=4\)。如果选择
$$A=\{4,2\}, \qquad B=\{3,1\},$$
那么按每块内部降序排列后得到
$$4,2,3,1.$$
相邻比较依次为 \(4 \gt 2\)、\(2 \lt 3\)、\(3 \gt 1\)，因此恰好有一次上升。
反过来，如果选择
$$A=\{4,3\}, \qquad B=\{2,1\},$$
得到的就是
$$4,3,2,1,$$
这时没有任何上升，所以它属于前面要扣掉的坏划分。再看一个程序里实际用到的检查点：当 \(n=3\) 时，
$$a(3)=2^3-3-1=4,$$
于是
$$p(3)=\binom{26}{3}\cdot 4=10400.$$
这个值正好能验证公式和实现是一致的。
把“选字母”和“排顺序”两个因素合并，就得到代码直接计算的公式：
$$p(n)=\binom{26}{n}(2^n-n-1).$$
如果字母表大小一般化为 \(m\)，则对应公式是
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
到这里就不再需要新的组合技巧了。实现只要把所有允许的 \(n\) 从 \(1\) 到 \(m\) 扫一遍，算出每个 \(p_m(n)\)，保存其中最大者即可。对于本题的 \(m=26\)，最优长度是 \(18\)。
C++、Python 和 Java 三个实现的结构几乎完全一致。它们都从 \(n=1\) 枚举到 \(26\)，先计算组合数 \(\binom{26}{n}\)，再计算“恰好一次上升”的因子 \(2^n-n-1\)，两者相乘得到 \(p(n)\)，然后更新当前最大值。
实现过程中完全不会显式生成字符串，更不会枚举所有排列。数学推导的价值就在这里：原本看起来像是指数级甚至阶乘级的搜索，被压缩成了极少量的整数运算。
C++ 和 Java 版本用乘法连乘的方式计算组合数，并利用 \(\binom{n}{k}=\binom{n}{n-k}\) 这一对称性缩短循环。Python 版本直接调用标准库中的精确组合数运算。C++ 版本还允许把字母表大小改成其他值，并额外检查 \(p(3)=10400\) 这个已知结果。
若把字母表大小记为一般的 \(m\)，那么用乘法公式计算单个 \(\binom{m}{n}\) 需要 \(O(\min(n,m-n))\) 时间和 \(O(1)\) 额外空间。因此把所有 \(n=1,2,\dots,m\) 都扫一遍，总时间复杂度就是这里实现所体现的 \(O(m^2)\)。
对于本题的 \(m=26\)，这个代价几乎可以忽略。更重要的是，算法从头到尾都没有接触 \(\binom{26}{n}n!\) 个候选字符串本身，而是直接对它们做组合计数。
Пусть \(p(n)\) обозначает число строк длины \(n\), составленных из упорядоченного алфавита из \(26\) букв без повторений, для которых существует ровно один индекс \(i\), такой что следующий символ больше предыдущего:
$$s_i \lt s_{i+1}.$$
Иными словами, среди всех соседних пар есть ровно один лексикографический подъем. Требуется найти
$$\max_{1 \le n \le 26} p(n).$$
Во всех реализациях используется не перебор строк, а готовая комбинаторная формула. Для стандартного алфавита из \(26\) букв максимум достигается при \(n=18\) и равен \(409511334375\).
Подсчет удобно разбить на две независимые части: сначала выбрать сами буквы, а затем посчитать, сколько относительных порядков этих букв дают ровно один подъем.
Пусть выбранные \(n\) букв в возрастающем порядке записаны как
$$L_1 \lt L_2 \lt \cdots \lt L_n.$$
Если заменить \(L_j\) на число \(j\), то все сравнения между соседними символами сохраняются. Значит, после выбора множества букв их конкретные имена уже не важны; важен только относительный порядок.
Обозначим через \(a(n)\) число перестановок \(\pi_1\pi_2\cdots\pi_n\) множества \(\{1,2,\dots,n\}\), в которых есть ровно один подъем. Тогда
$$p(n)=\binom{26}{n}a(n).$$
Вся задача сводится к вычислению \(a(n)\).
Пусть единственный подъем расположен между позициями \(k\) и \(k+1\), то есть
$$\pi_k \lt \pi_{k+1}.$$
До этой границы новых подъемов быть не может, поэтому левая часть обязана строго убывать:
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k.$$
После границы ситуация такая же, и правая часть тоже строго убывает:
$$\pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Следовательно, каждая допустимая перестановка имеет вид
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
Это можно переформулировать как разбиение множества \(\{1,\dots,n\}\) на две непустые части
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
после чего элементы \(A\) записываются в убывающем порядке, а затем в убывающем порядке записываются элементы \(B\). Внутри каждого блока порядок уже однозначен; остается проверить только знак на границе между блоками.
Непустое собственное подмножество \(A\) можно выбрать \(2^n-2\) способами, а \(B\) тогда определяется как дополнение. Чтобы на границе действительно был подъем, нужно и достаточно, чтобы
$$\min(A) \lt \max(B).$$
Это условие нарушается ровно тогда, когда каждый элемент \(A\) больше любого элемента \(B\). Тогда вся перестановка оказывается полностью убывающей и не содержит подъемов вообще. Единственные плохие разбиения имеют вид
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
Таких случаев ровно \(n-1\). Значит,
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
Это же число можно рассматривать как эйлерово число для перестановок с одним подъемом.
Пусть \(n=4\). Возьмем
$$A=\{4,2\}, \qquad B=\{3,1\}.$$
Тогда принудительная запись блоков по убыванию дает перестановку
$$4,2,3,1.$$
Соседние сравнения равны \(4 \gt 2\), \(2 \lt 3\), \(3 \gt 1\), то есть подъем ровно один.
Если же выбрать
$$A=\{4,3\}, \qquad B=\{2,1\},$$
то получится
$$4,3,2,1,$$
а подъемов не будет вовсе. Это один из \(n-1\) исключенных случаев. Для \(n=3\) формула дает \(a(3)=2^3-3-1=4\), поэтому
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
и именно это значение используется в реализации как контрольный пример.
Соединив выбор букв и подсчет относительных порядков, получаем формулу, которую вычисляет код:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
В общем случае для упорядоченного алфавита размера \(m\) имеем
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
Дальше никакой новой комбинаторики не требуется: нужно просто вычислить это выражение для всех допустимых \(n\) и сохранить наибольшее значение. Для \(m=26\) оптимальная длина равна \(18\).
Реализации на C++, Python и Java устроены одинаково. Они перебирают \(n=1,2,\dots,26\), вычисляют биномиальный множитель \(\binom{26}{n}\), затем фактор \(2^n-n-1\), отвечающий ровно одному подъему, перемножают их и обновляют текущий максимум.
Ни строки, ни перестановки явно не строятся. Именно в этом и состоит выигрыш математического решения: огромный комбинаторный перебор заменяется несколькими десятками точных вычислений с целыми числами.
В версиях на C++ и Java биномиальный коэффициент считается мультипликативно, с использованием симметрии \(\binom{n}{k}=\binom{n}{n-k}\), чтобы уменьшить число шагов цикла. В Python применяется готовая точная функция для сочетаний. Кроме того, версия на C++ позволяет менять размер алфавита и проверяет контрольное равенство \(p(3)=10400\).
Если обозначить размер алфавита через \(m\), то вычисление одного значения \(p(n)\) при мультипликативном подсчете \(\binom{m}{n}\) требует \(O(\min(n,m-n))\) времени и \(O(1)\) дополнительной памяти. Полный проход по всем \(n=1,2,\dots,m\) в таком прямом подходе дает \(O(m^2)\) по времени.
Для реального значения \(m=26\) это ничтожно мало. Ключевой содержательный факт в другом: алгоритм вообще не рассматривает \(\binom{26}{n}n!\) конкретных кандидатов, а считает их напрямую по формуле.
لنعرّف \(p(n)\) بأنه عدد السلاسل ذات الطول \(n\) المكوّنة من أبجدية مرتبة من \(26\) حرفًا، من دون تكرار أي حرف، بحيث يوجد موضع وحيد فقط يتحقق فيه
$$s_i \lt s_{i+1}.$$
أي أن هناك صعودًا لِكْسِيكُوغرافيًا واحدًا فقط بين الأزواج المتجاورة. المطلوب هو حساب
$$\max_{1 \le n \le 26} p(n).$$
التنفيذ لا يَعُدّ السلاسل واحدةً واحدة، بل يعتمد على صيغة مغلقة. وفي حالة الأبجدية القياسية ذات \(26\) حرفًا، يتحقق أكبر مقدار عند \(n=18\)، وتكون قيمته \(409511334375\).
يمكن فصل العد إلى جزأين واضحين: نختار أولًا الحروف التي ستظهر، ثم نعدّ الترتيبات النسبية لهذه الحروف التي تحتوي على صعود واحد بالضبط.
افترض أن الحروف المختارة هي
$$L_1 \lt L_2 \lt \cdots \lt L_n.$$
إذا استبدلنا كل \(L_j\) بالعدد \(j\)، فإن جميع المقارنات بين الحروف المتجاورة تبقى كما هي. لذلك، بعد تثبيت مجموعة الحروف، لا تعود أسماء الحروف مهمة؛ المهم فقط هو ترتيبها النسبي.
إذا رمزنا بـ \(a(n)\) إلى عدد تبديلات المجموعة \(\{1,2,\dots,n\}\) التي تحتوي على صعود واحد فقط، فإننا نحصل على
$$p(n)=\binom{26}{n}a(n).$$
إذن جوهر المسألة هو إيجاد \(a(n)\).
لنفترض أن الصعود الوحيد يقع بين الموضعين \(k\) و\(k+1\)، أي
$$\pi_k \lt \pi_{k+1}.$$
قبل هذه النقطة لا يجوز أن يظهر أي صعود آخر، ولذلك يجب أن يكون الجزء الأيسر متناقصًا تمامًا:
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k.$$
وبالمنطق نفسه، لا يجوز أن يظهر صعود بعد الموضع \(k+1\)، ولذلك يكون الجزء الأيمن أيضًا متناقصًا تمامًا:
$$\pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
إذن كل تبديل صالح يأخذ الصورة
$$\pi_1 \gt \pi_2 \gt \cdots \gt \pi_k \lt \pi_{k+1} \gt \pi_{k+2} \gt \cdots \gt \pi_n.$$
وبصياغة مكافئة، نقسم المجموعة \(\{1,\dots,n\}\) إلى جزأين غير فارغين:
$$A=\{\pi_1,\dots,\pi_k\}, \qquad B=\{\pi_{k+1},\dots,\pi_n\},$$
ثم نكتب عناصر \(A\) بترتيب تنازلي، وبعدها عناصر \(B\) بترتيب تنازلي. ترتيب كل جزء يصبح محددًا قسرًا، ولا يبقى إلا فحص المقارنة على الحد الفاصل بين الجزأين.
عدد الطرق لاختيار جزء أيسر \(A\) يكون \(2^n-2\)، لأن \(A\) يجب أن يكون غير فارغ وغير مساوي للمجموعة كلها. بعد اختيار \(A\)، يتحدد \(B\) بوصفه المتمم. ولكي يكون الحد الفاصل صعودًا فعلًا، يجب أن يتحقق
$$\min(A) \lt \max(B).$$
متى يفشل هذا الشرط؟ يفشل بالضبط عندما يكون كل عنصر في \(A\) أكبر من كل عنصر في \(B\). عندها يصبح التبديل كله متناقصًا، وبالتالي لا يوجد أي صعود أصلًا. والحالات السيئة الوحيدة هي
$$A=\{t+1,t+2,\dots,n\}, \qquad B=\{1,2,\dots,t\}, \qquad 1 \le t \le n-1.$$
وعددها يساوي تمامًا \(n-1\). لذلك
$$a(n)=(2^n-2)-(n-1)=2^n-n-1.$$
وهذا هو أيضًا العدد الأويلري الذي يحصي التبديلات ذات الصعود الواحد.
خذ \(n=4\). إذا اخترنا
$$A=\{4,2\}, \qquad B=\{3,1\},$$
فإن كتابة الجزأين تنازليًا تعطينا
$$4,2,3,1.$$
والمقارنات المتجاورة هي \(4 \gt 2\)، ثم \(2 \lt 3\)، ثم \(3 \gt 1\)، ولذلك يوجد صعود واحد بالضبط.
أما إذا اخترنا
$$A=\{4,3\}, \qquad B=\{2,1\},$$
فنحصل على
$$4,3,2,1,$$
وهنا لا يوجد أي صعود، ولذلك تُستبعد هذه الحالة. كما أن الصيغة تعطي عند \(n=3\)
$$a(3)=2^3-3-1=4,$$
ومن ثم
$$p(3)=\binom{26}{3}\cdot 4=10400,$$
وهي قيمة التحقق الصغيرة التي يستخدمها التنفيذ.
بجمع عامل اختيار الحروف مع عامل ترتيبها نحصل على الصيغة التي تحسبها الشيفرة مباشرة:
$$p(n)=\binom{26}{n}(2^n-n-1).$$
وبصورة أعم، إذا كان حجم الأبجدية المرتبة هو \(m\)، فالصيغة تصبح
$$p_m(n)=\binom{m}{n}(2^n-n-1).$$
بعد ذلك لا توجد حيلة إضافية: يُحسب هذا المقدار لكل \(n\) ممكن، ثم تُحفظ أكبر قيمة. وفي حالة \(m=26\)، يكون الطول الأفضل هو \(18\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تمرّ على جميع القيم \(n=1,2,\dots,26\)، وتحسب أولًا المعامل الثنائي \(\binom{26}{n}\)، ثم تحسب العامل \(2^n-n-1\) الخاص بوجود صعود واحد، وبعد ذلك تضرب العاملين للحصول على \(p(n)\) وتحدّث القيمة العظمى الجارية.
لا يجري توليد أي سلسلة ولا أي تبديل بصورة صريحة. وهذا هو لب الفكرة الرياضية: فضاء بحث هائل ينهار إلى عدد صغير جدًا من حسابات صحيحة مباشرة.
إصدارا C++ وJava يحسبان المعامل الثنائي بطريقة ضرب متتالية، ويستفيدان من التناظر \(\binom{n}{k}=\binom{n}{n-k}\) لتقليل عدد الخطوات. أما إصدار Python فيستخدم دالة دقيقة من المكتبة القياسية لحساب التوافقات. كما أن إصدار C++ يتيح تغيير حجم الأبجدية ويفحص أيضًا القيمة المعروفة \(p(3)=10400\).
إذا رمزنا إلى حجم الأبجدية بـ \(m\)، فإن حساب قيمة واحدة \(p(n)\) باستخدام الصيغة الضربية للمعامل الثنائي يكلّف \(O(\min(n,m-n))\) زمنًا و\(O(1)\) مساحة إضافية. ومن ثم فإن المرور على جميع القيم \(n=1,2,\dots,m\) يعطي تعقيدًا زمنيًا مقداره \(O(m^2)\) في الأسلوب المباشر المستخدم هنا.
في المسألة الفعلية حيث \(m=26\)، تكون الكلفة صغيرة جدًا. والنقطة الأهم أن الخوارزمية لا تلامس أبدًا جميع المرشحات وعددها \(\binom{26}{n}n!\)، بل تعدّها رمزيًا مباشرة.