Start with a uniformly random permutation of \(\{1,2,\dots,n\}\). Whenever adjacent cards form an increasing consecutive run, they are glued into one bundle. The bundles are then shuffled uniformly at random, the gluing rule is applied again, and the process continues until the whole deck becomes one fully sorted bundle.
If \(S(n)\) denotes the expected number of shuffles still needed from that random starting arrangement, the task is to evaluate \(S(52)\) and print it to eight decimal places. The core difficulty is that the deck contains many different visible arrangements, but the implementations show that all of them collapse to a very small state space.
The key observation is that after every gluing phase, each bundle is already internally correct: it contains a consecutive interval of labels in increasing order. That makes it possible to ignore the exact card values inside each bundle and track only how many bundles remain.
Suppose a gluing phase has just finished and there are \(m\) bundles. Read those bundles in increasing label order and rename them \(1,2,\dots,m\). Their lengths may differ, but that no longer matters for the next shuffle.
After a random shuffle, what matters is only the permutation \(\pi\) of these \(m\) renamed bundles. Two neighboring bundles merge exactly when the second one is the immediate successor of the first one in label order. In the relabeled picture, that condition is simply
$$\pi(j+1)=\pi(j)+1.$$
Therefore every state with \(m\) bundles has the same transition law, independent of the bundle sizes. The process is a Markov chain on bundle counts \(1,2,\dots,n\).
Fix a current state with \(m\) bundles and ask for the probability of having exactly \(b\) bundles after the next shuffle and gluing phase.
To finish with \(b\) bundles, the labels \(1,2,\dots,m\) must first be split into \(b\) consecutive intervals. Choosing the \(b-1\) cut positions among the \(m-1\) gaps gives
$$\binom{m-1}{b-1}$$
possible interval decompositions.
Once these \(b\) intervals are fixed, treat each interval as one macro-block. They may be permuted, but the resulting order must avoid any place where macro-block \(i\) is immediately followed by macro-block \(i+1\), because such a pair would glue again and the decomposition would not be maximal.
Let \(A_b\) be the number of permutations of \(1,2,\dots,b\) with no adjacency of the form \(i\) immediately followed by \(i+1\). Then the number of permutations of the original \(m\) bundles that collapse to exactly \(b\) bundles is
$$\binom{m-1}{b-1}A_b.$$
For \(1\le i\le b-1\), let \(E_i\) be the event that block \(i\) is immediately followed by block \(i+1\). We want permutations avoiding all these events.
If we force a chosen set of \(r\) such adjacencies, the path \(1,2,\dots,b\) is compressed into \(b-r\) super-blocks. Each super-block has internally fixed order, and the super-blocks themselves can be permuted freely, so the number of permutations satisfying those \(r\) forced adjacencies is
$$(b-r)!.$$
There are \(\binom{b-1}{r}\) ways to choose which adjacencies are forced. Inclusion-exclusion therefore gives
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
Since every permutation of the \(m\) current bundles is equally likely, the transition probability is
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
Let \(T_m\) be the expected number of future shuffles needed when a gluing phase has just produced \(m\) bundles. Clearly
$$T_1=0,$$
because one bundle means the deck is already sorted.
For \(m>1\), we perform one shuffle immediately, then land in some new bundle count \(b\). Hence
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
The term with \(b=m\) represents the possibility that a shuffle creates no new merge at all. Moving that self-loop term to the left yields the usable recurrence
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
This allows \(T_2,T_3,\dots,T_n\) to be computed in increasing order.
The problem does not start from a post-shuffle state with a fixed bundle count. It starts from a uniformly random permutation of \(n\) single cards, before any counted shuffle has happened.
If we apply the gluing rule once to that initial random permutation, the resulting distribution of bundle counts is exactly the same as the transition distribution from \(n\) single-card bundles. Therefore
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
This is why the implementations first solve the recurrence for the post-compression expectation \(T_m\), and only then average over the initial distribution to obtain \(S(n)\).
For \(b=1,2,3,4\), inclusion-exclusion gives
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
Thus the transition probabilities from \(m=4\) bundles are
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
These probabilities sum to \(1\), as they must.
For the smallest nontrivial deck, \(n=2\), we have \(p_{2,1}=p_{2,2}=1/2\). Hence
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
The initial random permutation is already sorted with probability \(1/2\), so
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
This matches the exact small-case checkpoint used by the method.
The C++, Python, and Java implementations all follow the same pipeline. First they precompute factorials exactly as integers up to \(52!\), because all transition counts are rational combinations of factorials and binomial coefficients.
Next they evaluate the inclusion-exclusion count \(A_b\) for every \(1\le b\le 52\). With those counts available, they fill a triangular table of transition probabilities \(p_{m,b}\) for all \(1\le b\le m\le 52\).
The counting stage is done exactly, while the divisions are performed in high-precision decimal arithmetic with 100 digits of precision. That is more than enough to stabilize the final rounding to eight decimal places.
After the probability table is built, the implementations compute \(T_2,T_3,\dots,T_{52}\) using the rearranged recurrence. Finally they evaluate
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
and print the result with exactly eight digits after the decimal point. The same exact recurrence also reproduces useful checkpoints such as \(S(1)=0\), \(S(2)=1\), and \(S(5)=4213/871\).
Let \(N=52\), or more generally let \(N\) be the maximum deck size to be evaluated. Precomputing factorials costs \(O(N)\) big-integer operations. Computing all values \(A_b\) by inclusion-exclusion costs \(O(N^2)\). Filling the transition table \(p_{m,b}\) also costs \(O(N^2)\), and the dynamic-programming recurrence for \(T_m\) is another \(O(N^2)\).
So, ignoring the internal cost of high-precision arithmetic, the overall algorithm uses \(O(N^2)\) arithmetic steps and \(O(N^2)\) memory because the full triangular probability table is stored. For \(N=52\), this is easily fast enough.
Wir starten mit einer gleichverteilten zufälligen Permutation von \(\{1,2,\dots,n\}\). Immer wenn benachbarte Karten eine aufsteigende Folge aufeinanderfolgender Werte bilden, werden sie zu einem Bündel verklebt. Anschließend werden die Bündel gleichverteilt neu gemischt, dann wird wieder verklebt, und der Vorgang läuft weiter, bis das gesamte Deck ein einziges sortiertes Bündel ist.
Bezeichne \(S(n)\) die erwartete Anzahl weiterer Mischungen ausgehend von dieser zufälligen Startanordnung. Gesucht ist \(S(52)\) mit acht Nachkommastellen. Die eigentliche Vereinfachung besteht darin, dass nach jeder Verklebungsphase nur noch die Anzahl der Bündel relevant ist.
Nach jeder Verklebung ist jedes Bündel intern bereits korrekt: Es enthält ein Intervall aufeinanderfolgender Zahlen in aufsteigender Reihenfolge. Dadurch kann man die konkreten Kartenwerte innerhalb eines Bündels ignorieren und nur zählen, wie viele Bündel noch existieren.
Angenommen, eine Verklebungsphase ist gerade beendet und es gibt \(m\) Bündel. Liest man diese Bündel nach wachsender Kartenbeschriftung, kann man sie als \(1,2,\dots,m\) umbenennen. Die Bündellängen können verschieden sein, aber für den nächsten Schritt spielt das keine Rolle mehr.
Nach einem zufälligen Mischen zählt nur noch die Permutation \(\pi\) dieser \(m\) umbenannten Bündel. Zwei benachbarte Bündel verschmelzen genau dann, wenn das rechte Bündel im Label-Sinn der direkte Nachfolger des linken ist. In der umbenannten Darstellung lautet diese Bedingung
$$\pi(j+1)=\pi(j)+1.$$
Damit haben alle Konfigurationen mit \(m\) Bündeln dieselbe Übergangsverteilung, unabhängig von den tatsächlichen Bündelgrößen. Der Prozess ist also eine Markov-Kette auf den Zuständen \(1,2,\dots,n\).
Fixiere einen Zustand mit \(m\) Bündeln und frage nach der Wahrscheinlichkeit, nach dem nächsten Mischen und Verkleben genau \(b\) Bündel zu erhalten.
Dazu müssen die Labels \(1,2,\dots,m\) zunächst in \(b\) aufeinanderfolgende Intervalle zerlegt werden. Die Wahl der \(b-1\) Schnittstellen unter den \(m-1\) Zwischenräumen liefert
$$\binom{m-1}{b-1}$$
mögliche Zerlegungen.
Ist eine solche Zerlegung fest, behandelt man jedes Intervall als Makroblock. Diese Makroblöcke dürfen permutiert werden, aber die Reihenfolge darf an keiner Stelle Makroblock \(i\) direkt vor Makroblock \(i+1\) setzen, denn dann würden beide sofort wieder zusammenkleben und die Zerlegung wäre nicht maximal.
Sei \(A_b\) die Anzahl der Permutationen von \(1,2,\dots,b\), in denen niemals \(i\) unmittelbar von \(i+1\) gefolgt wird. Dann ist die Anzahl der Permutationen der ursprünglichen \(m\) Bündel, die zu genau \(b\) Bündeln kollabieren, gleich
$$\binom{m-1}{b-1}A_b.$$
Für \(1\le i\le b-1\) sei \(E_i\) das Ereignis, dass Block \(i\) unmittelbar vor Block \(i+1\) steht. Gesucht sind also Permutationen, die alle diese Ereignisse vermeiden.
Erzwingt man eine ausgewählte Menge von \(r\) solchen Nachbarschaften, dann schrumpft der Pfad \(1,2,\dots,b\) zu \(b-r\) Superblöcken. Innerhalb jedes Superblocks ist die Reihenfolge fest, aber die Superblöcke selbst können beliebig angeordnet werden. Daher gibt es
$$(b-r)!$$
Permutationen, die diese \(r\) erzwungenen Nachbarschaften erfüllen.
Es gibt \(\binom{b-1}{r}\) Möglichkeiten, welche Nachbarschaften erzwungen werden. Somit ergibt Inklusion-Exklusion
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
Da alle Permutationen der \(m\) aktuellen Bündel gleich wahrscheinlich sind, folgt für die Übergangswahrscheinlichkeit
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
Sei \(T_m\) die erwartete Anzahl künftiger Mischungen, wenn eine Verklebungsphase gerade \(m\) Bündel erzeugt hat. Offensichtlich gilt
$$T_1=0,$$
denn ein einziges Bündel bedeutet bereits vollständig sortiert.
Für \(m>1\) führen wir sofort eine Mischung aus und landen danach in irgendeinem neuen Bündelzustand \(b\). Also
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
Der Term mit \(b=m\) beschreibt den Fall ohne Fortschritt. Zieht man diesen Selbstschleifen-Anteil auf die linke Seite, erhält man die berechenbare Form
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
Damit lassen sich \(T_2,T_3,\dots,T_n\) sukzessive bestimmen.
Die Aufgabe startet nicht in einem Zustand mit bereits bekannter Bündelzahl nach einer gezählten Mischung. Stattdessen beginnt sie mit einer gleichverteilten zufälligen Permutation von \(n\) Einzelkarten.
Wendet man auf diese Startpermutation einmal die Verklebungsregel an, dann erhält man exakt dieselbe Verteilung der Bündelzahlen wie bei einem Übergang aus \(n\) Einzelkarten-Bündeln. Daher gilt
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
Genau deshalb lösen die Implementierungen zuerst die Rekurrenz für \(T_m\) und mitteln erst danach über die Anfangsverteilung, um \(S(n)\) zu bekommen.
Für \(b=1,2,3,4\) liefert Inklusion-Exklusion
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
Somit sind die Übergangswahrscheinlichkeiten aus \(m=4\) Bündeln
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
Die Summe ist \(1\), wie es sein muss.
Für das kleinste nichttriviale Deck \(n=2\) gilt \(p_{2,1}=p_{2,2}=1/2\). Also
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
Die zufällige Startpermutation ist schon mit Wahrscheinlichkeit \(1/2\) sortiert, daher
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
Dieser Wert ist ein exakter Kontrollpunkt für das Verfahren.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Rechenkette. Zuerst werden Fakultäten bis \(52!\) exakt als Ganzzahlen vorab berechnet, weil alle Übergangszahlen rationale Kombinationen aus Fakultäten und Binomialkoeffizienten sind.
Danach wird für jedes \(1\le b\le 52\) der Inklusion-Exklusion-Wert \(A_b\) ausgewertet. Mit diesen Werten füllen die Programme eine dreieckige Tabelle der Übergangswahrscheinlichkeiten \(p_{m,b}\) für alle \(1\le b\le m\le 52\).
Die Zählung selbst geschieht exakt, die Divisionen erfolgen anschließend in hochpräziser Dezimalarithmetik mit 100 Stellen Genauigkeit. Das ist weit mehr als genug, um die Endausgabe auf acht Nachkommastellen stabil zu runden.
Nach dem Aufbau der Wahrscheinlichkeitstabelle berechnen die Implementierungen \(T_2,T_3,\dots,T_{52}\) per dynamischer Programmierung aus der umgestellten Rekurrenz. Am Ende wird
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
ausgewertet und mit genau acht Dezimalstellen ausgegeben. Dieselbe exakte Rekurrenz reproduziert auch nützliche Kontrollwerte wie \(S(1)=0\), \(S(2)=1\) und \(S(5)=4213/871\).
Sei \(N=52\), allgemeiner also \(N\) die größte zu betrachtende Deckgröße. Das Vorberechnen der Fakultäten kostet \(O(N)\) Operationen auf großen Ganzzahlen. Das Berechnen aller \(A_b\) per Inklusion-Exklusion kostet \(O(N^2)\). Das Füllen der Übergangstabelle \(p_{m,b}\) benötigt ebenfalls \(O(N^2)\), und die Rekurrenz für \(T_m\) ist noch einmal \(O(N^2)\).
Ignoriert man die interne Kostenstruktur der hochpräzisen Arithmetik, so verwendet das gesamte Verfahren also \(O(N^2)\) Rechenschritte und \(O(N^2)\) Speicher, weil die vollständige dreieckige Wahrscheinlichkeitstabelle gespeichert wird. Für \(N=52\) ist das problemlos schnell genug.
\(\{1,2,\dots,n\}\) kümesinin eş olasılıklı rastgele bir permütasyonuyla başlanır. Yan yana duran kartlar artan ve ardışık bir koşu oluşturuyorsa tek bir paket halinde yapıştırılır. Sonra bu paketler eşit olasılıkla yeniden karılır, yine aynı yapıştırma kuralı uygulanır ve bütün deste tek bir sıralı paket olana kadar süreç sürer.
\(S(n)\), bu rastgele başlangıç düzeninden itibaren hâlâ gereken shuffle sayısının beklenen değeridir. Amaç \(S(52)\)'yi sekiz ondalık basamakla hesaplamaktır. Çözümün temel noktası, yapıştırma sonrasında görünen ayrıntıların büyük kısmının gereksiz hale gelmesidir.
Her yapıştırma turundan sonra her paket kendi içinde zaten doğrudur: etiketleri artan sırada gelen, ardışık sayılardan oluşan bir aralık taşır. Bu yüzden bir paketin içinde hangi kartların bulunduğunu tek tek izlemek yerine yalnızca kaç paket kaldığını izlemek yeterlidir.
Bir yapıştırma turunun bittiğini ve elimizde \(m\) paket kaldığını varsayalım. Bu paketleri etiketlerinin nihai sıralamadaki yerine göre \(1,2,\dots,m\) diye yeniden adlandıralım. Paket boyları farklı olabilir, fakat bir sonraki tur için bunun önemi kalmaz.
Rastgele karıştırmadan sonra önemli olan tek şey, bu \(m\) yeniden adlandırılmış paketin hangi permütasyonla dizildiğidir. Yan yana duran iki paket ancak sağdaki, soldakinin etikette tam bir sonraki aralığıysa birleşir. Bu koşul yeniden adlandırılmış biçimde
$$\pi(j+1)=\pi(j)+1$$
şeklindedir.
Dolayısıyla \(m\) paketli her durum, gerçek paket uzunluklarından bağımsız olarak aynı geçiş dağılımına sahiptir. Süreç, durumları \(1,2,\dots,n\) olan bir Markov zincirine indirgenir.
Şimdi \(m\) paketli bir durumda olduğumuzu kabul edip, bir sonraki shuffle ve yapıştırma sonrasında tam olarak \(b\) paket kalma olasılığını sayalım.
Bunun için önce \(1,2,\dots,m\) etiketleri \(b\) tane ardışık aralığa bölünmelidir. \(m-1\) boşluk arasından \(b-1\) kesim seçildiği için bunun sayısı
$$\binom{m-1}{b-1}$$
olur.
Bu \(b\) aralık sabitlendikten sonra, her aralığı tek bir makro-paket gibi düşünürüz. Bu makro-paketler yer değiştirebilir; ancak herhangi bir yerde makro-paket \(i\)'nin hemen ardından makro-paket \(i+1\) gelirse bunlar yeniden birleşir ve seçtiğimiz ayrışım maksimal olmaz.
\(A_b\), \(1,2,\dots,b\) permütasyonları içinde hiçbir \(i\)'nin hemen ardından \(i+1\)'in gelmediği sıralama sayısı olsun. O zaman özgün \(m\) paketin tam olarak \(b\) pakete çökmesine yol açan permütasyon sayısı
$$\binom{m-1}{b-1}A_b$$
olur.
\(1\le i\le b-1\) için \(E_i\), blok \(i\)'nin hemen ardından blok \(i+1\)'in gelmesi olayı olsun. Biz bütün bu olaylardan kaçınan permütasyonları arıyoruz.
Bu komşuluklardan seçilmiş \(r\) tanesini zorunlu kılarsak, \(1,2,\dots,b\) yolu \(b-r\) süper bloğa sıkışır. Her süper bloğun iç sırası sabittir; yalnızca süper blokların kendi aralarındaki sıralama değişebilir. Bu nedenle, seçilen \(r\) zorunlu komşuluğu sağlayan permütasyon sayısı
$$(b-r)!$$
olur.
Hangi komşulukların zorunlu tutulacağını seçmenin sayısı \(\binom{b-1}{r}\) olduğundan, dahil et-çıkar ilkesi
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!$$
sonucunu verir. \(m\) paketin tüm permütasyonları eşit olasılıklı olduğundan geçiş olasılığı
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m$$
şeklindedir.
\(T_m\), bir yapıştırma adımı tamamlanıp \(m\) paket kaldığı anda, bundan sonra gereken shuffle sayısının beklenen değeri olsun. Açıkça
$$T_1=0$$
çünkü tek paket tüm destenin sıralandığı anlamına gelir.
\(m>1\) için hemen bir shuffle yapılır ve sonra yeni paket sayısı \(b\) olur. Bu yüzden
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
\(b=m\) terimi, hiç ilerleme kaydedilmeyen self-loop durumudur. Bunu sola taşırsak kullanılacak biçim elde edilir:
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
Böylece \(T_2,T_3,\dots,T_n\) artan sırayla hesaplanabilir.
Problem, sabit bir paket sayısına sahip bir sıkıştırılmış durumdan başlamaz. Başlangıçta \(n\) tekil kartın eş olasılıklı rastgele bir permütasyonu vardır ve henüz sayılan bir shuffle gerçekleşmemiştir.
Bu başlangıç permütasyonuna yapıştırma kuralını bir kez uygularsak, ortaya çıkan paket sayısı dağılımı, \(n\) tane tek kart paketinden geçiş yapmışız gibi tam olarak \(p_{n,b}\) ile aynıdır. Dolayısıyla
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
İmplementasyonların önce \(T_m\) bağıntısını çözmesinin, sonra da başlangıç dağılımı üzerinde ortalama almasının nedeni budur.
\(b=1,2,3,4\) için dahil et-çıkar şu değerleri verir:
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
Buna göre \(m=4\) durumundan geçiş olasılıkları
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
Toplam \(1\) çıkar; bu da doğru bir olasılık dağılımı elde ettiğimizi gösterir.
En küçük önemsiz olmayan deste için, yani \(n=2\) olduğunda, \(p_{2,1}=p_{2,2}=1/2\) olur. Dolayısıyla
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
Başlangıçtaki rastgele permütasyon yarı olasılıkla zaten sıralı olduğundan
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
Bu değer yöntemin tam küçük durum kontrolüdür.
C++, Python ve Java implementasyonları aynı hesap zincirini izler. Önce \(52!\)'ye kadar tüm faktöriyeller tam sayı olarak önceden hesaplanır; çünkü bütün geçiş sayıları faktöriyel ve binom katsayılarının rasyonel birleşimleridir.
Daha sonra her \(1\le b\le 52\) için dahil et-çıkar sayısı \(A_b\) üretilir. Bu sayılar kullanılarak bütün \(1\le b\le m\le 52\) için üçgensel geçiş olasılığı tablosu \(p_{m,b}\) doldurulur.
Sayma kısmı tam aritmetikle yapılır; bölmeler ise 100 basamak hassasiyetli ondalık aritmetiğe çevrilir. Bu hassasiyet, sonucun sekiz ondalık basamakta güvenli şekilde yuvarlanması için fazlasıyla yeterlidir.
Olasılık tablosu hazır olduktan sonra implementasyonlar \(T_2,T_3,\dots,T_{52}\) değerlerini yeniden düzenlenmiş bağıntıyla dinamik programlama olarak hesaplar. Son adımda
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
değeri alınır ve tam sekiz ondalık basamakla yazdırılır. Aynı bağıntı \(S(1)=0\), \(S(2)=1\) ve \(S(5)=4213/871\) gibi yararlı kontrol değerlerini de üretir.
\(N=52\) olsun; daha genel olarak \(N\), hesaplanacak en büyük deste boyutudur. Faktöriyel ön hesaplaması \(O(N)\) büyük tamsayı işlemi gerektirir. Tüm \(A_b\) değerlerini dahil et-çıkar ile hesaplamak \(O(N^2)\) sürer. Geçiş tablosu \(p_{m,b}\) için de \(O(N^2)\) iş yapılır; \(T_m\) bağıntısı da yine \(O(N^2)\) maliyetlidir.
Yüksek hassasiyetli aritmetiğin kendi iç maliyetini sabit kabul edersek, toplam yöntem \(O(N^2)\) aritmetik adım ve \(O(N^2)\) bellek kullanır; çünkü tam üçgensel olasılık tablosu saklanır. \(N=52\) için bu rahatlıkla yeterlidir.
Se empieza con una permutación aleatoria uniforme de \(\{1,2,\dots,n\}\). Siempre que cartas vecinas formen una sucesión creciente de valores consecutivos, se pegan en un solo bloque. Luego los bloques se barajan uniformemente, se vuelve a aplicar la misma regla de pegado y el proceso continúa hasta que toda la baraja se convierte en un único bloque completamente ordenado.
Si \(S(n)\) es el número esperado de barajados que todavía faltan desde esa disposición inicial aleatoria, hay que calcular \(S(52)\) con ocho decimales. La simplificación clave es que, después de cada fase de pegado, casi toda la información visible deja de importar.
Tras cada pegado, cada bloque ya es internamente correcto: contiene un intervalo de etiquetas consecutivas en orden creciente. Por eso no hace falta seguir los valores exactos dentro de cada bloque; basta con saber cuántos bloques quedan.
Supongamos que una fase de pegado acaba de terminar y quedan \(m\) bloques. Si leemos esos bloques en el orden de sus etiquetas finales, podemos renombrarlos como \(1,2,\dots,m\). Sus longitudes pueden ser distintas, pero eso ya no afecta al siguiente barajado.
Después de mezclar al azar, solo importa la permutación \(\pi\) de esos \(m\) bloques renombrados. Dos bloques vecinos se fusionan exactamente cuando el de la derecha es el sucesor inmediato del de la izquierda en el orden de etiquetas. En la versión renombrada, la condición es
$$\pi(j+1)=\pi(j)+1.$$
Así, todas las configuraciones con \(m\) bloques tienen la misma ley de transición, sin depender de los tamaños reales de los bloques. El proceso queda reducido a una cadena de Markov sobre los estados \(1,2,\dots,n\).
Fijemos ahora un estado con \(m\) bloques y contemos la probabilidad de acabar con exactamente \(b\) bloques tras el siguiente barajado y pegado.
Para ello, las etiquetas \(1,2,\dots,m\) deben partirse primero en \(b\) intervalos consecutivos. Elegir las \(b-1\) posiciones de corte entre los \(m-1\) huecos produce
$$\binom{m-1}{b-1}$$
descomposiciones posibles.
Una vez fijados esos \(b\) intervalos, cada uno se trata como un macro-bloque. Estos macro-bloques pueden permutarse, pero el orden resultante no puede colocar un macro-bloque \(i\) inmediatamente antes del macro-bloque \(i+1\), porque entonces volverían a pegarse y la descomposición no sería maximal.
Sea \(A_b\) el número de permutaciones de \(1,2,\dots,b\) sin ninguna adyacencia de la forma \(i\) seguida inmediatamente por \(i+1\). Entonces el número de permutaciones de los \(m\) bloques originales que colapsan en exactamente \(b\) bloques es
$$\binom{m-1}{b-1}A_b.$$
Para \(1\le i\le b-1\), sea \(E_i\) el evento “el bloque \(i\) va inmediatamente seguido del bloque \(i+1\)”. Queremos contar las permutaciones que evitan todos esos eventos.
Si imponemos un conjunto elegido de \(r\) de esas adyacencias, el camino \(1,2,\dots,b\) se comprime en \(b-r\) super-bloques. El orden interno de cada super-bloque queda fijado, y solo queda permutar libremente los super-bloques. Por tanto, el número de permutaciones que satisfacen esas \(r\) adyacencias forzadas es
$$(b-r)!.$$
Hay \(\binom{b-1}{r}\) formas de elegir cuáles son las adyacencias forzadas. Aplicando inclusión-exclusión se obtiene
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
Como todas las permutaciones de los \(m\) bloques actuales son equiprobables, la probabilidad de transición es
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
Sea \(T_m\) el número esperado de futuros barajados cuando una fase de pegado acaba de producir \(m\) bloques. Claramente
$$T_1=0,$$
porque un único bloque significa que la baraja ya está ordenada.
Para \(m>1\), hacemos un barajado inmediatamente y luego caemos en un nuevo número de bloques \(b\). Por tanto
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
El término con \(b=m\) representa un auto-bucle en el que no se consigue ninguna fusión nueva. Llevándolo al lado izquierdo queda la forma útil
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
Esto permite calcular \(T_2,T_3,\dots,T_n\) en orden creciente.
El problema no empieza en un estado ya comprimido con un número fijo de bloques tras un barajado contado. Empieza con una permutación aleatoria uniforme de \(n\) cartas sueltas, antes de cualquier barajado contado.
Si aplicamos una vez la regla de pegado a esa permutación inicial, la distribución resultante del número de bloques coincide exactamente con la distribución de transición desde \(n\) bloques unitarios. Por eso
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
Esa es la razón por la que las implementaciones resuelven primero la recurrencia para \(T_m\) y solo después promedian con la distribución inicial para obtener \(S(n)\).
Para \(b=1,2,3,4\), la inclusión-exclusión da
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
Así, las probabilidades de transición desde \(m=4\) bloques son
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
La suma es \(1\), como debe ocurrir.
Para la baraja no trivial más pequeña, \(n=2\), se tiene \(p_{2,1}=p_{2,2}=1/2\). Entonces
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
La permutación inicial ya está ordenada con probabilidad \(1/2\), de modo que
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
Ese valor sirve como comprobación exacta del método.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero precalculan factoriales exactos hasta \(52!\), ya que todos los conteos de transición son combinaciones racionales de factoriales y coeficientes binomiales.
Después evalúan el conteo por inclusión-exclusión \(A_b\) para cada \(1\le b\le 52\). Con esos valores construyen una tabla triangular de probabilidades de transición \(p_{m,b}\) para todos los \(1\le b\le m\le 52\).
La fase de conteo se hace con aritmética exacta, mientras que las divisiones se convierten a aritmética decimal de alta precisión con 100 dígitos. Eso basta holgadamente para que el redondeo final a ocho decimales sea estable.
Una vez construida la tabla de probabilidades, las implementaciones calculan \(T_2,T_3,\dots,T_{52}\) mediante la recurrencia reorganizada. Al final evalúan
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
y lo imprimen con exactamente ocho cifras tras el punto decimal. La misma recurrencia exacta también reproduce comprobaciones útiles como \(S(1)=0\), \(S(2)=1\) y \(S(5)=4213/871\).
Sea \(N=52\), o en general la mayor longitud de baraja que se quiere evaluar. Precalcular factoriales cuesta \(O(N)\) operaciones con enteros grandes. Calcular todos los valores \(A_b\) por inclusión-exclusión cuesta \(O(N^2)\). Rellenar la tabla de transición \(p_{m,b}\) también cuesta \(O(N^2)\), y la programación dinámica para \(T_m\) añade otro \(O(N^2)\).
Por tanto, ignorando el coste interno de la aritmética de alta precisión, el algoritmo completo usa \(O(N^2)\) pasos aritméticos y \(O(N^2)\) memoria, porque se almacena la tabla triangular completa de probabilidades. Para \(N=52\), esto es más que suficiente.
题目从 \(\{1,2,\dots,n\}\) 的一个等概率随机排列开始。每当相邻卡牌构成严格递增且数值连续的一段，就把它们粘成一个束。随后把这些束等概率随机重排，再重复同样的粘合规则，直到整副牌变成一个完全有序的大束为止。
设 \(S(n)\) 表示从这个随机初始排列出发，之后还需要多少次洗牌的期望值。目标是求出 \(S(52)\)，并输出到小数点后 8 位。难点在于牌面排列很多，但实现里真正保留下来的状态信息非常少。
核心观察是：每一次粘合结束后，每个束的内部都已经是“正确”的，也就是它恰好对应一个按升序排列的连续整数区间。既然如此，下一轮过程并不关心束内具体有多少张牌、是什么数值，只关心当前还剩多少个束。
假设某一次粘合刚结束，当前共有 \(m\) 个束。按照这些束在最终有序牌列中的先后位置，把它们重新编号为 \(1,2,\dots,m\)。各束长度可以不同，但对下一轮随机重排来说，这些长度已经不再影响转移概率。
随机重排之后，真正重要的只是这 \(m\) 个重编号束形成的一个排列 \(\pi\)。两个相邻束会再次合并，当且仅当右边那个束在编号上正好是左边那个束的后继，也就是
$$\pi(j+1)=\pi(j)+1.$$
因此，所有“当前有 \(m\) 个束”的局面都具有完全相同的后继分布，而不依赖于束的实际长度。于是整个过程可以看成定义在状态 \(1,2,\dots,n\) 上的一条 Markov 链。
固定当前状态为 \(m\) 个束，考虑下一次随机重排并粘合之后恰好剩下 \(b\) 个束的概率。
若最终变成 \(b\) 个束，那么编号 \(1,2,\dots,m\) 必须先被分成 \(b\) 个连续区间。因为需要在 \(m-1\) 个空隙中选出 \(b-1\) 个切点，所以这样的区间划分共有
$$\binom{m-1}{b-1}$$
种。
区间一旦固定，就把每个区间看成一个宏块。接下来可以对这些宏块做排列，但结果中不能出现“宏块 \(i\) 后面紧接着宏块 \(i+1\)”的情况；否则它们会再次粘在一起，说明这不是一个极大的分块。
记 \(A_b\) 为 \(1,2,\dots,b\) 的排列中，不出现任何 “\(i\) 紧跟着 \(i+1\)” 的排列个数。那么，原来 \(m\) 个束的所有随机排列里，恰好压缩成 \(b\) 个束的排列个数就是
$$\binom{m-1}{b-1}A_b.$$
对每个 \(1\le i\le b-1\)，设事件 \(E_i\) 表示“块 \(i\) 后面立刻跟着块 \(i+1\)”。我们需要统计的是避开所有这些事件的排列数。
如果强制其中某 \(r\) 个相邻关系成立，那么路径 \(1,2,\dots,b\) 会被压缩成 \(b-r\) 个超块。每个超块内部顺序已经固定，而超块之间可以任意排列，所以满足这些被强制相邻关系的排列数为
$$(b-r)!.$$
选出哪 \(r\) 个相邻关系被强制成立，有 \(\binom{b-1}{r}\) 种方法。于是容斥原理给出
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
由于当前 \(m\) 个束的全部 \(m!\) 种排列等可能，因此转移概率为
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
令 \(T_m\) 表示“某次粘合刚结束，当前有 \(m\) 个束”时，从这一刻开始还需要多少次洗牌的期望值。显然
$$T_1=0,$$
因为只剩 1 个束时，整副牌已经完全排好序。
当 \(m>1\) 时，接下来一定先进行一次洗牌，然后落到某个新的束数 \(b\)。因此
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
其中 \(b=m\) 的项对应“这次洗牌完全没有带来新的合并”。把这个自环项移到左边，可以得到适合动态规划的形式
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
这样就能按 \(m=2,3,\dots,n\) 的顺序逐步求出所有 \(T_m\)。
题目并不是从“已经压缩完、束数已知”的状态开始的。它一开始只是 \(n\) 张单卡形成的一个随机排列，而且这一步随机排列本身不算作要统计的洗牌次数。
如果先对这个随机初态应用一次粘合规则，那么得到的束数分布，恰好与“从 \(n\) 个单卡束出发做一次状态转移”的分布相同。因此有
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
这也解释了为什么实现会先求出压缩态下的期望 \(T_m\)，再用起始分布做一次平均，得到真正要求的 \(S(n)\)。
对 \(b=1,2,3,4\)，由容斥公式可得
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
所以从 \(m=4\) 个束出发时，各种结果的概率是
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
四项相加正好等于 \(1\)。
再看最小的非平凡例子 \(n=2\)。这时 \(p_{2,1}=p_{2,2}=1/2\)，所以
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
由于随机起始排列有一半概率本来就是升序，因此
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
这个值正好是方法的一个精确小规模校验点。
C++、Python 和 Java 实现都遵循同一条计算流程。首先，它们把所有阶乘精确预处理到 \(52!\)，因为所有转移计数都能写成阶乘与二项式系数的有理组合。
然后，对每个 \(1\le b\le 52\) 计算容斥计数 \(A_b\)。有了这些值以后，再为所有 \(1\le b\le m\le 52\) 建立一个三角形的转移概率表 \(p_{m,b}\)。
计数阶段使用精确整数算术，真正做除法时才转成 100 位精度的高精度十进制数。这个精度远高于最终保留 8 位小数所需的稳定性要求。
构造出概率表后，程序按顺序求出 \(T_2,T_3,\dots,T_{52}\)。最后计算
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
并输出到小数点后 8 位。相同的精确递推还会给出有用的检查值，例如 \(S(1)=0\)、\(S(2)=1\) 和 \(S(5)=4213/871\)。
记最大牌数为 \(N\)，本题中 \(N=52\)。预处理阶乘需要 \(O(N)\) 次大整数运算。计算全部 \(A_b\) 需要 \(O(N^2)\)。建立整张转移概率表 \(p_{m,b}\) 也是 \(O(N^2)\)，而求解 \(T_m\) 的动态规划同样是 \(O(N^2)\)。
因此，如果把高精度算术内部的位复杂度视为常数因子，那么总算法需要 \(O(N^2)\) 次算术步骤和 \(O(N^2)\) 内存，因为完整的三角概率表被保留下来。对于 \(N=52\)，这个规模非常小。
Мы начинаем с равновероятной случайной перестановки \(\{1,2,\dots,n\}\). Если соседние карты образуют возрастающий непрерывный по значениям фрагмент, они склеиваются в один блок. Затем блоки равновероятно перемешиваются, правило склейки применяется снова, и процесс повторяется, пока вся колода не превратится в один полностью отсортированный блок.
Пусть \(S(n)\) обозначает математическое ожидание числа оставшихся перемешиваний из такой случайной начальной конфигурации. Требуется найти \(S(52)\) с точностью до восьми знаков после запятой. Главный выигрыш состоит в том, что после каждого этапа склейки почти вся детальная информация о раскладке больше не нужна.
После каждой склейки каждый блок уже внутренне корректен: он состоит из некоторого интервала последовательных меток, записанных по возрастанию. Поэтому дальше важно не содержимое блока, а только число блоков, которые еще остались.
Предположим, что этап склейки только что завершился и осталось \(m\) блоков. Если упорядочить эти блоки по их месту в окончательно отсортированной колоде, их можно перенумеровать как \(1,2,\dots,m\). Длины блоков могут различаться, но на следующий переход это уже не влияет.
После случайного перемешивания важна только перестановка \(\pi\) этих \(m\) перенумерованных блоков. Два соседних блока сольются тогда и только тогда, когда правый блок является непосредственным последователем левого по метке. В перенумерованной модели условие имеет вид
$$\pi(j+1)=\pi(j)+1.$$
Значит, у всех конфигураций с \(m\) блоками одно и то же распределение перехода, независимо от реальных размеров блоков. Процесс становится цепью Маркова по состояниям \(1,2,\dots,n\).
Зафиксируем состояние с \(m\) блоками и спросим: какова вероятность того, что после следующего перемешивания и новой склейки останется ровно \(b\) блоков?
Чтобы в итоге получить \(b\) блоков, метки \(1,2,\dots,m\) сначала должны разбиться на \(b\) последовательных интервалов. Выбор \(b-1\) мест разреза среди \(m-1\) промежутков дает
$$\binom{m-1}{b-1}$$
вариантов такого разбиения.
После этого каждый интервал рассматривается как один макроблок. Эти макроблоки можно переставлять, но итоговый порядок не должен содержать места, где макроблок \(i\) сразу стоит перед макроблоком \(i+1\), иначе они снова склеятся и выбранное разбиение не будет максимальным.
Обозначим через \(A_b\) число перестановок \(1,2,\dots,b\), в которых нигде не встречается соседство вида “\(i\) сразу перед \(i+1\)”. Тогда число перестановок исходных \(m\) блоков, которые схлопываются ровно в \(b\) блоков, равно
$$\binom{m-1}{b-1}A_b.$$
Для \(1\le i\le b-1\) обозначим через \(E_i\) событие “блок \(i\) непосредственно предшествует блоку \(i+1\)”. Нам нужно посчитать перестановки, избегающие всех этих событий.
Если принудительно зафиксировать некоторый набор из \(r\) таких соседств, путь \(1,2,\dots,b\) сожмется до \(b-r\) суперблоков. Внутренний порядок в каждом суперблоке уже фиксирован, а сами суперблоки можно переставлять произвольно. Поэтому число перестановок, удовлетворяющих этим \(r\) навязанным соседствам, равно
$$(b-r)!.$$
Выбрать, какие именно \(r\) соседств навязаны, можно \(\binom{b-1}{r}\) способами. Отсюда по включению-исключению получаем
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
Так как все \(m!\) перестановок текущих \(m\) блоков равновероятны, вероятность перехода равна
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
Пусть \(T_m\) обозначает ожидаемое число будущих перемешиваний в момент, когда очередной этап склейки только что оставил \(m\) блоков. Ясно, что
$$T_1=0,$$
потому что один блок означает полностью отсортированную колоду.
Для \(m>1\) мы немедленно выполняем одно перемешивание, а затем попадаем в новое число блоков \(b\). Поэтому
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
Слагаемое с \(b=m\) соответствует самопереходу без прогресса. Перенеся его влево, получаем удобную для динамики форму
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
Это позволяет последовательно вычислять \(T_2,T_3,\dots,T_n\).
Задача начинается не из уже сжатого состояния с фиксированным числом блоков после учитываемого перемешивания. В начале есть просто случайная перестановка \(n\) одиночных карт, причем эта начальная случайность не считается одним из искомых перемешиваний.
Если один раз применить правило склейки к этой начальной перестановке, распределение по числу блоков окажется в точности тем же самым, что и при переходе из \(n\) одноэлементных блоков. Следовательно,
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
Именно поэтому реализации сначала решают рекурсию для \(T_m\), а потом усредняют по начальному распределению, чтобы получить искомое \(S(n)\).
Для \(b=1,2,3,4\) из включения-исключения получаем
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
Значит, вероятности перехода из состояния \(m=4\) таковы:
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
Их сумма равна \(1\), как и должна.
Для минимального нетривиального случая \(n=2\) имеем \(p_{2,1}=p_{2,2}=1/2\). Тогда
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
Начальная случайная перестановка уже отсортирована с вероятностью \(1/2\), поэтому
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
Это точная маленькая проверка метода.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала они точно предвычисляют факториалы вплоть до \(52!\), потому что все числа переходов выражаются через факториалы и биномиальные коэффициенты.
Затем для каждого \(1\le b\le 52\) вычисляется инклюзионно-эксклюзионное число \(A_b\). После этого строится треугольная таблица вероятностей перехода \(p_{m,b}\) для всех \(1\le b\le m\le 52\).
Стадия подсчета выполняется точно, а деления переводятся в десятичную арифметику высокой точности с 100 значащими цифрами. Этого более чем достаточно, чтобы надежно округлить итог до восьми знаков после запятой.
Когда таблица вероятностей готова, реализации последовательно вычисляют \(T_2,T_3,\dots,T_{52}\) по переставленной рекурсии. Затем они находят
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
и печатают результат с восемью знаками после запятой. Та же точная схема также воспроизводит полезные контрольные значения \(S(1)=0\), \(S(2)=1\) и \(S(5)=4213/871\).
Пусть \(N=52\), а в общем случае \(N\) обозначает максимальный размер колоды. Предвычисление факториалов требует \(O(N)\) операций с большими целыми. Вычисление всех \(A_b\) по включению-исключению стоит \(O(N^2)\). Построение таблицы \(p_{m,b}\) тоже занимает \(O(N^2)\), и динамика для \(T_m\) добавляет еще \(O(N^2)\).
Следовательно, если не раскрывать внутреннюю стоимость высокоточной арифметики, общий алгоритм использует \(O(N^2)\) арифметических шагов и \(O(N^2)\) памяти, поскольку полная треугольная таблица вероятностей хранится целиком. Для \(N=52\) это очень небольшой объем работы.
نبدأ بترتيب عشوائي منتظم لعناصر \(\{1,2,\dots,n\}\). كلما كانت بطاقات متجاورة تشكل مقطعًا متزايدًا ومتتاليًا في القيم فإنها تُلصق في حزمة واحدة. بعد ذلك تُخلط الحزم عشوائيًا بالتساوي، ثم تُطبَّق قاعدة اللصق من جديد، وتستمر العملية حتى تصبح الرزمة كلها حزمة واحدة مرتبة بالكامل.
إذا رمزنا بـ \(S(n)\) إلى القيمة المتوقعة لعدد مرات الخلط المتبقية انطلاقًا من هذا الوضع الابتدائي العشوائي، فالمطلوب هو حساب \(S(52)\) حتى 8 منازل عشرية. الفكرة الحاسمة هي أن معظم التفاصيل المرئية بعد كل مرحلة لصق لا تعود مهمة للحساب.
بعد كل مرحلة لصق تكون كل حزمة صحيحة داخليًا بالفعل: فهي تمثل فترة من القيم المتتالية مرتبة تصاعديًا. لهذا لا نحتاج إلى تتبع البطاقات داخل كل حزمة على حدة، بل يكفي أن نعرف عدد الحزم المتبقية فقط.
افترض أن مرحلة لصق انتهت للتو وبقي لدينا \(m\) حزم. إذا رتبنا هذه الحزم بحسب مواضعها في الترتيب النهائي الصحيح، أمكن إعادة تسميتها إلى \(1,2,\dots,m\). أطوال الحزم قد تختلف، لكن ذلك لا يؤثر في الانتقال التالي.
بعد الخلط العشوائي، الشيء المهم الوحيد هو التبديل \(\pi\) لهذه الحزم \(m\). تندمج حزمتان متجاورتان بالضبط عندما تكون الحزمة اليمنى هي اللاحقة المباشرة للحزمة اليسرى في ترتيب العلامات. وفي الصورة المعاد ترميزها يصبح الشرط
$$\pi(j+1)=\pi(j)+1.$$
لذلك فإن كل الحالات التي تحتوي على \(m\) حزم لها التوزيع الانتقالي نفسه، بصرف النظر عن الأطوال الفعلية للحزم. وهكذا تتحول العملية إلى سلسلة Markov على الحالات \(1,2,\dots,n\).
ثبّت الآن حالة فيها \(m\) حزم، واسأل عن احتمال أن ينتهي الخلط التالي مع اللصق إلى \(b\) حزم بالضبط.
لكي نحصل في النهاية على \(b\) حزم، يجب أولًا تقسيم العلامات \(1,2,\dots,m\) إلى \(b\) فترات متتالية. اختيار \(b-1\) مواضع قطع من بين الفجوات \(m-1\) يعطي
$$\binom{m-1}{b-1}$$
تقسيمات ممكنة.
بعد تثبيت هذه الفترات، نتعامل مع كل فترة على أنها كتلة كبرى واحدة. يمكن تبديل هذه الكتل، لكن لا يجوز أن تأتي الكتلة \(i\) مباشرة قبل الكتلة \(i+1\)، لأنهما عندئذ ستلتصقان مرة أخرى ولن يكون التقسيم أعظميًا.
لنرمز بـ \(A_b\) إلى عدد تبديلات \(1,2,\dots,b\) التي لا يظهر فيها أي موضع من الشكل “\(i\) يتبعه مباشرة \(i+1\)”. عندئذ يكون عدد تبديلات الحزم الأصلية \(m\) التي تنهار إلى \(b\) حزم بالضبط هو
$$\binom{m-1}{b-1}A_b.$$
لكل \(1\le i\le b-1\)، ليكن \(E_i\) هو الحدث “الكتلة \(i\) تأتي مباشرة قبل الكتلة \(i+1\)”. نحن نريد عدّ التبديلات التي تتجنب كل هذه الأحداث.
إذا فرضنا مجموعة مختارة من \(r\) مجاورات من هذا النوع، فإن المسار \(1,2,\dots,b\) ينضغط إلى \(b-r\) كتل عظمى. الترتيب الداخلي لكل كتلة عظمى يصبح ثابتًا، وتبقى حرية تبديل هذه الكتل العظمى فيما بينها. لذلك فإن عدد التبديلات التي تحقق تلك المجاورات المفروضة هو
$$(b-r)!.$$
وهناك \(\binom{b-1}{r}\) طريقة لاختيار أي المجاورات تُفرض. ومن ثم يعطينا مبدأ الإدراج والإقصاء الصيغة
$$A_b=\sum_{r=0}^{b-1}(-1)^r\binom{b-1}{r}(b-r)!.$$
وبما أن جميع تبديلات الحزم الحالية وعددها \(m!\) متساوية الاحتمال، فإن احتمال الانتقال هو
$$p_{m,b}=\frac{\binom{m-1}{b-1}A_b}{m!},\qquad 1\le b\le m.$$
لتكن \(T_m\) هي القيمة المتوقعة لعدد مرات الخلط المستقبلية عندما تكون مرحلة اللصق قد انتهت لتوها إلى \(m\) حزم. من الواضح أن
$$T_1=0,$$
لأن وجود حزمة واحدة يعني أن الرزمة صارت مرتبة بالكامل.
إذا كان \(m>1\)، فنحن ننفذ خلطًا واحدًا فورًا، ثم نصل إلى عدد جديد من الحزم يساوي \(b\). ولذلك
$$T_m=1+\sum_{b=1}^{m}p_{m,b}T_b.$$
والحد الموافق لـ \(b=m\) يمثل إمكانية عدم حدوث أي اندماج جديد بعد الخلط. بنقل هذا الحد إلى الطرف الأيسر نحصل على الصيغة العملية
$$T_m=\frac{1+\sum_{b=1}^{m-1}p_{m,b}T_b}{1-p_{m,m}}.$$
وهذا يسمح بحساب \(T_2,T_3,\dots,T_n\) تدريجيًا.
المسألة لا تبدأ من حالة مضغوطة بعدد حزم معلوم بعد خلط محسوب. بل تبدأ من تبديل عشوائي منتظم لـ \(n\) بطاقات منفردة، وهذه العشوائية الابتدائية نفسها لا تُحسب كواحدة من مرات الخلط المطلوبة.
إذا طبقنا قاعدة اللصق مرة واحدة على هذا الترتيب الابتدائي، فإن توزيع عدد الحزم الناتج يطابق تمامًا توزيع الانتقال من \(n\) حزم أحادية. لذلك
$$S(n)=\sum_{b=1}^{n}p_{n,b}T_b.$$
ولهذا السبب تحسب التطبيقات أولًا توقعات ما بعد الضغط \(T_m\)، ثم تأخذ متوسطها وفق التوزيع الابتدائي للحصول على \(S(n)\).
عندما \(b=1,2,3,4\) تعطينا صيغة الإدراج والإقصاء
$$A_1=1,\qquad A_2=1,\qquad A_3=3,\qquad A_4=11.$$
ومن ثم تصبح احتمالات الانتقال من الحالة \(m=4\) هي
$$p_{4,1}=\frac{\binom{3}{0}A_1}{4!}=\frac{1}{24},\qquad p_{4,2}=\frac{\binom{3}{1}A_2}{4!}=\frac{3}{24},$$
$$p_{4,3}=\frac{\binom{3}{2}A_3}{4!}=\frac{9}{24},\qquad p_{4,4}=\frac{\binom{3}{3}A_4}{4!}=\frac{11}{24}.$$
ومجموعها يساوي \(1\)، كما يجب.
أما في أصغر حالة غير تافهة \(n=2\)، فإن \(p_{2,1}=p_{2,2}=1/2\). ومن ثم
$$T_2=\frac{1+\frac{1}{2}T_1}{1-\frac{1}{2}}=2.$$
ولأن الترتيب الابتدائي يكون مرتبًا أصلًا باحتمال \(1/2\)، نحصل على
$$S(2)=\frac{1}{2}T_1+\frac{1}{2}T_2=1.$$
وهذه قيمة فحص دقيقة للطريقة.
تتبع تطبيقات C++ و Python و Java السلسلة الحسابية نفسها. أولًا تُحسب جميع المضروبات حتى \(52!\) حسابًا صحيحًا تامًا، لأن كل أعداد الانتقال يمكن كتابتها على صورة تراكيب كسرية من المضروبات ومعاملات ثنائية الحد.
بعد ذلك يُحسب عدد الإدراج والإقصاء \(A_b\) لكل \(1\le b\le 52\). وبالاعتماد على هذه القيم تُملأ مصفوفة مثلثية لاحتمالات الانتقال \(p_{m,b}\) لكل \(1\le b\le m\le 52\).
مرحلة العد تتم بدقة صحيحة، ثم تُحوَّل القسمة إلى حساب عشري عالي الدقة يبلغ 100 رقم. وهذا أكثر من كافٍ لضمان ثبات التقريب النهائي إلى 8 منازل عشرية.
بعد اكتمال جدول الاحتمالات، تحسب التطبيقات \(T_2,T_3,\dots,T_{52}\) من العلاقة المعاد ترتيبها. وفي النهاية تُقيَّم الكمية
$$S(52)=\sum_{b=1}^{52}p_{52,b}T_b$$
وتُطبع مع 8 خانات بعد الفاصلة. كما أن العلاقة نفسها تعطي قيم تحقق مفيدة مثل \(S(1)=0\) و\(S(2)=1\) و\(S(5)=4213/871\).
لنكتب \(N=52\)، أو بصورة أعم \(N\) هو أكبر حجم رزمة نريد تقييمه. حساب المضروبات المسبقة يحتاج \(O(N)\) عملية على أعداد صحيحة كبيرة. وحساب جميع قيم \(A_b\) بالإدراج والإقصاء يكلف \(O(N^2)\). وبناء جدول الانتقال \(p_{m,b}\) يكلف أيضًا \(O(N^2)\)، وكذلك البرمجة الديناميكية الخاصة بـ \(T_m\).
إذًا، إذا تجاهلنا الكلفة الداخلية للحسابات عالية الدقة، فإن الخوارزمية كلها تستخدم \(O(N^2)\) خطوة حسابية و\(O(N^2)\) ذاكرة، لأن الجدول المثلثي الكامل للاحتمالات يُخزَّن صراحة. وعند \(N=52\) يكون هذا صغيرًا جدًا عمليًا.