A uniformly shuffled standard deck has \(52\) cards, arranged as \(13\) ranks with \(4\) cards of each rank. A rank is called perfect if no two cards of that rank appear in adjacent positions in the shuffled deck. If \(Y\) denotes the number of perfect ranks, the problem asks for
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
Brute force over all \(52!\) permutations is hopeless, so the implementations reorganize the question into two layers: first compute the probability that every rank in a fixed subset is perfect, then recover the full distribution of \(Y\) from those subset probabilities.
The key observation is that the exact identities of the tracked ranks do not matter; only how many ranks are being tracked matters. That symmetry makes it possible to solve thirteen smaller probability problems and then combine them.
Choose a subset \(S\) of \(j\) ranks, where \(0\le j\le 13\), and define
$$q_j=\Pr(\text{every rank in }S\text{ is perfect}).$$
Because every rank has the same multiplicity and every shuffle is uniform, \(q_j\) depends only on \(j\), not on the actual labels of the ranks in \(S\).
If we can evaluate \(q_j\) for all \(j\), then we can rebuild the distribution of the random variable \(Y\).
For each fixed \(j\)-subset \(S\), let \(I_S\) be the indicator that all ranks in \(S\) are perfect. In any particular shuffle with exactly \(Y\) perfect ranks, the number of \(j\)-subsets that satisfy this is \(\binom{Y}{j}\). Therefore
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
Taking expectations and using symmetry gives
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
Now write
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13.$$
Then the \(j\)-th binomial moment satisfies
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
This is an upper-triangular linear system, so once the \(B_j\) values are known, the exact probabilities \(D_k\) can be recovered by backward substitution.
To compute \(q_j\), imagine revealing the deck from left to right. Cards whose ranks are outside \(S\) are irrelevant except that they can separate two tracked cards and thereby prevent an adjacency violation.
At any point, the state can be summarized by:
$$u=\text{number of remaining cards from untracked ranks},$$
$$a_r=\text{number of tracked ranks with exactly }r\text{ unseen cards left},\qquad r=1,2,3,4,$$
and
$$s=\text{remaining multiplicity of the most recently drawn tracked rank},$$
with the convention \(s=0\) if the previous card was untracked or if the previous tracked rank has already been exhausted.
This compressed description is sufficient because ranks in the same class are exchangeable. The only rank that needs to be distinguished is the most recently drawn tracked rank, since drawing it again immediately would create an adjacent equal-rank pair and destroy perfection for that rank.
The initial state for a subset of size \(j\) is
$$\Psi_j(52-4j,0,0,0,j,0),$$
where \(\Psi_j\) denotes the probability of eventually finishing the reveal with every tracked rank still perfect.
From a state \((u,a_1,a_2,a_3,a_4,s)\), the number of cards still unseen is
$$R=u+a_1+2a_2+3a_3+4a_4.$$
If \(R=0\), the tracked subset has survived the whole shuffle without any forbidden adjacency, so
$$\Psi_j(0,0,0,0,0,0)=1.$$
If an untracked card is drawn, this happens with probability \(u/R\), the count \(u\) drops by \(1\), and the active restriction disappears because an untracked card separates future tracked cards from the previously drawn tracked rank.
If a tracked rank currently belongs to class \(r\), then each such rank contributes \(r\) possible next cards. However, if \(s=r\), one of those ranks is the forbidden rank that cannot be repeated immediately, so the number of eligible ranks in class \(r\) is
$$a_r-\mathbf{1}_{\{s=r\}}.$$
Hence the probability of drawing a tracked card from class \(r\) is
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
After such a draw, one tracked rank moves from class \(r\) to class \(r-1\). The new active value becomes \(r-1\), except that when \(r=1\) the rank is exhausted and the active value resets to \(0\).
Each state has at most five outgoing transitions: one for an untracked card and one for each multiplicity class \(r=1,2,3,4\). Memoization makes this recurrence practical because the same compressed state can be reached through many different reveal histories.
Once \(q_j=\Psi_j(52-4j,0,0,0,j,0)\) is known for every \(j\), we compute
$$B_j=\binom{13}{j}q_j.$$
The triangular relation
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
can then be inverted from \(k=13\) downward:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
Finally, the required probability is
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
For \(j=1\), let us track one specific rank. It is perfect exactly when its four positions in the shuffled deck contain no adjacent pair.
If those positions are
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2,$$
then setting \(y_i=x_i-(i-1)\) transforms them into
$$1\le y_1<y_2<y_3<y_4\le 49.$$
So the number of non-adjacent \(4\)-position choices is \(\binom{49}{4}\), while the total number of \(4\)-position choices is \(\binom{52}{4}\). Therefore
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
By linearity of expectation,
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
This matches the consistency check built into the implementations and confirms that the subset-probability viewpoint is aligned with the combinatorics of the shuffle.
The C++, Python, and Java implementations all follow the same sequence. First they precompute the binomial coefficients \(\binom{n}{k}\) for \(0\le n,k\le 13\). Then, for each subset size \(j\), they evaluate the memoized probability recurrence starting from the initial state with \(j\) tracked ranks and \(52-4j\) untracked cards.
Those thirteen probabilities produce the values \(q_1,\dots,q_{13}\), and from them the implementations form the binomial moments \(B_j=\binom{13}{j}q_j\). The triangular system is then solved backwards to obtain the full distribution \(D_0,D_1,\dots,D_{13}\).
After the distribution is known, the implementation adds the six probabilities corresponding to prime values of \(Y\) and prints the result to ten decimal places. One implementation also checks the identity \(\mathbb{E}[Y]=4324/425\), which is exactly the worked example above written as a sanity test.
For a fixed subset size \(j\), let \(S_j\) be the number of reachable compressed states \((u,a_1,a_2,a_3,a_4,s)\). Memoization ensures that each such state is evaluated once, and each evaluation considers at most five transitions. Therefore the running time for that \(j\) is \(O(S_j)\) and the memory usage is also \(O(S_j)\).
Across all subset sizes, the total cost is
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
where the \(O(13^2)\) term is the final backward substitution. There is no simple closed form for \(S_j\), but the state space is tightly constrained by
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
and by the fact that only \(13\) ranks exist. In practice the reachable-state count is small enough that the exact probability can be computed comfortably.
Ein gleichverteilt gemischtes Standarddeck besitzt \(52\) Karten, also \(13\) Ränge mit jeweils \(4\) Karten. Ein Rang heißt perfekt, wenn keine zwei Karten dieses Rangs auf benachbarten Positionen liegen. Bezeichnet \(Y\) die Anzahl perfekter Ränge, dann gesucht ist
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
Ein direkter Zugriff auf alle \(52!\) Permutationen ist ausgeschlossen. Deshalb zerlegen die Implementierungen das Problem in zwei Stufen: Zuerst wird die Wahrscheinlichkeit berechnet, dass alle Ränge einer festen Teilmenge perfekt sind, danach wird daraus die vollständige Verteilung von \(Y\) rekonstruiert.
Der entscheidende Punkt ist die Symmetrie der Ränge. Für die Rechnung ist nicht wichtig, welche Ränge verfolgt werden, sondern nur wie viele. Dadurch entstehen dreizehn überschaubare Teilprobleme, die sich am Ende wieder zusammensetzen lassen.
Sei \(S\) eine Teilmenge von \(j\) Rängen mit \(0\le j\le 13\). Definiere
$$q_j=\Pr(\text{jeder Rang in }S\text{ ist perfekt}).$$
Weil jeder Rang dieselbe Vielfachheit besitzt und jede Permutation gleich wahrscheinlich ist, hängt \(q_j\) nur von \(j\) ab, nicht von den konkreten Rangbezeichnungen in \(S\).
Sobald alle Werte \(q_j\) bekannt sind, lässt sich die Verteilung der Zufallsvariablen \(Y\) daraus zurückgewinnen.
Für jede feste \(j\)-Teilmenge \(S\) sei \(I_S\) die Indikatorvariable dafür, dass alle Ränge in \(S\) perfekt sind. In einer konkreten Mischung mit genau \(Y\) perfekten Rängen gibt es genau \(\binom{Y}{j}\) solche Teilmengen. Also gilt
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
Nach Erwartungswertbildung und unter Nutzung der Symmetrie folgt
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
Setzen wir außerdem
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13,$$
dann erfüllt das \(j\)-te binomiale Moment die Beziehung
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
Das ist ein obertriangulares lineares Gleichungssystem; sind die \(B_j\) bekannt, so lassen sich die exakten Wahrscheinlichkeiten \(D_k\) per Rückwärtseinsetzen berechnen.
Zur Berechnung von \(q_j\) decken wir das Deck gedanklich von links nach rechts auf. Karten von Rängen außerhalb von \(S\) sind nur insofern relevant, als sie zwei verfolgte Karten trennen und damit eine verbotene Nachbarschaft verhindern können.
Der Zustand lässt sich vollständig beschreiben durch
$$u=\text{Anzahl verbleibender Karten nicht verfolgter Ränge},$$
$$a_r=\text{Anzahl verfolgter Ränge mit genau }r\text{ noch ungesehenen Karten},\qquad r=1,2,3,4,$$
sowie
$$s=\text{Restmultiplizität des zuletzt gezogenen verfolgten Rangs},$$
wobei \(s=0\) bedeutet, dass die vorherige Karte nicht verfolgt war oder dass der vorherige verfolgte Rang bereits vollständig aufgebraucht ist.
Diese Zustandskompression reicht aus, weil alle Ränge innerhalb derselben Klasse austauschbar sind. Unterschieden werden muss nur der zuletzt gezogene verfolgte Rang, denn dessen sofortige Wiederholung würde eine benachbarte Gleichrangigkeit erzeugen und seine Perfektion zerstören.
Der Startzustand für eine Teilmenge der Größe \(j\) lautet
$$\Psi_j(52-4j,0,0,0,j,0),$$
wobei \(\Psi_j\) die Erfolgswahrscheinlichkeit bezeichnet, dass bis zum Ende alle verfolgten Ränge perfekt bleiben.
Aus einem Zustand \((u,a_1,a_2,a_3,a_4,s)\) ist die Zahl der noch ungesehenen Karten
$$R=u+a_1+2a_2+3a_3+4a_4.$$
Ist \(R=0\), dann wurde das gesamte Deck ohne verbotene Nachbarschaft innerhalb der verfolgten Teilmenge aufgedeckt, also
$$\Psi_j(0,0,0,0,0,0)=1.$$
Eine nicht verfolgte Karte wird mit Wahrscheinlichkeit \(u/R\) gezogen. Dann sinkt \(u\) um \(1\), und die aktive Sperre verschwindet, weil diese Karte zukünftige verfolgte Karten vom zuletzt gezogenen verfolgten Rang trennt.
Liegt ein verfolgter Rang in Klasse \(r\), so liefert jeder dieser Ränge \(r\) mögliche nächste Karten. Falls jedoch \(s=r\), ist genau einer dieser Ränge gesperrt, da er nicht sofort wieder erscheinen darf. Die Zahl zulässiger Ränge in Klasse \(r\) ist also
$$a_r-\mathbf{1}_{\{s=r\}}.$$
Damit ist die Wahrscheinlichkeit, eine verfolgte Karte aus Klasse \(r\) zu ziehen, gleich
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
Nach einem solchen Zug wandert genau ein Rang von Klasse \(r\) nach Klasse \(r-1\). Der neue aktive Wert ist \(r-1\), außer bei \(r=1\); dort ist der Rang erschöpft und der aktive Wert springt auf \(0\) zurück.
Jeder Zustand besitzt höchstens fünf ausgehende Übergänge: einen für eine nicht verfolgte Karte und je einen für die Klassen \(r=1,2,3,4\). Durch Memoisierung wird die Rekursion praktikabel, weil derselbe komprimierte Zustand auf vielen verschiedenen Aufdeckpfaden wiederkehrt.
Sobald \(q_j=\Psi_j(52-4j,0,0,0,j,0)\) für alle \(j\) bekannt ist, berechnen wir
$$B_j=\binom{13}{j}q_j.$$
Die obere Dreiecksbeziehung
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
wird dann für \(k=13,12,\dots,0\) rückwärts invertiert:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
Gesucht ist schließlich
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
Für \(j=1\) verfolgen wir genau einen bestimmten Rang. Er ist genau dann perfekt, wenn seine vier Positionen im Deck kein benachbartes Paar bilden.
Sind diese Positionen
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2,$$
dann führt die Transformation \(y_i=x_i-(i-1)\) auf
$$1\le y_1<y_2<y_3<y_4\le 49.$$
Also gibt es \(\binom{49}{4}\) zulässige nicht-benachbarte Positionsmengen und insgesamt \(\binom{52}{4}\) Positionsmengen. Damit
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
Mit Linearität des Erwartungswerts folgt
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
Genau dieser Wert wird in den Implementierungen als Konsistenzprüfung verwendet; er bestätigt, dass die Teilmengenperspektive perfekt zur Kombinatorik des Mischens passt.
Die C++-, Python- und Java-Implementierungen benutzen alle dieselbe Reihenfolge. Zunächst werden die Binomialkoeffizienten \(\binom{n}{k}\) für \(0\le n,k\le 13\) vorbereitet. Danach wird für jede Teilmengengröße \(j\) die memoisierten Wahrscheinlichkeitsrekursion aus dem Anfangszustand mit \(j\) verfolgten Rängen und \(52-4j\) nicht verfolgten Karten ausgewertet.
Aus diesen dreizehn Wahrscheinlichkeiten entstehen die Werte \(q_1,\dots,q_{13}\), und daraus die binomialen Momente \(B_j=\binom{13}{j}q_j\). Anschließend wird das obere Dreieckssystem rückwärts gelöst, um die vollständige Verteilung \(D_0,D_1,\dots,D_{13}\) zu erhalten.
Zum Schluss addiert die Implementierung die sechs Wahrscheinlichkeiten zu den primen Werten von \(Y\) und gibt das Ergebnis mit zehn Nachkommastellen aus. Eine der Implementierungen überprüft außerdem die Identität \(\mathbb{E}[Y]=4324/425\), also genau das Resultat des obigen Beispiels.
Für eine feste Teilmengengröße \(j\) sei \(S_j\) die Anzahl erreichbarer komprimierter Zustände \((u,a_1,a_2,a_3,a_4,s)\). Durch Memoisierung wird jeder solche Zustand höchstens einmal ausgewertet, und pro Auswertung gibt es höchstens fünf Übergänge. Daher beträgt die Laufzeit für dieses \(j\) gleich \(O(S_j)\), ebenso der Speicherbedarf.
Über alle Teilmengengrößen hinweg ergibt sich also
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
wobei \(O(13^2)\) vom abschließenden Rückwärtseinsetzen stammt. Für \(S_j\) gibt es keine einfache geschlossene Formel, doch der Zustandsraum ist stark eingeschränkt durch
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
und dadurch, dass insgesamt nur \(13\) Ränge existieren. In der Praxis bleibt die Zahl erreichbarer Zustände klein genug, um die exakte Wahrscheinlichkeit bequem zu berechnen.
Standart bir deste \(52\) karttan oluşur; yani \(13\) farklı rank vardır ve her ranktan \(4\) kart bulunur. Bir rank, bu ranka ait hiçbir iki kart destede yan yana gelmiyorsa perfect kabul edilir. \(Y\) perfect rank sayısı olmak üzere istenen büyüklük
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)$$
olasılığıdır. \(52!\) farklı karışımı doğrudan incelemek mümkün olmadığından, çözümler problemi iki katmana ayırır: önce sabit bir rank altkümesinin tamamının perfect olma olasılığı hesaplanır, sonra bu bilgilerden \(Y\)'nin tam dağılımı geri elde edilir.
Temel fikir simetridir. Hangi rankların izlendiği önemli değildir; sadece kaç rank izlendiği önemlidir. Bu sayede problem, çözülebilir büyüklükte on üç alt probleme ayrılır ve sonuçta tekrar birleştirilir.
\(0\le j\le 13\) için \(j\) ranktan oluşan sabit bir \(S\) altkümesi seçelim ve
$$q_j=\Pr(\text{\(S\) içindeki her rank perfect})$$
tanımını yapalım. Her rankın çokluğu aynı ve karıştırma düzgün rastgele olduğu için \(q_j\) değeri altkümenin etiketlerine değil, yalnızca büyüklüğüne bağlıdır.
Tüm \(q_j\) değerleri bilindiğinde, rastgele değişken \(Y\)'nin dağılımı bu bilgilerden çıkarılabilir.
Sabit bir \(j\)-elemanlı \(S\) altkümesi için \(I_S\), tüm bu rankların perfect olmasını gösteren gösterge değişkeni olsun. Belirli bir karışımda tam olarak \(Y\) tane perfect rank varsa, bu özelliği sağlayan \(j\)-li altküme sayısı tam olarak \(\binom{Y}{j}\) olur. Dolayısıyla
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
Beklenen değer alırsak ve simetriyi kullanırsak
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right]$$
eşitliğini elde ederiz. Ayrıca
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13$$
tanımlanırsa, \(j\). binom momenti şu bağıntıyı sağlar:
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
Bu, üst üçgensel bir lineer sistemdir; dolayısıyla \(B_j\) değerleri bilindiğinde tüm \(D_k\) olasılıkları geriye doğru çözülerek bulunabilir.
\(q_j\)'yi hesaplamak için desteyi soldan sağa açtığımızı düşünelim. \(S\) dışındaki ranklara ait kartlar yalnızca ayırıcı rol oynar; iki izlenen kartın arasına girerek yasak komşuluğu engelleyebilirler.
Her anda durum şu bilgilerle tamamen özetlenebilir:
$$u=\text{izlenmeyen ranklardan kalan kart sayısı},$$
$$a_r=\text{tam olarak }r\text{ görülmemiş kartı kalan izlenen rank sayısı},\qquad r=1,2,3,4,$$
ve
$$s=\text{en son çekilen izlenen rankın kalan çokluğu}.$$
Burada \(s=0\), önceki kart izlenmeyen bir ranktansa veya önceki izlenen rank tamamen bittiyse kullanılır.
Bu özet yeterlidir çünkü aynı sınıftaki ranklar birbirinden ayırt edilemez. Ayrı tutulması gereken tek rank, en son çekilen izlenen ranktır; çünkü onu hemen tekrar çekmek, yan yana eş-ranklı bir çift oluşturur ve o rankın perfect olma durumunu bozar.
\(j\) elemanlı bir altküme için başlangıç durumu
$$\Psi_j(52-4j,0,0,0,j,0)$$
şeklindedir. Burada \(\Psi_j\), mevcut durumdan başlanınca tüm izlenen rankların sona kadar perfect kalma olasılığıdır.
\((u,a_1,a_2,a_3,a_4,s)\) durumunda henüz açılmamış kart sayısı
$$R=u+a_1+2a_2+3a_3+4a_4$$
olur. Eğer \(R=0\) ise izlenen altküme, bütün deste boyunca yasak komşuluk oluşturmadan hayatta kalmıştır; yani
$$\Psi_j(0,0,0,0,0,0)=1.$$
İzlenmeyen bir kart gelme olasılığı \(u/R\)'dir. Bu durumda \(u\) bir azalır ve aktif yasak ortadan kalkar; çünkü araya izlenmeyen bir kart girdiğinden, bundan sonra gelen izlenen kartlar önceki izlenen kartla komşu sayılmaz.
Bir izlenen rank şu anda \(r\) sınıfındaysa, bu sınıftaki her rank bir sonraki kart için \(r\) seçenek üretir. Fakat \(s=r\) ise bu sınıftaki ranklardan biri yasaklıdır; en son çekilen izlenen rank hemen tekrar gelemez. Bu yüzden \(r\) sınıfındaki uygun rank sayısı
$$a_r-\mathbf{1}_{\{s=r\}}$$
olur. Dolayısıyla \(r\) sınıfından bir izlenen kart çekme olasılığı
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}$$
şeklindedir. Böyle bir çekişten sonra tam bir rank, \(r\) sınıfından \(r-1\) sınıfına iner. Yeni aktif değer \(r-1\)'dir; yalnız \(r=1\) durumunda rank tamamen bittiği için aktif değer yeniden \(0\) olur.
Her durumun en fazla beş çıkışı vardır: bir izlenmeyen kart geçişi ve \(r=1,2,3,4\) sınıfları için birer geçiş. Aynı sıkıştırılmış duruma çok farklı açılma geçmişlerinden ulaşılabildiği için, bellekli arama bu yinelemeyi pratik hale getirir.
Tüm \(j\) değerleri için \(q_j=\Psi_j(52-4j,0,0,0,j,0)\) bilindiğinde
$$B_j=\binom{13}{j}q_j$$
hesaplanır. Ardından
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
ilişkisi \(k=13\)'ten başlayarak tersten çözülür:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
Sonuçta aranan olasılık
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}$$
olur.
\(j=1\) iken tek bir belirli rankı izleyelim. Bu rank ancak dört kartının konumları arasında bitişik bir çift yoksa perfect olur.
Bu konumlar
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2$$
olsun. \(y_i=x_i-(i-1)\) dönüşümüyle
$$1\le y_1<y_2<y_3<y_4\le 49$$
elde edilir. Demek ki ardışık olmayan \(4\)-lü konum seçimlerinin sayısı \(\binom{49}{4}\), toplam \(4\)-lü konum seçimlerinin sayısı ise \(\binom{52}{4}\)'tür. Böylece
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}$$
bulunur. Beklenen değerin lineerliğiyle
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}$$
olur. Bu değer implementasyonlardaki tutarlılık kontrolüyle aynıdır ve altküme-olasılığı bakışının doğru kurulduğunu gösterir.
C++, Python ve Java implementasyonlarının akışı aynıdır. Önce \(\binom{n}{k}\) değerleri \(0\le n,k\le 13\) için hazırlanır. Sonra her \(j\) altküme büyüklüğü için, \(j\) izlenen rank ve \(52-4j\) izlenmeyen kart içeren başlangıç durumundan memoize edilmiş olasılık yinelemesi hesaplanır.
Bu on üç olasılık \(q_1,\dots,q_{13}\) değerlerini üretir; bunlardan da \(B_j=\binom{13}{j}q_j\) binom momentleri kurulur. Daha sonra üst üçgensel sistem geriye doğru çözülerek \(D_0,D_1,\dots,D_{13}\) tam dağılımı elde edilir.
Son adımda implementasyon, \(Y\)'nin asal değerlerine karşılık gelen altı olasılığı toplar ve sonucu ondalık olarak yazar. İçlerinden biri ayrıca \(\mathbb{E}[Y]=4324/425\) kimliğini doğrular; bu da yukarıdaki örneğin test halidir.
Sabit bir \(j\) için erişilebilen sıkıştırılmış durum sayısına \(S_j\) diyelim. Bellekleme sayesinde her durum en fazla bir kez değerlendirilir ve her değerlendirme en çok beş geçiş içerir. Dolayısıyla bu \(j\) için zaman karmaşıklığı \(O(S_j)\), bellek karmaşıklığı da \(O(S_j)\) olur.
Tüm altküme büyüklükleri boyunca toplam maliyet
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2)$$
şeklindedir; buradaki \(O(13^2)\) son ters çözüm adımından gelir. \(S_j\) için basit bir kapalı form yoktur, ancak durum uzayı
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
korunumu ve toplamda yalnızca \(13\) rank bulunması nedeniyle ciddi biçimde sınırlıdır. Pratikte erişilebilir durum sayısı, tam olasılığı rahatça hesaplayacak kadar küçüktür.
Una baraja estándar barajada uniformemente tiene \(52\) cartas, es decir, \(13\) rangos con \(4\) cartas por rango. Un rango se llama perfecto si ninguna pareja de cartas de ese rango aparece en posiciones adyacentes. Si \(Y\) es el número de rangos perfectos, el problema pide calcular
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
Enumerar las \(52!\) permutaciones es imposible, así que las implementaciones dividen el trabajo en dos etapas: primero calculan la probabilidad de que todos los rangos de un subconjunto fijo sean perfectos y luego reconstruyen la distribución completa de \(Y\) a partir de esas probabilidades parciales.
La simetría entre rangos es la clave. No importa qué rangos concretos sigamos, sino cuántos seguimos. Gracias a esa observación, el problema se reduce a trece cálculos de probabilidad más pequeños que luego se recombinan.
Tomemos un subconjunto \(S\) de \(j\) rangos, con \(0\le j\le 13\), y definamos
$$q_j=\Pr(\text{todos los rangos de }S\text{ son perfectos}).$$
Como todos los rangos tienen la misma multiplicidad y la baraja está barajada de forma uniforme, \(q_j\) depende solo de \(j\), no de las etiquetas concretas de los rangos elegidos.
Una vez conocidos todos los valores \(q_j\), ya es posible reconstruir la distribución de la variable aleatoria \(Y\).
Para cada subconjunto fijo \(S\) de tamaño \(j\), sea \(I_S\) el indicador del suceso “todos los rangos de \(S\) son perfectos”. En una baraja concreta con exactamente \(Y\) rangos perfectos, el número de subconjuntos de tamaño \(j\) que cumplen esto es \(\binom{Y}{j}\). Por tanto,
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
Al tomar esperanza y usar la simetría obtenemos
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
Si además escribimos
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13,$$
entonces el \(j\)-ésimo momento binomial satisface
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
Esta es una relación triangular superior, de modo que los \(D_k\) exactos se recuperan por sustitución hacia atrás una vez que los \(B_j\) ya se conocen.
Para calcular \(q_j\), imaginamos que revelamos la baraja carta por carta. Las cartas cuyos rangos no pertenecen a \(S\) solo importan como separadores: pueden quedar entre dos cartas seguidas del conjunto seguido y así evitar una adyacencia prohibida.
En cualquier momento, el estado queda descrito por
$$u=\text{número de cartas restantes de rangos no seguidos},$$
$$a_r=\text{número de rangos seguidos con exactamente }r\text{ cartas aún no vistas},\qquad r=1,2,3,4,$$
y también por
$$s=\text{multiplicidad restante del rango seguido extraído más recientemente}.$$
Usamos la convención \(s=0\) si la carta anterior no era de un rango seguido o si ese rango seguido ya se agotó por completo.
Esta compresión basta porque los rangos dentro de una misma clase son indistinguibles. El único rango que debe permanecer distinguido es el último rango seguido extraído, ya que repetirlo inmediatamente produciría una pareja adyacente de igual rango y destruiría su condición de perfecto.
El estado inicial para un subconjunto de tamaño \(j\) es
$$\Psi_j(52-4j,0,0,0,j,0),$$
donde \(\Psi_j\) representa la probabilidad de terminar la revelación sin que ningún rango seguido viole la condición de perfección.
Desde un estado \((u,a_1,a_2,a_3,a_4,s)\), el número total de cartas aún no vistas es
$$R=u+a_1+2a_2+3a_3+4a_4.$$
Si \(R=0\), entonces el subconjunto seguido ha sobrevivido toda la baraja sin adyacencias prohibidas, así que
$$\Psi_j(0,0,0,0,0,0)=1.$$
Si sale una carta no seguida, esto ocurre con probabilidad \(u/R\), la cantidad \(u\) baja en \(1\) y la restricción activa desaparece, porque esa carta separa las futuras cartas seguidas de la última carta seguida extraída.
Si un rango seguido está en la clase \(r\), cada uno de esos rangos aporta \(r\) cartas posibles para el siguiente paso. Sin embargo, cuando \(s=r\), uno de esos rangos es precisamente el rango prohibido que no puede repetirse de inmediato. Por eso, el número de rangos elegibles en la clase \(r\) es
$$a_r-\mathbf{1}_{\{s=r\}}.$$
La probabilidad de robar una carta seguida desde la clase \(r\) es entonces
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
Después de ese robo, un rango pasa de la clase \(r\) a la clase \(r-1\). El nuevo valor activo pasa a ser \(r-1\), salvo cuando \(r=1\), caso en el cual el rango se agota y el valor activo vuelve a \(0\).
Cada estado tiene como mucho cinco transiciones salientes: una para una carta no seguida y una por cada clase de multiplicidad \(r=1,2,3,4\). La memorización hace viable la recurrencia porque el mismo estado comprimido puede alcanzarse por muchos historiales distintos.
Una vez conocido \(q_j=\Psi_j(52-4j,0,0,0,j,0)\) para todo \(j\), calculamos
$$B_j=\binom{13}{j}q_j.$$
La relación triangular
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
se invierte después desde \(k=13\) hacia abajo:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
Por último, la probabilidad pedida es
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
Para \(j=1\), seguimos un rango concreto. Ese rango es perfecto exactamente cuando sus cuatro posiciones en la baraja no contienen ninguna pareja adyacente.
Si dichas posiciones son
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2,$$
la transformación \(y_i=x_i-(i-1)\) las convierte en
$$1\le y_1<y_2<y_3<y_4\le 49.$$
Así, el número de elecciones de \(4\) posiciones sin adyacencias es \(\binom{49}{4}\), mientras que el número total de elecciones de \(4\) posiciones es \(\binom{52}{4}\). Por tanto,
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
Usando linealidad de la esperanza,
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
Ese valor coincide con la comprobación interna de las implementaciones y confirma que el punto de vista basado en subconjuntos está perfectamente alineado con la combinatoria del problema.
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia. Primero precalculan los coeficientes binomiales \(\binom{n}{k}\) para \(0\le n,k\le 13\). Después, para cada tamaño de subconjunto \(j\), evalúan la recurrencia de probabilidad memorizada desde el estado inicial con \(j\) rangos seguidos y \(52-4j\) cartas no seguidas.
Esas trece probabilidades producen los valores \(q_1,\dots,q_{13}\), y con ellos se forman los momentos binomiales \(B_j=\binom{13}{j}q_j\). A continuación se resuelve hacia atrás el sistema triangular para obtener la distribución completa \(D_0,D_1,\dots,D_{13}\).
Una vez conocida la distribución, la implementación suma las seis probabilidades correspondientes a valores primos de \(Y\) e imprime el resultado con diez decimales. Una de las implementaciones también verifica la identidad \(\mathbb{E}[Y]=4324/425\), que es exactamente el ejemplo anterior convertido en prueba de consistencia.
Para un tamaño fijo \(j\), sea \(S_j\) el número de estados comprimidos alcanzables \((u,a_1,a_2,a_3,a_4,s)\). La memorización garantiza que cada estado se evalúe una sola vez, y cada evaluación considera como máximo cinco transiciones. Por tanto, el tiempo para ese \(j\) es \(O(S_j)\) y la memoria también es \(O(S_j)\).
Sumando todos los tamaños de subconjunto, el coste total es
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
donde el término \(O(13^2)\) proviene de la inversión triangular final. No existe una forma cerrada sencilla para \(S_j\), pero el espacio de estados está fuertemente restringido por
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
y por el hecho de que solo existen \(13\) rangos. En la práctica, el número de estados alcanzables es lo bastante pequeño como para que el cálculo exacto sea cómodo.
一副标准扑克牌共有 \(52\) 张，也就是 \(13\) 个点数，每个点数恰好出现 \(4\) 次。若某个点数的四张牌在洗牌后的排列中没有任何两张相邻，则称这个点数是 perfect 的。记 \(Y\) 为 perfect 点数的个数，则题目要求计算
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
直接在 \(52!\) 个排列上暴力统计完全不可行，因此实现采用两层思路：先求“一个固定点数子集全部 perfect”的概率，再把这些子集概率还原成 \(Y\) 的完整分布。
这道题真正可利用的是点数之间的对称性。我们并不关心跟踪的是哪几个具体点数，只关心一共跟踪了多少个点数。利用这一点，可以把问题拆成 \(j=0,1,\dots,13\) 这几个规模很小的概率问题，再把答案组合回来。
取一个大小为 \(j\) 的点数子集 \(S\)，其中 \(0\le j\le 13\)，定义
$$q_j=\Pr(\text{子集 }S\text{ 中的每个点数都是 perfect}).$$
由于每个点数都出现四次，而且所有洗牌结果等概率，\(q_j\) 只依赖于 \(j\)，与 \(S\) 里究竟是哪几个点数无关。
因此，只要我们能对每个 \(j\) 算出 \(q_j\)，就已经掌握了恢复随机变量 \(Y\) 分布所需的原材料。
对每个固定的 \(j\) 元子集 \(S\)，定义指标变量 \(I_S\)：当且仅当 \(S\) 中所有点数都 perfect 时，\(I_S=1\)。如果某个具体洗牌结果中一共有 \(Y\) 个 perfect 点数，那么满足条件的 \(j\) 元子集个数恰好是 \(\binom{Y}{j}\)。于是有
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
对两边取期望，并利用“所有同样大小的子集概率相同”这一对称性，就得到
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
再记
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13,$$
那么第 \(j\) 个二项矩满足
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
这是一个上三角线性系统，因此只要 \(B_j\) 全部已知，就可以从大到小回代，精确恢复每个 \(D_k\)。
为了计算 \(q_j\)，我们把洗牌后的牌堆想象成从左到右依次揭开。对子集 \(S\) 之外的点数而言，它们本身是否 perfect 不重要；它们的作用只是充当“分隔符”，把两张被跟踪的牌隔开，从而避免不合法的相邻。
在任意时刻，状态可以完全压缩为以下几项信息：
$$u=\text{未跟踪点数剩余的牌张数},$$
$$a_r=\text{仍有 }r\text{ 张未揭开的被跟踪点数个数},\qquad r=1,2,3,4,$$
以及
$$s=\text{最近一次揭开的被跟踪点数，在揭开后还剩多少张牌}.$$
这里约定 \(s=0\) 表示上一张牌不是被跟踪点数，或者上一张被跟踪点数已经完全耗尽。
为什么这些信息就够了？因为同一类中的点数是完全对称的。例如，所有“还剩 3 张”的被跟踪点数彼此没有区别。唯一需要被单独标记的是“上一张来自哪个被跟踪点数”，因为如果下一张马上又来自它，就会形成相邻的同点数牌，从而立刻破坏这个点数的 perfect 条件。
对大小为 \(j\) 的子集，初始状态是
$$\Psi_j(52-4j,0,0,0,j,0),$$
其中 \(\Psi_j\) 表示从当前状态继续揭牌，最终使所有被跟踪点数都保持 perfect 的概率。
在状态 \((u,a_1,a_2,a_3,a_4,s)\) 下，尚未揭开的总牌数为
$$R=u+a_1+2a_2+3a_3+4a_4.$$
若 \(R=0\)，说明整副牌已经揭完，而且从未出现任何被跟踪点数的违规相邻，因此
$$\Psi_j(0,0,0,0,0,0)=1.$$
如果下一张是未跟踪点数，那么其概率为 \(u/R\)。这时 \(u\) 减少 \(1\)，同时活动限制清空，因为插入了一张未跟踪牌之后，之后再出现被跟踪牌就不再和刚才那张被跟踪牌相邻。
如果下一张来自当前“还剩 \(r\) 张”的某个被跟踪点数，那么这一类里每个点数都贡献 \(r\) 张可能的牌。但当 \(s=r\) 时，这一类中恰好有一个点数是刚刚出现过的那个点数，它不能立刻重复出现。因此，这一类中真正可选的点数个数是
$$a_r-\mathbf{1}_{\{s=r\}}.$$
于是，从第 \(r\) 类抽到下一张被跟踪牌的概率是
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
抽到之后，会有一个点数从“还剩 \(r\) 张”转移到“还剩 \(r-1\) 张”。新的活动限制值变成 \(r-1\)；如果 \(r=1\)，说明该点数已经抽完，于是活动限制重新变回 \(0\)。
因此，每个状态最多只有五种出边：一种是抽到未跟踪牌，另外四种分别对应 \(r=1,2,3,4\) 这四个剩余张数类。由于很多不同的揭牌路径会汇合到同一个压缩状态，记忆化正是让递推可行的关键。
当所有 \(q_j=\Psi_j(52-4j,0,0,0,j,0)\) 都算出来之后，先构造
$$B_j=\binom{13}{j}q_j.$$
然后利用
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
这个上三角关系，从 \(k=13\) 开始向下回代：
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
最终所求概率就是
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
当 \(j=1\) 时，只跟踪一个指定点数。这个点数 perfect，当且仅当它的四张牌在整副牌中的四个位置没有任何一对相邻。
设这四个位置为
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2.$$
令 \(y_i=x_i-(i-1)\)，那么条件就变成
$$1\le y_1<y_2<y_3<y_4\le 49.$$
这说明“不相邻的四个位置”的选法有 \(\binom{49}{4}\) 种，而任取四个位置总共有 \(\binom{52}{4}\) 种，所以
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
再利用期望的线性性，就得到
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
这个值正好与实现中的一致性检查吻合，也说明“先算子集概率，再还原总体分布”的思路与题目的组合结构完全一致。
C++、Python 和 Java 实现遵循完全相同的流程。首先预计算 \(\binom{n}{k}\)（其中 \(0\le n,k\le 13\)）。然后对每个子集大小 \(j\)，从“有 \(j\) 个被跟踪点数、\(52-4j\) 张未跟踪牌”的初始状态出发，计算记忆化概率递推。
这样就得到 \(q_1,\dots,q_{13}\)。接下来把它们转换成二项矩 \(B_j=\binom{13}{j}q_j\)，再通过上三角系统的回代求出完整分布 \(D_0,D_1,\dots,D_{13}\)。
最后，程序把 \(Y\) 取素数值时对应的六个概率相加，并按十位小数输出。其中一个实现还额外检查了 \(\mathbb{E}[Y]=4324/425\) 这个恒等式，也就是上面单点数例子的结论。
对固定的 \(j\)，设 \(S_j\) 为可达压缩状态 \((u,a_1,a_2,a_3,a_4,s)\) 的数量。由于采用记忆化，每个状态只会被计算一次，而每次计算最多考虑五个转移，因此这一层的时间复杂度是 \(O(S_j)\)，空间复杂度也是 \(O(S_j)\)。
把 \(j=1\) 到 \(13\) 全部加起来，总复杂度为
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
其中 \(O(13^2)\) 来自最终的回代求解。虽然 \(S_j\) 没有一个简洁的闭式，但状态空间受到
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
以及“总共只有 \(13\) 个点数”这两个条件的强烈限制，所以实际可达状态数足够小，精确计算完全可行。
Стандартная колода после равновероятного перемешивания содержит \(52\) карты, то есть \(13\) рангов по \(4\) карты каждого ранга. Ранг назовем идеальным, если никакие две карты этого ранга не стоят рядом в итоговой перестановке. Пусть \(Y\) обозначает число идеальных рангов. Требуется найти
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
Полный перебор \(52!\) перестановок невозможен, поэтому реализации решают задачу в два этапа: сначала считают вероятность того, что все ранги из фиксированного подмножества идеальны, а затем восстанавливают полное распределение \(Y\) по этим вероятностям.
Главная идея состоит в симметрии рангов. Важно не то, какие именно ранги мы отслеживаем, а только то, сколько их отслеживается. Благодаря этому задача разбивается на тринадцать небольших вероятностных расчетов, которые затем объединяются.
Пусть \(S\) — фиксированное подмножество из \(j\) рангов, где \(0\le j\le 13\). Определим
$$q_j=\Pr(\text{каждый ранг из }S\text{ идеален}).$$
Поскольку каждый ранг встречается ровно четыре раза и все перестановки колоды равновероятны, величина \(q_j\) зависит только от числа \(j\), а не от конкретных названий рангов в \(S\).
Когда все значения \(q_j\) известны, из них уже можно восстановить распределение случайной величины \(Y\).
Для каждого фиксированного \(j\)-элементного подмножества \(S\) введем индикатор \(I_S\), равный \(1\), если все ранги из \(S\) идеальны. В любой конкретной перестановке, где идеальных рангов ровно \(Y\), число подмножеств размера \(j\), состоящих целиком из идеальных рангов, равно \(\binom{Y}{j}\). Следовательно,
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
Берем математическое ожидание и используем симметрию:
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
Если теперь обозначить
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13,$$
то получаем соотношение
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
Это верхнетреугольная линейная система, поэтому после вычисления \(B_j\) точные вероятности \(D_k\) извлекаются обратной подстановкой.
Чтобы вычислить \(q_j\), мысленно открываем карты слева направо. Карты рангов вне \(S\) сами по себе неинтересны; они важны лишь как разделители, которые могут разорвать потенциальную соседнюю пару отслеживаемого ранга.
В любой момент состояние полностью описывается величинами
$$u=\text{число оставшихся карт неотслеживаемых рангов},$$
$$a_r=\text{число отслеживаемых рангов, у которых осталось ровно }r\text{ неоткрытых карт},\qquad r=1,2,3,4,$$
а также параметром
$$s=\text{остаточная кратность последнего открытого отслеживаемого ранга}.$$
Здесь \(s=0\) означает, что предыдущая карта не принадлежала отслеживаемому рангу или что предыдущий отслеживаемый ранг уже полностью исчерпан.
Этого достаточно, потому что все ранги внутри одной и той же группы симметричны. Выделять отдельно нужно только последний открытый отслеживаемый ранг, поскольку его немедленное повторение создало бы соседнюю пару одинакового ранга и разрушило бы условие идеальности.
Начальное состояние для подмножества размера \(j\) имеет вид
$$\Psi_j(52-4j,0,0,0,j,0),$$
где \(\Psi_j\) — вероятность успешно дойти до конца колоды, не нарушив идеальность ни одного отслеживаемого ранга.
Из состояния \((u,a_1,a_2,a_3,a_4,s)\) общее число еще неоткрытых карт равно
$$R=u+a_1+2a_2+3a_3+4a_4.$$
Если \(R=0\), значит, вся колода уже пройдена и ни одно запрещенное соседство не возникло, поэтому
$$\Psi_j(0,0,0,0,0,0)=1.$$
Неотслеживаемая карта вытягивается с вероятностью \(u/R\). Тогда \(u\) уменьшается на \(1\), а активный запрет исчезает, потому что такая карта отделяет будущие отслеживаемые карты от последнего отслеживаемого ранга.
Если некоторый отслеживаемый ранг находится в классе \(r\), то каждый такой ранг дает \(r\) возможных карт для следующего шага. Но если \(s=r\), то один из этих рангов временно запрещен: это тот самый ранг, который только что встретился и не может повториться немедленно. Поэтому число допустимых рангов в классе \(r\) равно
$$a_r-\mathbf{1}_{\{s=r\}}.$$
Отсюда вероятность вытянуть отслеживаемую карту из класса \(r\) равна
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
После такого хода один ранг переходит из класса \(r\) в класс \(r-1\). Новый активный параметр становится равным \(r-1\), а при \(r=1\) ранг полностью исчерпан, и активный параметр возвращается к \(0\).
У каждого состояния не более пяти исходящих переходов: один для неотслеживаемой карты и по одному для классов \(r=1,2,3,4\). Мемоизация делает рекурсию эффективной, поскольку одно и то же сжатое состояние достигается множеством разных историй открытия колоды.
Когда для всех \(j\) найдены значения \(q_j=\Psi_j(52-4j,0,0,0,j,0)\), вычисляем
$$B_j=\binom{13}{j}q_j.$$
Далее используем треугольное соотношение
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
и инвертируем его сверху вниз:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
Искомая вероятность после этого равна
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
При \(j=1\) мы отслеживаем один конкретный ранг. Он идеален тогда и только тогда, когда четыре его позиции в колоде не содержат соседних значений.
Пусть эти позиции равны
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2.$$
Положив \(y_i=x_i-(i-1)\), получаем эквивалентную систему
$$1\le y_1<y_2<y_3<y_4\le 49.$$
Значит, число допустимых наборов позиций без соседства равно \(\binom{49}{4}\), а общее число наборов четырех позиций равно \(\binom{52}{4}\). Следовательно,
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
По линейности ожидания
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
Этот результат совпадает со встроенной проверкой в реализациях и подтверждает корректность всей схемы с подмножествами рангов.
Реализации на C++, Python и Java используют один и тот же алгоритмический конвейер. Сначала они заранее строят таблицу биномиальных коэффициентов \(\binom{n}{k}\) для \(0\le n,k\le 13\). Затем для каждого размера подмножества \(j\) вычисляют мемоизированную рекуррентную вероятность, стартуя из состояния с \(j\) отслеживаемыми рангами и \(52-4j\) неотслеживаемыми картами.
Эти тринадцать вероятностей дают значения \(q_1,\dots,q_{13}\), из которых формируются биномиальные моменты \(B_j=\binom{13}{j}q_j\). После этого верхнетреугольная система решается обратной подстановкой, что дает полное распределение \(D_0,D_1,\dots,D_{13}\).
На последнем шаге реализация суммирует шесть вероятностей, соответствующих простым значениям \(Y\), и печатает ответ с точностью до десяти знаков после запятой. Одна из реализаций дополнительно проверяет тождество \(\mathbb{E}[Y]=4324/425\), то есть именно тот результат, который был выведен в разобранном примере.
Для фиксированного \(j\) обозначим через \(S_j\) число достижимых сжатых состояний \((u,a_1,a_2,a_3,a_4,s)\). Мемоизация гарантирует, что каждое такое состояние вычисляется только один раз, а из каждого состояния есть не более пяти переходов. Значит, время для данного \(j\) равно \(O(S_j)\), и память тоже равна \(O(S_j)\).
Суммарная стоимость по всем размерам подмножеств составляет
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
где член \(O(13^2)\) соответствует финальной обратной подстановке. Простой замкнутой формулы для \(S_j\) нет, но пространство состояний сильно ограничено условиями
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
и тем фактом, что в колоде всего \(13\) рангов. На практике число достижимых состояний остается достаточно малым для комфортного точного расчета.
الرزمة القياسية بعد خلطٍ عشوائي منتظم تحتوي على \(52\) ورقة، أي \(13\) رتبة ولكل رتبة \(4\) أوراق. نسمي الرتبة مثالية إذا لم تظهر أي ورقتين من تلك الرتبة في موضعين متجاورين داخل الترتيب النهائي. إذا كان \(Y\) هو عدد الرتب المثالية، فالمطلوب هو حساب
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right).$$
العد المباشر على جميع التبديلات وعددها \(52!\) غير ممكن، لذلك تقسم التطبيقات المسألة إلى مرحلتين: أولًا نحسب احتمال أن تكون كل الرتب داخل مجموعة ثابتة مثالية، ثم نستعيد من هذه الاحتمالات التوزيع الكامل للمتغير \(Y\).
الفكرة الحاسمة هي التناظر بين الرتب. لا يهم أي رتب نختار، بل المهم فقط كم رتبة نتابع. هذا يسمح بتحويل المسألة إلى ثلاث عشرة مسألة احتمالية أصغر ثم جمعها من جديد.
لنأخذ مجموعة ثابتة \(S\) من \(j\) رتب حيث \(0\le j\le 13\)، ونعرّف \(q_j\) على أنه احتمال أن تكون كل رتبة في \(S\) مثالية.
بما أن كل رتبة تظهر أربع مرات، وبما أن كل خلط ممكن متساوي الاحتمال، فإن \(q_j\) يعتمد فقط على \(j\)، لا على أسماء الرتب الموجودة في \(S\).
بمجرد معرفة جميع القيم \(q_j\)، يصبح من الممكن استرجاع توزيع المتغير العشوائي \(Y\).
لكل مجموعة ثابتة \(S\) ذات حجم \(j\)، ليكن \(I_S\) هو متغير المؤشر للحدث القائل إن جميع رتب \(S\) مثالية. في أي خلط يحتوي على \(Y\) رتب مثالية بالضبط، فإن عدد المجموعات ذات الحجم \(j\) المؤلفة بالكامل من رتب مثالية يساوي \(\binom{Y}{j}\). لذلك
$$\sum_{\lvert S\rvert=j} I_S=\binom{Y}{j}.$$
وبأخذ التوقع، ثم استعمال التناظر، نحصل على
$$B_j=\binom{13}{j}q_j=\mathbb{E}\!\left[\binom{Y}{j}\right].$$
وإذا كتبنا أيضًا
$$D_k=\Pr(Y=k),\qquad 0\le k\le 13,$$
فإن العزم الثنائي رقم \(j\) يحقق العلاقة
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k.$$
هذه منظومة مثلثية علوية، ولذلك يمكن استرجاع جميع الاحتمالات \(D_k\) بالرجوع من الأعلى إلى الأسفل بعد معرفة قيم \(B_j\).
لحساب \(q_j\)، نتخيل أننا نكشف أوراق الرزمة من اليسار إلى اليمين. الأوراق التي تنتمي إلى رتب خارج \(S\) لا تهم بذاتها، لكنها قد تعمل كفواصل بين ورقتين متتبعتين، وبذلك تمنع حدوث تجاور ممنوع.
يمكن تلخيص الحالة في أي لحظة بالمعطيات التالية:
نكتب \(u\) لعدد الأوراق المتبقية من الرتب غير المتتبعة.
ونكتب \(a_r\) لعدد الرتب المتتبعة التي بقي لها بالضبط \(r\) أوراق غير مكشوفة، حيث \(r=1,2,3,4\).
ونكتب \(s\) لعدد الأوراق المتبقية من آخر رتبة متتبعة ظهرت.
ونأخذ الاصطلاح \(s=0\) إذا كانت الورقة السابقة غير متتبعة، أو إذا كانت آخر رتبة متتبعة قد انتهت تمامًا.
هذا الوصف المضغوط كافٍ لأن جميع الرتب داخل الفئة نفسها متناظرة تمامًا. الرتبة الوحيدة التي يجب تمييزها مؤقتًا هي آخر رتبة متتبعة ظهرت، لأن ظهورها مباشرة مرة ثانية سيصنع زوجًا متجاورًا من الرتبة نفسها، فيفسد شرط المثالية لتلك الرتبة.
الحالة الابتدائية لمجموعة حجمها \(j\) هي
$$\Psi_j(52-4j,0,0,0,j,0),$$
حيث تمثل \(\Psi_j\) احتمال الوصول إلى نهاية الرزمة مع بقاء كل الرتب المتتبعة مثالية.
من الحالة \((u,a_1,a_2,a_3,a_4,s)\)، يكون عدد الأوراق غير المكشوفة هو
$$R=u+a_1+2a_2+3a_3+4a_4.$$
إذا كان \(R=0\)، فهذا يعني أن كشف الرزمة اكتمل من دون أي تجاور ممنوع داخل المجموعة المتتبعة، وبالتالي
$$\Psi_j(0,0,0,0,0,0)=1.$$
احتمال أن تكون الورقة التالية من رتبة غير متتبعة هو \(u/R\). عندها ينقص \(u\) بمقدار \(1\)، وتزول القيود النشطة لأن هذه الورقة تفصل بين ما سيأتي لاحقًا وبين آخر رتبة متتبعة ظهرت.
أما إذا كانت هناك رتبة متتبعة ضمن الفئة \(r\)، فإن كل رتبة من هذه الفئة تساهم بـ \(r\) أوراق ممكنة للخطوة التالية. لكن عندما يكون \(s=r\)، فإن رتبة واحدة من هذه الفئة هي الرتبة الممنوعة مؤقتًا لأنها ظهرت للتو ولا يجوز تكرارها فورًا. إذن عدد الرتب المسموح بها في الفئة \(r\) هو
$$a_r-\mathbf{1}_{\{s=r\}}.$$
وعليه يكون احتمال سحب ورقة متتبعة من الفئة \(r\) مساويًا لـ
$$\frac{r\left(a_r-\mathbf{1}_{\{s=r\}}\right)}{R}.$$
بعد هذا السحب، تنتقل رتبة واحدة من الفئة \(r\) إلى الفئة \(r-1\). وتصبح القيمة النشطة الجديدة \(r-1\)، إلا إذا كان \(r=1\)، ففي هذه الحالة تكون الرتبة قد انتهت تمامًا وتعود القيمة النشطة إلى \(0\).
إذن لكل حالة خمس انتقالات كحد أقصى: انتقال واحد لورقة غير متتبعة، وأربعة انتقالات محتملة لفئات البواقي \(r=1,2,3,4\). التذكر يجعل هذه العلاقة العملية فعالة، لأن الحالة المضغوطة نفسها قد تُزار عبر عدد كبير من تواريخ الكشف المختلفة.
بعد حساب جميع القيم \(q_j=\Psi_j(52-4j,0,0,0,j,0)\)، نبني
$$B_j=\binom{13}{j}q_j.$$
ثم نستخدم العلاقة المثلثية
$$B_j=\sum_{k=j}^{13}\binom{k}{j}D_k$$
ونعكسها بالرجوع من \(k=13\) نزولًا:
$$D_k=B_k-\sum_{t=k+1}^{13}\binom{t}{k}D_t.$$
وفي النهاية يكون الاحتمال المطلوب هو
$$\Pr\!\left(Y\in\{2,3,5,7,11,13\}\right)=D_2+D_3+D_5+D_7+D_{11}+D_{13}.$$
عندما \(j=1\)، نتابع رتبة واحدة محددة. تكون هذه الرتبة مثالية إذا وفقط إذا كانت مواضع أوراقها الأربع في الرزمة لا تحتوي على أي زوج متجاور.
إذا كانت هذه المواضع هي
$$1\le x_1<x_2<x_3<x_4\le 52,\qquad x_{i+1}\ge x_i+2,$$
فإن التحويل \(y_i=x_i-(i-1)\) يعطي
$$1\le y_1<y_2<y_3<y_4\le 49.$$
إذًا عدد اختيارات المواضع الأربع غير المتجاورة هو \(\binom{49}{4}\)، بينما العدد الكلي لاختيار أربعة مواضع هو \(\binom{52}{4}\). ومن ثم
$$q_1=\frac{\binom{49}{4}}{\binom{52}{4}}=\frac{4324}{5525}.$$
وباستخدام خطية التوقع نحصل على
$$\mathbb{E}[Y]=13q_1=\frac{4324}{425}.$$
هذه القيمة تطابق فحص الاتساق الموجود داخل التطبيقات، وتؤكد أن منظور “احتمال المجموعات الفرعية” منسجم تمامًا مع التركيب التوافقي للمسألة.
تتبع تطبيقات C++ وPython وJava التسلسل نفسه. أولًا تُحسب معاملات ثنائية \(\binom{n}{k}\) لكل \(0\le n,k\le 13\). بعد ذلك، ولكل حجم مجموعة \(j\)، يجري تقييم علاقة الاحتمال ذات التذكر انطلاقًا من الحالة الابتدائية التي تحتوي على \(j\) رتب متتبعة و\(52-4j\) ورقة غير متتبعة.
هذه الحسابات تعطي القيم \(q_1,\dots,q_{13}\)، ومنها تُبنى العزوم الثنائية \(B_j=\binom{13}{j}q_j\). بعد ذلك تُحل المنظومة المثلثية بالرجوع من الأعلى إلى الأسفل للحصول على التوزيع الكامل \(D_0,D_1,\dots,D_{13}\).
في الخطوة الأخيرة تجمع الشيفرة الاحتمالات الستة الموافقة للقيم الأولية لـ \(Y\)، ثم تطبع النتيجة بدقة عشر مراتب عشرية. كما أن إحدى التطبيقات تتحقق أيضًا من العلاقة \(\mathbb{E}[Y]=4324/425\)، وهي بالضبط نتيجة المثال السابق في صورة اختبار اتساق.
لثابت \(j\)، لنرمز بعدد الحالات المضغوطة الممكن الوصول إليها \((u,a_1,a_2,a_3,a_4,s)\) بالرمز \(S_j\). بما أن التذكر يضمن أن كل حالة تُقيَّم مرة واحدة فقط، ولكل حالة في أقصى الأحوال خمس انتقالات، فإن الزمن لهذا \(j\) يساوي \(O(S_j)\)، وكذلك الذاكرة تساوي \(O(S_j)\).
وعبر جميع أحجام المجموعات نحصل على الكلفة الكلية
$$O\!\left(\sum_{j=1}^{13} S_j\right)+O(13^2),$$
حيث يأتي الحد \(O(13^2)\) من خطوة الرجوع الأخيرة. لا توجد صيغة مغلقة بسيطة لـ \(S_j\)، لكن فضاء الحالات مقيَّد بقوة بواسطة الشرط
$$u+a_1+2a_2+3a_3+4a_4\le 52$$
وبحقيقة أن عدد الرتب الكلي في الرزمة لا يتجاوز \(13\). عمليًا، يبقى عدد الحالات الممكنة صغيرًا بما يكفي لإجراء الحساب الدقيق بسهولة.