For Problem 964, the quantity attached to \(k\) is evaluated at the special size
$$n=\frac{k(k-1)}{2}+1.$$
For the required instance \(k=7\), this gives \(n=22\). The three implementations all compute the same normalized combinatorial quantity: first they build an inclusion-exclusion total over a reduced universe of \(n-1\) relative chair positions, and only at the end do they divide by \(n!\).
The important point is that the problem is not attacked by enumerating chair arrangements directly. Instead, the mathematics tracks which relative chair positions can survive simultaneously through \(k\) successive stages. Once that common-survivor question is written correctly, the whole computation collapses to a short alternating sum with binomial coefficients.
Let \(\mathcal{U}\) be the reduced set of relative chair positions, with \(|\mathcal{U}|=n-1\). The implementations can be read as working with stage sets
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$$
where \(A_i\) records the positions still compatible with surviving stage \(i\), and where the only data that matters is the cardinality
$$|A_i|=n-i.$$
The value \(n=\frac{k(k-1)}2+1\) is the natural size parameter of the problem. In the final target case \(k=7\), the reduced universe has \(n-1=21\) positions. The code never tries to list all chair configurations. It uses only the fact that every stage \(i\) leaves a uniformly distributed subset of size \(n-i\) inside the same ambient set \(\mathcal{U}\).
This immediately creates a useful invariant: for a fixed integer \(r\), every \(r\)-element subset \(R\subseteq \mathcal{U}\) behaves identically. The contribution depends only on \(r\), never on the actual labels of the chairs inside \(R\).
Define \(Q_k\) to be the raw inclusion-exclusion total before the final factorial normalization. We want to count the configurations in which no relative chair position survives all \(k\) stages at once. For each \(x\in\mathcal{U}\), let \(E_x\) be the event that \(x\) belongs to every stage set \(A_1,\dots,A_k\). Then
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
Applying inclusion-exclusion over subsets \(R\subseteq\mathcal{U}\) gives
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
Because all subsets of the same size are equivalent, we can group terms by \(r=|R|\).
Fix an \(r\)-element subset \(R\subseteq\mathcal{U}\). For one stage \(i\), the probability that all elements of \(R\) survive that stage is the fraction of size-\((n-i)\) subsets containing \(R\):
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
The implementations multiply these stage factors across \(i=1,\dots,k\), which is exactly why the core term in the code is a product of \(k\) binomial ratios. The factor for \(i=1\) equals 1, since \(|A_1|=n-1\), but it is left inside the product so that every stage is treated uniformly.
There are \(\binom{n-1}{r}\) possible sets \(R\) of size \(r\), so the grouped inclusion-exclusion sum becomes
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
This is the exact formula evaluated in C++, Python, and Java. A useful simplification is that \(\binom{n-i}{r}=0\) whenever \(r>n-i\). In particular, once \(r>n-k\), the whole term vanishes automatically. So although the loop is written up to \(n-1\), only the first \(n-k+1\) terms can contribute.
The final Project Euler quantity is then
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
That last division by \(n!\) is not a numerical trick; it is part of the problem's definition, and the three implementations all perform it only after the alternating sum has been accumulated at high precision.
For \(k=3\), we get \(n=\frac{3\cdot2}{2}+1=4\), so \(|\mathcal{U}|=3\) and the stage sizes are \(3,2,1\). The formula becomes
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
The \(r=0\) term is \(1\). For \(r=1\), we subtract
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
All terms with \(r\ge2\) vanish, because the last stage leaves only one surviving position. Therefore
$$Q_3=1-\frac23=\frac13,$$
and after the factorial normalization,
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
This matches the validation constant used by the implementations, so the inclusion-exclusion derivation is exactly the one the code is evaluating.
The C++, Python, and Java implementations all follow the same structure. They first set a high-precision decimal environment, compute \(n=\frac{k(k-1)}2+1\), and then sweep through the alternating sum over \(r=0,1,\dots,n-1\). For each \(r\), they evaluate the exact binomial coefficient \(\binom{n-1}{r}\), then multiply the \(k\) stage ratios \(\binom{n-i}{r}/\binom{n-1}{r}\).
After the product is formed, the implementation restores the outer factor \(\binom{n-1}{r}\), applies the sign \((-1)^r\), and adds the result to the running total. Nothing symbolic is cached, because for the target case \(k=7\) the numbers are tiny enough that direct exact binomial evaluation is already sufficient.
Once the alternating sum \(Q_k\) is complete, the code divides by \(n!\) using the same high-precision arithmetic. Finally, it checks the known values for \(k=2\), \(k=3\), and \(k=4\), and prints the answer for \(k=7\) in scientific notation.
If binomial coefficients are regarded as available in \(O(1)\) time, the mathematical core is just the outer \(r\)-sum with \(k\) multiplicative factors per term, so the complexity is \(O(nk)\). Since \(n=\Theta(k^2)\), that is \(O(k^3)\) for the closed-form summation itself.
The literal C++ and Java implementations recompute each binomial coefficient by a short multiplicative loop, so their raw arithmetic count is closer to \(O(kn^2)\). For the actual target \(k=7\), however, \(n=22\), so both viewpoints are tiny in practice. Memory usage is \(O(1)\) apart from the high-precision numeric objects used for the accumulation and the final factorial.
Fuer Problem 964 wird die zu \(k\) gehoerende Groesse bei
$$n=\frac{k(k-1)}{2}+1$$
ausgewertet. Fuer den gesuchten Fall \(k=7\) ist also \(n=22\). Alle drei Implementierungen berechnen dieselbe normalisierte kombinatorische Groesse: Zuerst wird eine Inklusions-Exklusions-Summe ueber einen reduzierten Raum von \(n-1\) relativen Stuhlpositionen aufgebaut, erst danach erfolgt die Division durch \(n!\).
Der entscheidende Gedanke ist, nicht alle moeglichen Stuhlkonfigurationen direkt zu erzeugen. Stattdessen verfolgt die Mathematik nur, welche relativen Positionen gleichzeitig alle \(k\) Stufen ueberleben koennen. Genau diese gemeinsame-Ueberlebensfrage fuehrt auf eine kurze alternierende Summe mit Binomialkoeffizienten.
Sei \(\mathcal{U}\) die reduzierte Menge relativer Stuhlpositionen mit \(|\mathcal{U}|=n-1\). Die Implementierungen lassen sich so lesen, dass zu jeder Stufe
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k)$$
diejenigen Positionen gehoeren, die nach Stufe \(i\) noch kompatibel sind. Relevant ist nur die Groesse dieser Mengen:
$$|A_i|=n-i.$$
Die Groesse \(n=\frac{k(k-1)}2+1\) ist der natuerliche Problemparameter. Im Ziel fall \(k=7\) hat der reduzierte Raum also \(n-1=21\) Positionen. Der Code listet keine Stuhlordnungen aus; er benutzt nur, dass jede Stufe \(i\) eine gleichverteilte Teilmenge der Groesse \(n-i\) innerhalb desselben Grundraums \(\mathcal{U}\) hinterlaesst.
Daraus folgt sofort eine wichtige Invariante: Fuer festes \(r\) verhalten sich alle \(r\)-elementigen Teilmengen \(R\subseteq\mathcal{U}\) identisch. Der Beitrag haengt nur von \(r\) ab, nicht von den konkreten Stuhlnummern in \(R\).
Bezeichne mit \(Q_k\) die rohe Inklusions-Exklusions-Groesse vor der abschliessenden Faktorial-Normierung. Gesucht werden genau die Konfigurationen, in denen keine relative Stuhlposition alle \(k\) Stufen gleichzeitig ueberlebt. Fuer jedes \(x\in\mathcal{U}\) sei \(E_x\) das Ereignis, dass \(x\) in allen Mengen \(A_1,\dots,A_k\) liegt. Dann gilt
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
Mit Inklusions-Exklusion ueber Teilmengen \(R\subseteq\mathcal{U}\) erhaelt man
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
Wegen der Symmetrie werden anschliessend alle Terme gleicher Groesse \(r=|R|\) zusammengefasst.
Fixiere eine \(r\)-elementige Menge \(R\subseteq\mathcal{U}\). Fuer eine einzelne Stufe \(i\) ist die Wahrscheinlichkeit, dass alle Elemente von \(R\) in \(A_i\) enthalten sind, genau der Anteil der Teilmengen der Groesse \(n-i\), die \(R\) enthalten:
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Die Implementierungen multiplizieren diese Stufenfaktoren ueber \(i=1,\dots,k\). Genau deshalb besteht der Kernterm im Code aus einem Produkt von \(k\) Binomialverhaeltnissen. Der Faktor fuer \(i=1\) ist gleich 1, weil \(|A_1|=n-1\), wird aber der Einheitlichkeit halber im Produkt belassen.
Es gibt \(\binom{n-1}{r}\) moegliche Mengen \(R\) der Groesse \(r\). Daher wird die gruppierte Inklusions-Exklusions-Summe zu
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Das ist exakt die Formel, die in C++, Python und Java ausgewertet wird. Praktisch wichtig ist ausserdem: \(\binom{n-i}{r}=0\), sobald \(r>n-i\). Insbesondere verschwindet jeder Summand mit \(r>n-k\) automatisch. Obwohl also bis \(n-1\) iteriert wird, tragen nur die ersten \(n-k+1\) Werte wirklich bei.
Die gesuchte Euler-Groesse ist dann
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
Diese Division durch \(n!\) ist kein numerischer Kunstgriff, sondern Teil der Problemdefinition. Alle drei Implementierungen fuehren sie erst nach der hochpraezisen Summation aus.
Fuer \(k=3\) gilt \(n=\frac{3\cdot2}{2}+1=4\), also \(|\mathcal{U}|=3\) und die Stufengroessen sind \(3,2,1\). Die Formel lautet dann
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
Der Term fuer \(r=0\) ist \(1\). Fuer \(r=1\) wird abgezogen
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
Alle Terme mit \(r\ge2\) verschwinden, weil die letzte Stufe nur eine einzige ueberlebende Position besitzt. Also folgt
$$Q_3=1-\frac23=\frac13,$$
und nach der Faktorial-Normierung
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
Genau dieser Wert wird in den Implementierungen zur Validierung verwendet. Damit ist klar, dass die Herleitung mit der Rechnung des Codes vollstaendig uebereinstimmt.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Ablauf. Zunaechst wird eine hochpraezise Dezimalarithmetik eingerichtet, dann \(n=\frac{k(k-1)}2+1\) berechnet und schliesslich die alternierende Summe ueber \(r=0,1,\dots,n-1\) durchlaufen. Fuer jedes \(r\) werden der exakte Binomialkoeffizient \(\binom{n-1}{r}\) und anschliessend die \(k\) Stufenfaktoren \(\binom{n-i}{r}/\binom{n-1}{r}\) gebildet.
Danach setzt die Implementierung den aeusseren Faktor \(\binom{n-1}{r}\) wieder davor, versieht den Summanden mit dem Vorzeichen \((-1)^r\) und addiert ihn zum laufenden Total. Es wird nichts symbolisch zwischengespeichert, weil fuer den Zielwert \(k=7\) die Zahlen so klein sind, dass eine direkte exakte Auswertung der Binomialkoeffizienten voellig ausreicht.
Wenn die Summe \(Q_k\) vollstaendig ist, wird durch \(n!\) dividiert. Anschliessend prueft der Code die bekannten Werte fuer \(k=2\), \(k=3\) und \(k=4\) und gibt das Ergebnis fuer \(k=7\) in wissenschaftlicher Schreibweise aus.
Wenn man Binomialkoeffizienten als in \(O(1)\) verfuegbar betrachtet, besteht der mathematische Kern nur aus der aeusseren \(r\)-Summe mit \(k\) Faktoren pro Summand. Das ergibt \(O(nk)\). Da \(n=\Theta(k^2)\) gilt, ist die geschlossene Summe damit \(O(k^3)\).
Die konkrete C++- und Java-Implementierung berechnet jeden Binomialkoeffizienten jedoch per kurzer multiplikativer Schleife neu, sodass die rohe Anzahl arithmetischer Schritte eher bei \(O(kn^2)\) liegt. Fuer den tatsaechlichen Zielwert \(k=7\) mit \(n=22\) ist beides praktisch winzig. Der Speicherverbrauch ist \(O(1)\), abgesehen von den hochpraezisen Zahlobjekten fuer Summe und Fakultaet.
Problem 964 icin \(k\)'ya bagli nicelik
$$n=\frac{k(k-1)}{2}+1$$
boyutunda degerlendiriliyor. Istenen durumda \(k=7\) oldugu icin \(n=22\) elde edilir. Uc uygulamanin da yaptigi sey aynidir: once \(n-1\) adet goreli sandalye konumu uzerinde bir dahil etme-dislama toplami kurulur, sonra en sonda sonuc \(n!\)'e bolunur.
Asil fikir, sandalye duzenlerini tek tek saymak degildir. Bunun yerine matematik, hangi goreli sandalye konumlarinin \(k\) asamanin hepsinde birden ayakta kalabildigini izler. Bu ortak hayatta kalma sorusu dogru bicimde yazildiginda problem, binom katsayili kisa bir alternansli toplama indirgenir.
\(\mathcal{U}\) ile indirgenmis goreli sandalye konumlari kumesini gosterelim; \(|\mathcal{U}|=n-1\) olsun. Uygulamalar,
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k)$$
kumesini \(i\). asamadan sonra hala mumkun olan konumlar olarak ele alir. Burada onemli olan tek bilgi su buyukluktur:
$$|A_i|=n-i.$$
\(n=\frac{k(k-1)}2+1\) degeri problemin dogal boyut parametresidir. Hedef durum \(k=7\) icin indirgenmis uzayda \(n-1=21\) konum vardir. Kod hicbir zaman tum sandalye dizilimlerini acikca uretmez; yalnizca her \(i\) asamasinin ayni temel kume \(\mathcal{U}\) icinde boyutu \(n-i\) olan esit olasilikli bir altkume biraktigi gercegini kullanir.
Buradan gercek bir degismezlik dogar: sabit bir \(r\) icin \(\mathcal{U}\) icindeki tum \(r\) elemanli altkumeler ayni davranir. Katki, secilen sandalyelerin etiketlerine degil, yalnizca \(r\)'ye baglidir.
\(Q_k\) ile son faktoriyel normallestirmeden onceki ham dahil etme-dislama toplamini gosterelim. Aradigimiz sey, hicbir goreli sandalye konumunun tum \(k\) asamada birden hayatta kalmadigi durumdur. Her \(x\in\mathcal{U}\) icin \(E_x\), \(x\)'in \(A_1,\dots,A_k\) kumelerinin hepsinde yer almasi olayi olsun. O zaman
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
Dahil etme-dislama prensibiyle
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k)$$
elde edilir. Ayni buyuklukteki altkumeler esit davrandigi icin toplam daha sonra \(r=|R|\) degerine gore gruplanir.
\(|R|=r\) olan sabit bir \(R\subseteq\mathcal{U}\) altkumesi secelim. Tek bir \(i\) asamasinda \(R\)'nin tamaminin hayatta kalma olasiligi, \(R\)'yi iceren boyutu \(n-i\) olan altkumelerin oranidir:
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Uygulamalar tam olarak bu asama carpanlarini \(i=1,\dots,k\) boyunca carpiyor. Kodun merkezindeki ifade bu yuzden \(k\) tane binom oraninin carpimidir. \(i=1\) icin gelen carpan 1'dir; cunku \(|A_1|=n-1\). Yine de her asamayi ayni bicimde yazmak icin urunun icinde tutulur.
Boyutu \(r\) olan \(\binom{n-1}{r}\) adet farkli \(R\) altkumesi vardir. Dolayisiyla gruplanmis dahil etme-dislama toplami
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}$$
olur. C++, Python ve Java tam olarak bu formulu degerlendirir. Burada onemli bir sadeleme daha vardir: \(r>n-i\) oldugunda \(\binom{n-i}{r}=0\) olur. Ozellikle \(r>n-k\) ise ilgili toplam terimi otomatik olarak sifirdir. Yani dongu \(n-1\)'e kadar yazilsa da gercekte katkilar yalnizca ilk \(n-k+1\) terimden gelir.
Son Project Euler niceligi ise
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
Buradaki \(n!\) bolmesi sayisal bir hile degil, problemin taniminin parcasidir. Uc uygulamanin ucunde de bu bolme, alternansli toplam yuksek hassasiyetle tamamlandiktan sonra yapilir.
\(k=3\) icin \(n=\frac{3\cdot2}{2}+1=4\) olur. Demek ki \(|\mathcal{U}|=3\) ve asama buyuklukleri \(3,2,1\)'dir. Formul
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}$$
haline gelir. \(r=0\) terimi \(1\)'dir. \(r=1\) icin cikarilan miktar
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23$$
olur. \(r\ge2\) olan tum terimler sifirlanir; cunku son asamada yalnizca bir konum kalir. Bu nedenle
$$Q_3=1-\frac23=\frac13,$$
ve faktoriyel normallestirmeden sonra
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
Bu, uygulamalardaki dogrulama sabitiyle ayni degerdir. Yani dahil etme-dislama turetimi kodun hesapladigi nicelikle bire bir uyumludur.
C++, Python ve Java uygulamalari ayni is akisini izler. Once yuksek hassasiyetli ondalik ortam kurulur, sonra \(n=\frac{k(k-1)}2+1\) hesaplanir ve ardindan \(r=0,1,\dots,n-1\) icin alternansli toplam dolasilir. Her \(r\) adiminda \(\binom{n-1}{r}\) tam olarak hesaplanir, sonra da \(k\) adet asama orani \(\binom{n-i}{r}/\binom{n-1}{r}\) carpilir.
Carpim hazir olduktan sonra distaki \(\binom{n-1}{r}\) katsayisi geri eklenir, \((-1)^r\) isareti uygulanir ve terim biriken toplama katilir. Hicbir sembolik onbellekleme yapilmaz; cunku hedef durum \(k=7\) icin sayilar yeterince kucuktur ve binom katsayilarini dogrudan tam olarak hesaplamak zaten yeterlidir.
Alternansli toplam \(Q_k\) tamamlandiginda kod sonucu \(n!\)'e boler. Son adimda \(k=2\), \(k=3\) ve \(k=4\) icin bilinen degerler kontrol edilir ve \(k=7\) cevabi bilimsel gosterimle yazdirilir.
Binom katsayilarinin \(O(1)\) zamanda hazir oldugu varsayilirsa matematiksel cekirdek, her terimde \(k\) carpan bulunan bir \(r\)-toplamidir ve karmasiklik \(O(nk)\) olur. \(n=\Theta(k^2)\) oldugu icin kapali formun kendisi \(O(k^3)\) seklinde okunabilir.
Gercek C++ ve Java uygulamalari ise her binom katsayisini kisa bir carpimli donguyle yeniden hesaplar; bu da ham is sayisini daha cok \(O(kn^2)\) duzeyine getirir. Fakat hedef durumda \(k=7\) ve \(n=22\) oldugundan bu fark pratikte onemsizdir. Bellek kullanimi, yuksek hassasiyetli sayi nesneleri disinda \(O(1)\)'dir.
En el Problema 964, la cantidad asociada a \(k\) se evalua en el tamano especial
$$n=\frac{k(k-1)}{2}+1.$$
Para el caso pedido, \(k=7\), se obtiene \(n=22\). Las tres implementaciones calculan la misma cantidad combinatoria normalizada: primero construyen una suma de inclusion-exclusion sobre un universo reducido de \(n-1\) posiciones relativas de sillas, y solo al final dividen por \(n!\).
La idea importante es que no se enumeran directamente todas las configuraciones de sillas. En cambio, la derivacion sigue que posiciones relativas pueden sobrevivir simultaneamente a lo largo de las \(k\) etapas. Una vez formulada correctamente esa pregunta de supervivencia comun, todo el problema se reduce a una suma alternante corta con coeficientes binomiales.
Sea \(\mathcal{U}\) el conjunto reducido de posiciones relativas, con \(|\mathcal{U}|=n-1\). Las implementaciones pueden interpretarse mediante conjuntos de etapa
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$$
donde \(A_i\) contiene las posiciones que siguen siendo compatibles despues de la etapa \(i\). El unico dato esencial es su cardinal:
$$|A_i|=n-i.$$
El valor \(n=\frac{k(k-1)}2+1\) es el parametro natural del problema. En el objetivo \(k=7\), el universo reducido tiene \(n-1=21\) posiciones. El codigo nunca intenta listar todas las disposiciones posibles; usa solo el hecho de que cada etapa \(i\) deja un subconjunto uniformemente distribuido de tamano \(n-i\) dentro del mismo conjunto base \(\mathcal{U}\).
De aqui aparece un invariante util: para un entero fijo \(r\), cualquier subconjunto \(R\subseteq\mathcal{U}\) con \(r\) elementos se comporta igual que cualquier otro. La contribucion depende solamente de \(r\), no de las etiquetas concretas de las sillas elegidas.
Denotemos por \(Q_k\) la cantidad bruta antes de la normalizacion final por factorial. Queremos las configuraciones en las que ninguna posicion relativa sobrevive a las \(k\) etapas a la vez. Para cada \(x\in\mathcal{U}\), sea \(E_x\) el evento de que \(x\) pertenezca a todos los conjuntos \(A_1,\dots,A_k\). Entonces
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
Aplicando inclusion-exclusion sobre subconjuntos \(R\subseteq\mathcal{U}\), obtenemos
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
Como todos los subconjuntos del mismo tamano son equivalentes, la suma se agrupa por \(r=|R|\).
Fijemos un subconjunto \(R\subseteq\mathcal{U}\) con \(|R|=r\). En una etapa \(i\), la probabilidad de que todos sus elementos sobrevivan es la fraccion de subconjuntos de tamano \(n-i\) que contienen a \(R\):
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Las implementaciones multiplican exactamente estos factores de etapa para \(i=1,\dots,k\). Por eso el termino central del codigo es un producto de \(k\) cocientes binomiales. El factor con \(i=1\) vale 1, porque \(|A_1|=n-1\), pero se deja dentro del producto para mantener una formula uniforme.
Existen \(\binom{n-1}{r}\) subconjuntos \(R\) de tamano \(r\), asi que la suma agrupada queda
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Esta es exactamente la expresion que calculan las versiones en C++, Python y Java. Ademas, \(\binom{n-i}{r}=0\) cuando \(r>n-i\). En particular, si \(r>n-k\), el termino completo desaparece. Por eso, aunque el bucle llega hasta \(n-1\), solo pueden contribuir los primeros \(n-k+1\) valores.
La cantidad final pedida por el problema es
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
Esa division por \(n!\) no es un detalle numerico accidental; forma parte de la definicion final, y las tres implementaciones la aplican solo despues de acumular la suma alternante con alta precision.
Si \(k=3\), entonces \(n=\frac{3\cdot2}{2}+1=4\), de modo que \(|\mathcal{U}|=3\) y los tamanos de etapa son \(3,2,1\). La formula se convierte en
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
El termino \(r=0\) vale \(1\). Para \(r=1\), se resta
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
Todos los terminos con \(r\ge2\) se anulan, porque la ultima etapa deja solo una posicion superviviente. Por tanto,
$$Q_3=1-\frac23=\frac13,$$
y despues de normalizar,
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
Ese valor coincide con la comprobacion incorporada en las implementaciones, asi que la derivacion matematica es exactamente la que el codigo usa.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero configuran aritmetica decimal de alta precision, calculan \(n=\frac{k(k-1)}2+1\) y recorren la suma alternante para \(r=0,1,\dots,n-1\). En cada \(r\), calculan exactamente \(\binom{n-1}{r}\) y luego multiplican los \(k\) cocientes de etapa \(\binom{n-i}{r}/\binom{n-1}{r}\).
Una vez formado el producto, la implementacion restaura el factor exterior \(\binom{n-1}{r}\), aplica el signo \((-1)^r\) y lo agrega al acumulado. No se necesita ninguna simplificacion simbolica ni tablas grandes, porque para el objetivo \(k=7\) los enteros involucrados son muy pequenos y las combinaciones se pueden evaluar directamente.
Al terminar la suma \(Q_k\), el resultado se divide por \(n!\) con la misma precision alta. Por ultimo, el codigo valida los casos \(k=2\), \(k=3\) y \(k=4\), y muestra la respuesta para \(k=7\) en notacion cientifica.
Si se supone que los coeficientes binomiales ya estan disponibles en tiempo \(O(1)\), el nucleo matematico es solo la suma exterior en \(r\) con \(k\) factores por termino, es decir \(O(nk)\). Como \(n=\Theta(k^2)\), la forma cerrada equivale a \(O(k^3)\).
Las implementaciones literales en C++ y Java recalculan cada coeficiente binomial mediante un pequeno producto, de modo que su costo aritmetico bruto se acerca mas a \(O(kn^2)\). Para el caso real \(k=7\) con \(n=22\), ambas estimaciones son minusculas en la practica. El uso de memoria es \(O(1)\), aparte de los objetos numericos de alta precision necesarios para la suma y el factorial final.
在第 964 题中，与 \(k\) 对应的量是在特殊规模
$$n=\frac{k(k-1)}{2}+1$$
下计算的。目标实例是 \(k=7\)，因此 \(n=22\)。三份实现做的是同一件事：先在一个大小为 \(n-1\) 的“相对椅子位置”空间上建立容斥和，最后再除以 \(n!\) 完成题目要求的归一化。
真正关键的地方，不是去枚举所有可能的座位安排，而是追踪哪些相对位置能够同时穿过全部 \(k\) 个阶段。只要把“共同存活的位置”这个问题写对，整个题目就会坍缩为一个很短的、带二项式系数的交错求和。
记 \(\mathcal{U}\) 为约化后的相对椅子位置集合，满足 \(|\mathcal{U}|=n-1\)。可以把实现理解为在处理一组阶段集合
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$$
其中 \(A_i\) 表示第 \(i\) 个阶段结束后仍然“可存活”的位置。这里真正重要的只有它们的大小：
$$|A_i|=n-i.$$
\(n=\frac{k(k-1)}2+1\) 是这道题的自然规模参数。对于目标值 \(k=7\)，约化后的宇宙大小就是 \(n-1=21\)。代码从头到尾都没有显式枚举所有椅子配置，它只利用这样一个事实：每一个阶段 \(i\) 都在同一个底层集合 \(\mathcal{U}\) 中留下一个大小为 \(n-i\) 的等可能子集。
这立刻给出一个很重要的不变量：固定 \(r\) 之后，\(\mathcal{U}\) 中任意两个 \(r\) 元子集的行为完全相同。也就是说，贡献只取决于 \(r\)，而不取决于这些椅子位置的具体编号。
用 \(Q_k\) 表示除以 \(n!\) 之前的原始容斥总量。我们需要的是“没有任何一个相对位置能在全部 \(k\) 个阶段中同时存活”的情况。对每个 \(x\in\mathcal{U}\)，令 \(E_x\) 表示“位置 \(x\) 属于 \(A_1,\dots,A_k\) 的交集”这个事件。那么
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
对所有子集 \(R\subseteq\mathcal{U}\) 使用容斥原理，可以写成
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
由于同样大小的子集完全等价，接下来就只需要按 \(r=|R|\) 分组。
固定一个 \(r\) 元子集 \(R\subseteq\mathcal{U}\)。在单个阶段 \(i\) 中，\(R\) 的所有元素都幸存的概率，就是“大小为 \(n-i\) 的子集里包含 \(R\) 的比例”：
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
三份实现正是把这些阶段因子对 \(i=1,\dots,k\) 连乘起来，所以代码的核心自然是 \(k\) 个二项式比值的乘积。这里 \(i=1\) 时的因子等于 1，因为 \(|A_1|=n-1\)，但把它保留在乘积中，公式会更整齐。
大小为 \(r\) 的子集 \(R\) 一共有 \(\binom{n-1}{r}\) 个，因此按大小分组后的容斥和就是
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
这正是 C++、Python 和 Java 版本逐项计算的表达式。还有一个非常实用的观察：当 \(r>n-i\) 时，\(\binom{n-i}{r}=0\)。特别地，只要 \(r>n-k\)，整个项就自动为零。因此虽然循环写到了 \(n-1\)，真正可能有贡献的只有前 \(n-k+1\) 项。
题目最终要求的量是
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
这里除以 \(n!\) 不是为了数值稳定，而是题目定义本身的一部分。三份实现都是先高精度累计完整个交错和，再做这一步归一化。
当 \(k=3\) 时，\(n=\frac{3\cdot2}{2}+1=4\)，所以 \(|\mathcal{U}|=3\)，三个阶段的大小分别是 \(3,2,1\)。公式化为
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
\(r=0\) 项等于 \(1\)。对于 \(r=1\)，要减去
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
所有 \(r\ge2\) 的项都为零，因为最后一个阶段只剩下一个位置还能存活。因此
$$Q_3=1-\frac23=\frac13,$$
再除以 \(4!\) 得到
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
这和实现中用来校验的小规模常数完全一致，所以可以确认，代码计算的正是这套容斥推导。
C++、Python 和 Java 三个实现的流程完全一致。它们先设置高精度十进制环境，计算 \(n=\frac{k(k-1)}2+1\)，然后遍历 \(r=0,1,\dots,n-1\) 的交错求和。对每个 \(r\)，先精确求出 \(\binom{n-1}{r}\)，再把 \(k\) 个阶段比值 \(\binom{n-i}{r}/\binom{n-1}{r}\) 相乘。
乘积算出后，程序再乘回外层的 \(\binom{n-1}{r}\)，按 \((-1)^r\) 加上符号，并累加到总和中。由于目标只有 \(k=7\)、\(n=22\)，相关整数都很小，所以实现没有做复杂的符号化预处理，也不需要庞大的预计算表。
当交错和 \(Q_k\) 完成以后，程序用同样的高精度算术除以 \(n!\)。最后，它会检查 \(k=2\)、\(k=3\)、\(k=4\) 的已知值，并以科学计数法输出 \(k=7\) 的答案。
如果把二项式系数视为 \(O(1)\) 可得，那么数学核心只是一个外层 \(r\) 求和，每项有 \(k\) 个乘法因子，所以复杂度是 \(O(nk)\)。由于 \(n=\Theta(k^2)\)，闭式求和本身也可以写成 \(O(k^3)\)。
但从字面实现来看，C++ 和 Java 会用短乘法循环重新计算每个二项式系数，因此原始算术工作量更接近 \(O(kn^2)\)。对实际目标 \(k=7\)、\(n=22\) 来说，这两种估计都非常小。除高精度数值对象外，额外内存基本是 \(O(1)\)。
В задаче 964 величина, связанная с \(k\), рассматривается при специальном размере
$$n=\frac{k(k-1)}{2}+1.$$
Для целевого случая \(k=7\) получаем \(n=22\). Все три реализации вычисляют одну и ту же нормированную комбинаторную величину: сначала строится сумма включения-исключения на уменьшенном множестве из \(n-1\) относительных положений стульев, и только потом результат делится на \(n!\).
Ключевая идея состоит не в прямом переборе всех рассадок. Вместо этого математика отслеживает, какие относительные позиции могут пережить все \(k\) этапов одновременно. Как только этот вопрос о совместном выживании записан правильно, вся задача сводится к короткой знакопеременной сумме с биномиальными коэффициентами.
Обозначим через \(\mathcal{U}\) сокращенное множество относительных позиций, где \(|\mathcal{U}|=n-1\). Реализации удобно понимать через семейство множеств
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$$
где \(A_i\) состоит из позиций, которые еще совместимы с выживанием после этапа \(i\). Важен только их размер:
$$|A_i|=n-i.$$
Число \(n=\frac{k(k-1)}2+1\) является естественным параметром задачи. В целевом случае \(k=7\) сокращенное пространство содержит \(n-1=21\) позицию. Код нигде не перечисляет все возможные конфигурации стульев; он использует только тот факт, что на каждом этапе \(i\) остается равновероятное подмножество размера \(n-i\) внутри одного и того же базового множества \(\mathcal{U}\).
Отсюда сразу возникает полезный инвариант: если фиксировать \(r\), то любые два \(r\)-элементных подмножества \(R\subseteq\mathcal{U}\) ведут себя одинаково. Вклад зависит только от \(r\), а не от конкретных номеров стульев.
Обозначим через \(Q_k\) сырую сумму включения-исключения до финальной нормировки на факториал. Нас интересуют конфигурации, в которых ни одна относительная позиция не переживает все \(k\) этапов сразу. Для каждого \(x\in\mathcal{U}\) обозначим через \(E_x\) событие, что \(x\) принадлежит всем множествам \(A_1,\dots,A_k\). Тогда
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
По принципу включения-исключения по всем \(R\subseteq\mathcal{U}\) получаем
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
Поскольку все подмножества одного размера эквивалентны, сумму удобно сгруппировать по \(r=|R|\).
Зафиксируем \(R\subseteq\mathcal{U}\) размера \(r\). На одном этапе \(i\) вероятность того, что все элементы \(R\) выживут, равна доле подмножеств размера \(n-i\), содержащих \(R\):
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Именно эти множители реализации перемножают по всем \(i=1,\dots,k\). Поэтому центральный терм в коде представляет собой произведение \(k\) биномиальных отношений. Множитель при \(i=1\) равен 1, поскольку \(|A_1|=n-1\), но он сохраняется в формуле ради единообразия.
Подмножеств \(R\) размера \(r\) существует \(\binom{n-1}{r}\), поэтому сгруппированная сумма принимает вид
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
Именно это выражение буквально вычисляют версии на C++, Python и Java. Есть и важное упрощение: если \(r>n-i\), то \(\binom{n-i}{r}=0\). В частности, все слагаемые с \(r>n-k\) автоматически равны нулю. Поэтому хотя цикл формально идет до \(n-1\), ненулевыми могут быть только первые \(n-k+1\) членов.
Итоговая величина задачи равна
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
Деление на \(n!\) здесь не служит численной стабилизацией; оно входит в само определение искомой величины. Все три реализации выполняют это деление только после накопления всей знакопеременной суммы с высокой точностью.
При \(k=3\) имеем \(n=\frac{3\cdot2}{2}+1=4\), значит \(|\mathcal{U}|=3\), а размеры этапов равны \(3,2,1\). Формула превращается в
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
Член при \(r=0\) равен \(1\). При \(r=1\) вычитается
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
Все члены с \(r\ge2\) обнуляются, потому что на последнем этапе остается только одна выжившая позиция. Следовательно,
$$Q_3=1-\frac23=\frac13,$$
а после нормировки получаем
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
Это в точности совпадает с проверочным значением в реализациях, так что математический вывод полностью соответствует тому, что действительно вычисляет код.
Все три реализации устроены одинаково. Сначала настраивается высокоточная десятичная арифметика, затем вычисляется \(n=\frac{k(k-1)}2+1\), после чего программа проходит по знакопеременной сумме для \(r=0,1,\dots,n-1\). Для каждого \(r\) она точно вычисляет \(\binom{n-1}{r}\), а затем перемножает \(k\) этапных отношений \(\binom{n-i}{r}/\binom{n-1}{r}\).
После этого внешний множитель \(\binom{n-1}{r}\) возвращается на место, применяется знак \((-1)^r\), и слагаемое добавляется к накопленной сумме. Никаких тяжелых предварительных таблиц не требуется, потому что для целевого случая \(k=7\) все используемые целые числа очень малы.
Когда сумма \(Q_k\) накоплена, результат делится на \(n!\) в той же высокой точности. Затем код проверяет известные значения для \(k=2\), \(k=3\) и \(k=4\), и печатает ответ для \(k=7\) в научной записи.
Если считать биномиальные коэффициенты доступными за \(O(1)\), то математическое ядро представляет собой внешний цикл по \(r\) и \(k\) множителей в каждом члене, то есть \(O(nk)\). Поскольку \(n=\Theta(k^2)\), сама закрытая формула имеет порядок \(O(k^3)\).
Однако буквальные реализации на C++ и Java каждый биномиальный коэффициент заново считают коротким мультипликативным циклом, так что их сырой арифметический счет ближе к \(O(kn^2)\). Для фактической цели \(k=7\) и \(n=22\) обе оценки очень малы на практике. Память составляет \(O(1)\), если не считать объектов высокой точности, в которых хранятся сумма и факториал.
في المسألة 964، تُقاس الكمية المرتبطة بـ \(k\) عند الحجم الخاص
$$n=\frac{k(k-1)}{2}+1.$$
وفي الحالة المطلوبة \(k=7\) نحصل على \(n=22\). التنفيذات الثلاثة تحسب المقدار التوافقي نفسه بعد تطبيع نهائي: فهي تبني اولًا مجموع شمول واستبعاد فوق فضاء مختزل حجمه \(n-1\) من المواضع النسبية للكراسي، ثم تقسم الناتج في النهاية على \(n!\).
الفكرة الحاسمة ليست تعداد جميع ترتيبات الجلوس مباشرة، بل تتبع المواضع النسبية التي يمكنها البقاء عبر المراحل \(k\) كلها في الوقت نفسه. وعندما تُصاغ مسألة "البقاء المشترك" بهذه الصورة، ينهار الحساب كله إلى مجموع متناوب قصير ذي معاملات ثنائية.
لنرمز بـ \(\mathcal{U}\) إلى مجموعة المواضع النسبية المختزلة، حيث \(|\mathcal{U}|=n-1\). ويمكن قراءة التنفيذات على أنها تتعامل مع مجموعات مراحل من الشكل
$$A_i\subseteq \mathcal{U}\qquad (1\le i\le k),$$
بحيث تمثل \(A_i\) المواضع التي تبقى متوافقة مع النجاة بعد المرحلة \(i\). والمعلومة الجوهرية هنا هي الحجم فقط:
$$|A_i|=n-i.$$
القيمة \(n=\frac{k(k-1)}2+1\) هي وسيط الحجم الطبيعي في هذه المسألة. وعند الهدف \(k=7\) يكون حجم الفضاء المختزل \(n-1=21\). الشفرة لا تحاول ابدًا سرد جميع ترتيبات الكراسي، بل تكتفي بحقيقة أن كل مرحلة \(i\) تترك داخل المجموعة نفسها \(\mathcal{U}\) مجموعة فرعية متساوية الاحتمال حجمها \(n-i\).
ومن هنا يظهر ثابت مهم: إذا ثبتنا عددًا \(r\)، فإن كل مجموعة فرعية \(R\subseteq\mathcal{U}\) ذات \(r\) عناصر تتصرف بالطريقة نفسها. أي إن المساهمة تعتمد على \(r\) فقط، لا على هوية الكراسي المختارة.
لنكتب \(Q_k\) للمقدار الخام قبل القسمة النهائية على العامل \(n!\). نحن نريد الحالات التي لا ينجو فيها أي موضع نسبي عبر المراحل \(k\) كلها دفعة واحدة. ولكل \(x\in\mathcal{U}\)، ليكن \(E_x\) هو الحدث القائل إن \(x\) ينتمي إلى جميع المجموعات \(A_1,\dots,A_k\). عندئذ
$$Q_k=\Pr\!\left(\bigcap_{x\in\mathcal{U}} E_x^{\,c}\right).$$
وباستخدام مبدأ الشمول والاستبعاد على جميع المجموعات الفرعية \(R\subseteq\mathcal{U}\) نحصل على
$$Q_k=\sum_{R\subseteq\mathcal{U}}(-1)^{|R|}\Pr(R\subseteq A_1,\dots,R\subseteq A_k).$$
ولأن جميع المجموعات الفرعية ذات الحجم نفسه متكافئة، يمكن جمع الحدود بحسب \(r=|R|\).
ثبت مجموعة \(R\subseteq\mathcal{U}\) بحيث \(|R|=r\). في مرحلة واحدة \(i\)، يكون احتمال بقاء جميع عناصر \(R\) هو نسبة المجموعات الفرعية ذات الحجم \(n-i\) التي تحتوي \(R\):
$$\Pr(R\subseteq A_i)=\frac{\binom{n-1-r}{n-i-r}}{\binom{n-1}{n-i}}=\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
والتنفيذات تضرب هذه العوامل عبر جميع المراحل \(i=1,\dots,k\). ولهذا السبب بالتحديد فإن الحد المركزي في الشفرة هو حاصل ضرب \(k\) نسب ثنائية. أما العامل الموافق لـ \(i=1\) فهو يساوي \(1\) لأن \(|A_1|=n-1\)، لكنه يبقى داخل الصيغة حفاظًا على انتظامها.
عدد المجموعات الفرعية \(R\) ذات الحجم \(r\) هو \(\binom{n-1}{r}\)، ولذلك يصبح مجموع الشمول والاستبعاد بعد التجميع
$$Q_k=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}{r}\prod_{i=1}^{k}\frac{\binom{n-i}{r}}{\binom{n-1}{r}}.$$
هذه هي الصيغة التي تنفذها نسخ C++ وPython وJava حرفيًا. وهناك تبسيط مهم آخر: عندما يكون \(r>n-i\) فإن \(\binom{n-i}{r}=0\). وبخاصة، إذا كان \(r>n-k\) فإن الحد كله يختفي تلقائيًا. لذلك، رغم أن الحلقة البرمجية تمتد حتى \(n-1\)، فإن الحدود غير الصفرية لا يمكن أن تأتي إلا من أول \(n-k+1\) قيم.
والكمية النهائية المطلوبة في المسألة هي
$$\boxed{P_k=\frac{Q_k}{n!}.}$$
هذه القسمة على \(n!\) ليست حيلة عددية، بل جزء من تعريف الكمية نفسها. وجميع التنفيذات الثلاثة تؤجلها إلى ما بعد اكتمال المجموع المتناوب بدقة عالية.
عندما \(k=3\)، نحصل على \(n=\frac{3\cdot2}{2}+1=4\)، ومن ثم \(|\mathcal{U}|=3\) واحجام المراحل هي \(3,2,1\). وعندئذ تصبح الصيغة
$$Q_3=\sum_{r=0}^{3}(-1)^r\binom{3}{r}\prod_{i=1}^{3}\frac{\binom{4-i}{r}}{\binom{3}{r}}.$$
الحد عند \(r=0\) يساوي \(1\). وعند \(r=1\) نطرح
$$\binom{3}{1}\left(\frac{\binom{3}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{2}{1}}{\binom{3}{1}}\right)\left(\frac{\binom{1}{1}}{\binom{3}{1}}\right)=3\cdot1\cdot\frac23\cdot\frac13=\frac23.$$
أما جميع الحدود التي فيها \(r\ge2\) فتساوي صفرًا، لأن المرحلة الاخيرة لا تترك إلا موضعًا ناجيًا واحدًا. لذلك
$$Q_3=1-\frac23=\frac13,$$
وبعد التطبيع نحصل على
$$P_3=\frac{1/3}{4!}=\frac1{72}.$$
وهذه هي بالضبط القيمة المستخدمة في اختبارات التحقق داخل التنفيذات، مما يؤكد أن الاشتقاق الرياضي يطابق الحساب البرمجي تمامًا.
التنفيذات في C++ وPython وJava تتبع الخطة نفسها. فهي تضبط اولًا بيئة حساب عشري عالي الدقة، ثم تحسب \(n=\frac{k(k-1)}2+1\)، وبعد ذلك تمر على مجموع متناوب حيث \(r=0,1,\dots,n-1\). عند كل قيمة \(r\)، تحسب بدقة المعامل الثنائي \(\binom{n-1}{r}\)، ثم تضرب نسب المراحل \( \binom{n-i}{r}/\binom{n-1}{r} \) لعدد \(k\) من المرات.
بعد تكوين حاصل الضرب، تعيد الشفرة العامل الخارجي \(\binom{n-1}{r}\)، وتطبق الإشارة \((-1)^r\)، ثم تضيف الحد إلى المجموع الجاري. ولا توجد حاجة إلى جداول رمزية كبيرة أو تجهيزات مسبقة معقدة، لأن الحالة المستهدفة \(k=7\) تعطي أعدادًا صغيرة جدًا.
بعد اكتمال المجموع \(Q_k\)، تقسم الشفرة النتيجة على \(n!\) بالدقة العالية نفسها. وفي النهاية تتحقق من القيم المعروفة عند \(k=2\) و\(k=3\) و\(k=4\)، ثم تطبع جواب \(k=7\) بالصيغة العلمية.
إذا اعتبرنا أن المعاملات الثنائية متاحة في زمن \(O(1)\)، فإن القلب الرياضي ليس إلا مجموعًا خارجيًا على \(r\) مع \(k\) عوامل في كل حد، أي \(O(nk)\). وبما أن \(n=\Theta(k^2)\)، فإن الصيغة المغلقة نفسها يمكن النظر إليها على أنها \(O(k^3)\).
لكن التنفيذين الحرفيين في C++ وJava يعيدان حساب كل معامل ثنائي بواسطة حلقة ضرب قصيرة، لذلك يصبح العد الخام للعمليات الحسابية أقرب إلى \(O(kn^2)\). ومع ذلك، ففي الحالة الفعلية \(k=7\) و\(n=22\)، يبقى الزمن ضئيلًا جدًا. واستهلاك الذاكرة هو \(O(1)\) باستثناء كائنات الدقة العالية اللازمة للمجموع والعامل النهائي.