Problem 930 studies a gathering process on the cycle graph \(C_n\) with \(m\) walkers. The quantity \(F(n,m)\) is the average gathering time for that pair \((n,m)\), and the final target is
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
The local implementations do not simulate the Markov chain step by step. Instead, they evaluate the spectral decomposition of the relative-position chain, then group equal Fourier modes together so the final sum runs over occupancy counts \(x_0,\dots,x_{n-1}\).
Only relative positions matter for gathering. If all walkers are shifted by the same amount around the cycle, the configuration is unchanged from the point of view of the meeting event. That means the natural state space is the quotient
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
Write \(\omega=e^{2\pi i/n}\). A Fourier character on \((\mathbb{Z}/n\mathbb{Z})^m\) has the form
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
where \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). Such a character descends to the quotient exactly when it is invariant under the diagonal shift \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\). That condition is
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
The implementations do not keep the ordered \(m\)-tuple \(k\) directly. They only need to know how many entries of \(k\) are equal to each residue \(r\in\{0,1,\dots,n-1\}\). Define
\[ x_r=\#\{j:k_j=r\}. \]
Then the admissible vectors satisfy
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
So the summation is over the set
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
Many ordered frequency tuples produce the same occupancy vector \(x\). Their multiplicity is the multinomial coefficient
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
This is exactly what the implementations build incrementally with a product of binomial coefficients:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
In one step of the gathering chain, one of the \(m\) walkers is chosen uniformly, then that walker moves one edge left or right with probability \(1/2\). For a single Fourier frequency \(r\), the transition operator contributes the factor
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
If the whole mode is summarized by the occupancy vector \(x\), the corresponding eigenvalue is the average of those single-frequency factors:
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
The averaged hitting-time formula for the quotient chain therefore becomes
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
Written out explicitly, this is
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
The excluded vector \(x=(m,0,\dots,0)\) is the constant Fourier mode. It has \(\lambda(x)=1\), so it corresponds to the stationary part and would make the denominator vanish. Every other admissible vector has \(\lambda(x)<1\), since \(\cos(2\pi r/n)\le 1\) and equality occurs only at \(r=0\).
For \(n=3\) and \(m=2\), the constraints are
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
The only nontrivial solution is \(x=(0,1,1)\). Its multiplicity is
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
Its eigenvalue is
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
So the contribution is
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
which agrees with the exact small case used by the implementations.
The C++, Python, and Java implementations first build a Pascal-triangle table of binomial coefficients up to \(m\). They also precompute the list of cosine values \(\cos(2\pi r/n)\) for \(r=0,1,\dots,n-1\). Those two tables are enough to evaluate every grouped Fourier contribution.
The main recursion distributes the total mass \(m\) across the \(n\) residues. At every stage it maintains the remaining mass, the partial residue sum modulo \(n\), the partial cosine sum, and the current combinatorial multiplicity. When the last residue is reached, the implementation checks the congruence condition, discards the trivial all-zero-frequency mode, computes the denominator \(1-\lambda(x)\), and adds \(W(x)/(1-\lambda(x))\) to the running total.
Because the multiplicity is accumulated incrementally from binomial choices, the code never has to construct \(m!\) or any large tuple of frequencies directly. It works only with the grouped occupancy data that matter mathematically.
After one value \(F(n,m)\) is finished, the outer loops add it into the grand total for all \(2\le n\le 12\) and \(2\le m\le 12\). The C++ implementation also checks several small exact values before producing the final scientific-notation output.
For fixed \(n\) and \(m\), the recursion enumerates the weak compositions of \(m\) into \(n\) parts. Their count is
\[ \binom{m+n-1}{n-1}, \]
so the running time for one pair \((n,m)\) is of that order, up to constant work per branch and the \(O(m^2)\) preprocessing used to build the binomial table. The cosine table adds only \(O(n)\) work.
Therefore the total cost for the final answer is
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
with memory usage \(O(m^2+n)\) for the binomial table and cosine list, plus \(O(n)\) recursion depth. The important gain is that the algorithm sums grouped spectral terms directly instead of simulating an exponentially larger state graph.
Problem 930 behandelt einen Sammelprozess auf dem Zyklusgraphen \(C_n\) mit \(m\) Wanderern. Die Größe \(F(n,m)\) ist die mittlere Sammelzeit für dieses Paar \((n,m)\), und gesucht ist am Ende
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
Die lokalen Implementierungen simulieren die Markov-Kette nicht Schritt für Schritt. Stattdessen werten sie ihre Spektralzerlegung auf der Kette der Relativpositionen aus und fassen gleiche Fourier-Moden über Besetzungszahlen \(x_0,\dots,x_{n-1}\) zusammen.
Für das Sammeln zählen nur Relativpositionen. Wenn alle Wanderer gemeinsam um denselben Betrag auf dem Zyklus verschoben werden, ändert sich das Treffereignis nicht. Deshalb ist der natürliche Zustandsraum der Quotient
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
Mit \(\omega=e^{2\pi i/n}\) hat ein Fourier-Charakter auf \((\mathbb{Z}/n\mathbb{Z})^m\) die Form
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
wobei \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\) ist. Dieser Charakter steigt genau dann auf den Quotienten ab, wenn er unter der diagonalen Verschiebung \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\) invariant ist. Das ist äquivalent zu
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
Die Implementierungen speichern nicht das geordnete \(m\)-Tupel \(k\), sondern nur, wie oft jede Restklasse \(r\in\{0,1,\dots,n-1\}\) vorkommt. Dazu definiert man
\[ x_r=\#\{j:k_j=r\}. \]
Dann gilt für zulässige Vektoren
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
Die Summe läuft also über
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
Viele geordnete Frequenz-Tupel führen zum selben Besetzungsvektor \(x\). Ihre Anzahl ist der Multinomialkoeffizient
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
Genau diese Größe bauen die Implementierungen schrittweise aus Binomialfaktoren auf:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
In einem Schritt der Sammelkette wird einer der \(m\) Wanderer gleichverteilt ausgewählt und bewegt sich dann mit Wahrscheinlichkeit \(1/2\) eine Kante nach links oder rechts. Für eine einzelne Fourier-Frequenz \(r\) liefert der Übergangsoperator den Faktor
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
Wenn der gesamte Modus durch den Besetzungsvektor \(x\) beschrieben wird, ist der zugehörige Eigenwert daher
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
Damit wird die gemittelte Treffzeitformel auf dem Quotientenraum zu
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
Explizit ausgeschrieben:
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
Der ausgeschlossene Vektor \(x=(m,0,\dots,0)\) ist die konstante Fourier-Mode. Für ihn gilt \(\lambda(x)=1\); er gehört also zum stationären Anteil und würde den Nenner verschwinden lassen. Jeder andere zulässige Vektor erfüllt \(\lambda(x)<1\), weil \(\cos(2\pi r/n)\le 1\) und Gleichheit nur bei \(r=0\) eintritt.
Für \(n=3\) und \(m=2\) lauten die Bedingungen
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
Die einzige nichttriviale Lösung ist \(x=(0,1,1)\). Ihre Multiplizität ist
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
Der Eigenwert ist
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
Daher ergibt sich
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
genau wie im kleinen Exakttest der Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst eine Pascal-Tafel der Binomialkoeffizienten bis \(m\). Außerdem wird die Liste der Kosinuswerte \(\cos(2\pi r/n)\) für \(r=0,1,\dots,n-1\) vorbereitet. Mehr numerische Zutaten braucht die geschlossene Formel nicht.
Die Hauptrekursion verteilt die Gesamtmasse \(m\) auf die \(n\) Restklassen. Dabei hält sie die noch unverteilte Masse, die partielle Restsumme modulo \(n\), die partielle Kosinussumme und die aktuelle kombinatorische Multiplizität fest. Beim letzten Eintrag prüft die Implementierung die Kongruenzbedingung, verwirft die triviale reine Nullfrequenz-Mode, berechnet den Nenner \(1-\lambda(x)\) und addiert \(W(x)/(1-\lambda(x))\) zum laufenden Wert.
Weil die Multiplizität schrittweise aus Binomialentscheidungen aufgebaut wird, muss der Code weder \(m!\) direkt noch ein großes Frequenz-Tupel explizit erzeugen. Er arbeitet nur mit den mathematisch relevanten gruppierten Besetzungsdaten.
Nachdem ein Wert \(F(n,m)\) fertig ist, addieren die äußeren Schleifen ihn in die Gesamtsumme für alle \(2\le n\le 12\) und \(2\le m\le 12\). Die C++-Implementierung prüft zusätzlich einige kleine exakte Werte, bevor sie die endgültige Ausgabe in wissenschaftlicher Schreibweise erzeugt.
Für feste \(n\) und \(m\) enumeriert die Rekursion die schwachen Kompositionen von \(m\) in \(n\) Teile. Deren Anzahl ist
\[ \binom{m+n-1}{n-1}, \]
also liegt die Laufzeit für ein Paar \((n,m)\) in dieser Größenordnung, bis auf konstanten Aufwand pro Verzweigung und die \(O(m^2)\)-Vorberechnung der Binomialtafel. Die Kosinustabelle kostet nur \(O(n)\).
Damit erhält man insgesamt
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
während der Speicherbedarf \(O(m^2+n)\) für Binomialtafel und Kosinusliste sowie \(O(n)\) Rekursionstiefe beträgt. Der entscheidende Vorteil ist, dass der Algorithmus gruppierte Spektralterme direkt summiert, statt einen exponentiell größeren Zustandsgraphen zu simulieren.
Problem 930, \(C_n\) çevrim grafı üzerinde \(m\) yürüyücünün bir noktada toplanma sürecini inceler. \(F(n,m)\) bu \((n,m)\) çifti için ortalama toplanma süresidir ve nihai hedef
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m) \]
değerini hesaplamaktır. Yerel uygulamalar Markov zincirini adım adım simüle etmez. Bunun yerine göreli konum zincirinin spektral ayrışımını hesaplar ve eşdeğer Fourier modlarını \(x_0,\dots,x_{n-1}\) doluluk sayıları üzerinden gruplayarak toplar.
Toplanma olayı açısından yalnızca göreli konumlar önemlidir. Bütün yürüyücüler çevrim üzerinde aynı miktarda birlikte kaydırılırsa durum değişmez. Bu yüzden doğal durum uzayı
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle \]
bölümüdür. \(\omega=e^{2\pi i/n}\) olsun. \((\mathbb{Z}/n\mathbb{Z})^m\) üzerindeki bir Fourier karakteri
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m} \]
şeklindedir; burada \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). Bu karakterin bölüme inebilmesi için diyagonal kaydırma \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\) altında değişmemesi gerekir. Bu da
\[ k_1+\cdots+k_m\equiv 0 \pmod{n} \]
şartına eşdeğerdir.
Uygulamalar sıralı \(m\)-li frekans vektörünü doğrudan tutmaz. Yalnızca her artık sınıfı \(r\in\{0,1,\dots,n-1\}\) kaç kez kullanıldı sorusunu izler. Bunun için
\[ x_r=\#\{j:k_j=r\} \]
tanımı yapılır. O zaman geçerli vektörler
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \]
koşullarını sağlar. Yani toplam şu küme üzerinde alınır:
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
Aynı doluluk vektörü \(x\), birçok sıralı frekans seçimine karşılık gelir. Bunların sayısı multinom katsayısıdır:
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
Uygulamalarda bu ağırlık art arda binom çarpanlarıyla kuruluyor:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
Toplanma zincirinin bir adımında \(m\) yürüyücüden biri eşit olasılıkla seçilir; sonra bu yürüyücü \(1/2\) olasılıkla sola, \(1/2\) olasılıkla sağa bir kenar ilerler. Tek bir Fourier frekansı \(r\) için geçiş operatörü
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right) \]
çarpanını üretir. Bütün mod \(x\) doluluk vektörüyle özetlenirse, buna karşılık gelen özdeğer
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right) \]
olur. Böylece bölüm zincirinin ortalama vurma süresi formülü
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)} \]
biçimine iner. Açık yazarsak
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
Hariç tutulan \(x=(m,0,\dots,0)\) vektörü sabit Fourier modudur. Bunun için \(\lambda(x)=1\) olur; yani durağan parçayı temsil eder ve paydayı sıfır yapar. Diğer bütün geçerli vektörlerde \(\lambda(x)<1\) geçerlidir; çünkü \(\cos(2\pi r/n)\le 1\) ve eşitlik yalnızca \(r=0\) için mümkündür.
\(n=3\) ve \(m=2\) için koşullar
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3} \]
olur. Tek gayritrivial çözüm \(x=(0,1,1)\)'dir. Bunun ağırlığı
\[ W(x)=\frac{2!}{1!\,1!}=2 \]
ve özdeğeri
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2} \]
olur. Dolayısıyla
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
ki bu da uygulamalardaki küçük kesin kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce \(m\)'ye kadar Pascal üçgeni biçiminde binom katsayılarını üretir. Ardından \(r=0,1,\dots,n-1\) için \(\cos(2\pi r/n)\) tablosunu hazırlar. Kapalı formüldeki tüm katkılar bu iki veriyle hesaplanır.
Ana özyineleme toplam kütle \(m\)'yi \(n\) artık sınıfına dağıtır. Bu sırada kalan kütleyi, kısmi artık toplamını modulo \(n\), kısmi kosinüs toplamını ve mevcut kombinatoryel çarpanı birlikte taşır. Son sınıfa gelindiğinde uygulama kongruens koşulunu denetler, trivial saf sıfır-frekans modunu atar, \(1-\lambda(x)\) paydasını hesaplar ve \(W(x)/(1-\lambda(x))\) katkısını toplama ekler.
Ağırlık binom seçimlerinden kademeli olarak üretildiği için kod ne \(m!\)'yi açıkça kurmak ne de büyük frekans demetlerini tek tek oluşturmak zorunda kalır. Yalnızca matematiksel olarak gerekli olan gruplanmış doluluk verileriyle çalışır.
Bir \(F(n,m)\) değeri tamamlandıktan sonra dış döngüler bunu tüm \(2\le n\le 12\) ve \(2\le m\le 12\) çiftleri için büyük toplama ekler. C++ uygulaması ayrıca birkaç küçük kesin değeri doğruladıktan sonra sonucu bilimsel gösterimde yazar.
Sabit \(n\) ve \(m\) için özyineleme, \(m\)'nin \(n\) parçalı zayıf kompozisyonlarını gezer. Bunların sayısı
\[ \binom{m+n-1}{n-1} \]
olduğundan, bir \((n,m)\) çifti için çalışma süresi bu mertebededir; buna dal başına sabit iş ve binom tablosu için \(O(m^2)\) ön işlem eklenir. Kosinüs tablosu yalnızca \(O(n)\) maliyet getirir.
Bu yüzden toplam maliyet
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right) \]
şeklindedir. Bellek kullanımı binom tablosu ve kosinüs listesi için \(O(m^2+n)\), özyineleme derinliği için \(O(n)\)'dir. Asıl kazanç, algoritmanın üstel derecede daha büyük bir durum grafını simüle etmek yerine gruplanmış spektral terimleri doğrudan toplamasıdır.
El problema 930 estudia un proceso de reunión sobre el grafo ciclo \(C_n\) con \(m\) caminantes. La cantidad \(F(n,m)\) es el tiempo medio de reunión para ese par \((n,m)\), y el objetivo final es
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
Las implementaciones locales no simulan la cadena de Markov paso a paso. En su lugar evalúan la descomposición espectral de la cadena de posiciones relativas y agrupan los modos de Fourier equivalentes mediante los conteos de ocupación \(x_0,\dots,x_{n-1}\).
Para que todos se reúnan solo importan las posiciones relativas. Si todos los caminantes se desplazan juntos la misma cantidad alrededor del ciclo, la situación no cambia desde el punto de vista del encuentro. Por eso el espacio de estados natural es el cociente
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
Sea \(\omega=e^{2\pi i/n}\). Un carácter de Fourier sobre \((\mathbb{Z}/n\mathbb{Z})^m\) tiene la forma
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
donde \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). Este carácter desciende al cociente exactamente cuando es invariante bajo el corrimiento diagonal \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\). Esa condición es
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
Las implementaciones no guardan directamente el \(m\)-tuplo ordenado \(k\). Solo necesitan saber cuántas veces aparece cada residuo \(r\in\{0,1,\dots,n-1\}\). Definimos
\[ x_r=\#\{j:k_j=r\}. \]
Entonces los vectores admisibles cumplen
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
La suma se realiza, por tanto, sobre
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
Muchos tuplos ordenados de frecuencias producen el mismo vector de ocupación \(x\). Su multiplicidad es el coeficiente multinomial
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
Eso es exactamente lo que construyen las implementaciones mediante factores binomiales sucesivos:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
En un paso de la cadena de reunión se elige uniformemente uno de los \(m\) caminantes y luego ese caminante avanza una arista a la izquierda o a la derecha con probabilidad \(1/2\). Para una sola frecuencia de Fourier \(r\), el operador de transición aporta el factor
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
Si el modo completo queda resumido por el vector de ocupación \(x\), el autovalor correspondiente es
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
La fórmula del tiempo medio de llegada en la cadena cociente se convierte entonces en
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
Escrita por completo, queda
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
El vector excluido \(x=(m,0,\dots,0)\) es el modo de Fourier constante. Tiene \(\lambda(x)=1\), así que representa la parte estacionaria y haría cero el denominador. Todo vector admisible no trivial satisface \(\lambda(x)<1\), porque \(\cos(2\pi r/n)\le 1\) y la igualdad solo ocurre para \(r=0\).
Para \(n=3\) y \(m=2\), las restricciones son
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
La única solución no trivial es \(x=(0,1,1)\). Su multiplicidad vale
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
Su autovalor es
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
Por tanto,
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
exactamente el mismo valor pequeño que verifican las implementaciones.
Las implementaciones en C++, Python y Java construyen primero una tabla tipo triángulo de Pascal con los coeficientes binomiales hasta \(m\). También precalculan la lista de valores \(\cos(2\pi r/n)\) para \(r=0,1,\dots,n-1\). Con esas dos tablas basta para evaluar cada contribución espectral agrupada.
La recursión principal distribuye la masa total \(m\) entre los \(n\) residuos. En cada nivel mantiene la masa aún no asignada, la suma parcial de residuos módulo \(n\), la suma parcial de cosenos y la multiplicidad combinatoria acumulada. Cuando llega al último residuo, la implementación comprueba la congruencia, descarta el modo trivial de frecuencia cero, calcula el denominador \(1-\lambda(x)\) y añade \(W(x)/(1-\lambda(x))\) al total.
Como la multiplicidad se forma de manera incremental a partir de elecciones binomiales, el código nunca necesita construir \(m!\) de forma explícita ni enumerar un gran tuplo de frecuencias. Trabaja solo con los datos de ocupación agrupados que realmente importan en la fórmula.
Después de terminar un valor \(F(n,m)\), los bucles exteriores lo añaden a la suma global para todos los \(2\le n\le 12\) y \(2\le m\le 12\). La implementación en C++ además comprueba varios casos pequeños exactos antes de imprimir la respuesta final en notación científica.
Para \(n\) y \(m\) fijos, la recursión enumera las composiciones débiles de \(m\) en \(n\) partes. Su cantidad es
\[ \binom{m+n-1}{n-1}, \]
de modo que el tiempo para un par \((n,m)\) es de ese orden, salvo trabajo constante por rama y la precomputación \(O(m^2)\) necesaria para la tabla binomial. La tabla de cosenos solo añade \(O(n)\).
En consecuencia, el coste total para la respuesta final es
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
con memoria \(O(m^2+n)\) para la tabla binomial y la lista de cosenos, más profundidad recursiva \(O(n)\). La ventaja clave es que el algoritmo suma directamente términos espectrales agrupados en vez de simular un grafo de estados exponencialmente mayor.
第 930 题研究的是长度为 \(n\) 的环图 \(C_n\) 上，\(m\) 个行走者最终聚到同一顶点的过程。\(F(n,m)\) 表示这一对 \((n,m)\) 的平均聚集时间，最后要求的是
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
本地实现并不是逐步模拟整条 Markov 链，而是直接计算相对位置链的谱分解，并把等价的 Fourier 模式按照占据计数 \(x_0,\dots,x_{n-1}\) 合并后求和。
对“是否聚到一起”这个事件而言，真正重要的是相对位置，而不是整体转了多少格。如果所有行走者同时沿着环平移同样的距离，配置对于聚集问题没有变化。因此自然的状态空间是商空间
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
设 \(\omega=e^{2\pi i/n}\)。\((\mathbb{Z}/n\mathbb{Z})^m\) 上的 Fourier 特征函数可以写成
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
其中 \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\)。它能够下降到上面的商空间，当且仅当它在对角平移 \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\) 下保持不变。这个条件正是
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
实现并不直接保存有序的 \(m\) 元频率向量 \(k\)，而是只记录每个剩余类 \(r\in\{0,1,\dots,n-1\}\) 出现了多少次。定义
\[ x_r=\#\{j:k_j=r\}. \]
于是允许的向量必须满足
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
所以求和对象恰好是
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
很多有序频率元组会对应同一个占据向量 \(x\)。它们的总数是多项式系数
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
这也正是实现里用一连串二项式因子逐步累乘出来的量：
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
聚集链的一步操作是：先在 \(m\) 个行走者中等概率选一个，再让它以概率 \(1/2\) 向左走一条边，或以概率 \(1/2\) 向右走一条边。对单个 Fourier 频率 \(r\) 而言，转移算子贡献的因子是
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
如果整个模式由占据向量 \(x\) 概括，那么对应的特征值就是这些单频贡献的平均值：
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
于是商空间上的平均首次到达时间公式可以写成
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
完全展开后就是
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
被排除掉的 \(x=(m,0,\dots,0)\) 就是常数 Fourier 模式。它满足 \(\lambda(x)=1\)，对应平稳部分，因此会让分母变成零。除它之外的所有允许向量都满足 \(\lambda(x)<1\)，因为 \(\cos(2\pi r/n)\le 1\)，而等号只会在 \(r=0\) 时出现。
当 \(n=3\)、\(m=2\) 时，约束条件变成
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
唯一的非平凡解是 \(x=(0,1,1)\)。它的重数为
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
它的特征值是
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
因此
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
这与实现中用于小规模校验的精确值完全一致。
C++、Python 和 Java 实现都会先构造到 \(m\) 为止的 Pascal 三角形二项式系数表，再预先算出 \(r=0,1,\dots,n-1\) 的 \(\cos(2\pi r/n)\) 列表。闭式公式中的每一项都只依赖这两组数值。
主递归把总质量 \(m\) 分配到 \(n\) 个剩余类中。递归过程中一直维护四个量：尚未分配的质量、当前的模 \(n\) 剩余和、当前累积的余弦和，以及由连续二项式选择形成的组合重数。到达最后一个剩余类时，程序检查同余条件，剔除纯零频率的平凡模式，计算分母 \(1-\lambda(x)\)，并把 \(W(x)/(1-\lambda(x))\) 加入总和。
由于重数是通过连续的二项式因子逐步构造出来的，代码从不需要显式生成 \(m!\)，也不需要真的列出所有大型频率元组。它始终只处理公式中真正有意义的归并占据数据。
单个 \(F(n,m)\) 算完之后，外层双循环会把它加入所有 \(2\le n\le 12\)、\(2\le m\le 12\) 的总和中。C++ 实现还会先验证几个小规模精确值，再输出最终的科学计数法结果。
对固定的 \(n\) 和 \(m\)，递归枚举的是把 \(m\) 分成 \(n\) 份的弱组合，其数量为
\[ \binom{m+n-1}{n-1}. \]
因此单个 \((n,m)\) 的时间复杂度就是这个量级，再加上每条分支的常数工作，以及建立二项式系数表所需的 \(O(m^2)\) 预处理。余弦表只需要 \(O(n)\) 时间。
所以最终总复杂度为
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
空间复杂度则是二项式表和余弦表的 \(O(m^2+n)\)，外加 \(O(n)\) 的递归深度。真正的收益在于：算法直接累加归并后的谱项，而不是去模拟一个规模指数级更大的状态图。
Задача 930 рассматривает процесс сбора \(m\) блуждающих точек на цикле \(C_n\). Величина \(F(n,m)\) равна среднему времени до сбора для пары \((n,m)\), а итоговая цель имеет вид
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
Локальные реализации не моделируют цепь Маркова шаг за шагом. Вместо этого они вычисляют спектральное разложение цепи относительных положений и группируют одинаковые Fourier-моды по числам заполнения \(x_0,\dots,x_{n-1}\).
Для события сбора важны только относительные положения. Если всех ходоков сдвинуть по циклу на одну и ту же величину, конфигурация с точки зрения встречи не изменится. Поэтому естественное пространство состояний есть фактор
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
Пусть \(\omega=e^{2\pi i/n}\). Fourier-характер на \((\mathbb{Z}/n\mathbb{Z})^m\) имеет вид
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
где \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). Такой характер спускается на фактор тогда и только тогда, когда он инвариантен относительно диагонального сдвига \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\). Это равносильно условию
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
Реализация не хранит упорядоченный \(m\)-кортеж \(k\) напрямую. Достаточно знать, сколько раз каждая частота \(r\in\{0,1,\dots,n-1\}\) встречается. Определим
\[ x_r=\#\{j:k_j=r\}. \]
Тогда допустимые векторы удовлетворяют условиям
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
Следовательно, суммирование идет по множеству
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
Одному и тому же вектору заполнения \(x\) соответствуют многие упорядоченные наборы частот. Их число равно мультиномиальному коэффициенту
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
Именно эту величину реализации собирают по шагам через произведение биномиальных множителей:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
За один шаг цепи сбора равновероятно выбирается один из \(m\) ходоков, после чего он с вероятностью \(1/2\) идет на одно ребро влево или вправо. Для одной Fourier-частоты \(r\) оператор перехода дает множитель
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
Если весь мод описывается вектором заполнения \(x\), соответствующее собственное значение равно среднему этих вкладов:
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
Тем самым формула для среднего времени достижения на фактор-цепи принимает вид
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
В развернутом виде это
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
Исключенный вектор \(x=(m,0,\dots,0)\) есть постоянный Fourier-мод. Для него \(\lambda(x)=1\), то есть это стационарная часть, которая зануляет знаменатель. Для любого другого допустимого вектора выполняется \(\lambda(x)<1\), поскольку \(\cos(2\pi r/n)\le 1\), а равенство возможно только при \(r=0\).
При \(n=3\) и \(m=2\) ограничения имеют вид
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
Единственное нетривиальное решение это \(x=(0,1,1)\). Его кратность равна
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
Собственное значение равно
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
Следовательно,
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
что в точности совпадает с малой проверкой, встроенной в реализации.
Реализации на C++, Python и Java сначала строят таблицу биномиальных коэффициентов в стиле треугольника Паскаля до \(m\). Затем они заранее вычисляют список значений \(\cos(2\pi r/n)\) для \(r=0,1,\dots,n-1\). Этих двух таблиц достаточно для вычисления каждого сгруппированного спектрального вклада.
Основная рекурсия распределяет суммарную массу \(m\) по \(n\) классам остатков. На каждом шаге она хранит еще не распределенную массу, частичную сумму остатков по модулю \(n\), частичную сумму косинусов и текущую комбинаторную кратность. На последнем остатке реализация проверяет условие сравнения, отбрасывает тривиальный чисто нулевой мод, вычисляет знаменатель \(1-\lambda(x)\) и добавляет вклад \(W(x)/(1-\lambda(x))\) к накопленной сумме.
Поскольку кратность собирается постепенно из биномиальных выборов, коду не нужно явно строить \(m!\) и не нужно перечислять огромные кортежи частот. Он работает только с теми сгруппированными данными заполнения, которые действительно входят в формулу.
После вычисления одного значения \(F(n,m)\) внешние циклы добавляют его в общий итог по всем \(2\le n\le 12\) и \(2\le m\le 12\). Реализация на C++ дополнительно проверяет несколько небольших точных значений перед выводом окончательного ответа в научной записи.
При фиксированных \(n\) и \(m\) рекурсия перечисляет слабые композиции числа \(m\) на \(n\) частей. Их количество равно
\[ \binom{m+n-1}{n-1}, \]
поэтому время для одной пары \((n,m)\) имеет такой порядок, с точностью до константной работы на ветвь и предварительной обработки \(O(m^2)\) для таблицы биномиальных коэффициентов. Таблица косинусов требует только \(O(n)\).
Значит, полная сложность для окончательного ответа равна
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
а память составляет \(O(m^2+n)\) для биномиальной таблицы и списка косинусов плюс \(O(n)\) глубины рекурсии. Ключевой выигрыш в том, что алгоритм сразу суммирует сгруппированные спектральные члены, а не моделирует экспоненциально больший граф состояний.
المسألة 930 تدرس عملية اجتماع \(m\) من السائرين على الرسم الدوري \(C_n\). الكمية \(F(n,m)\) هي الزمن المتوسط للاجتماع لهذا الزوج \((n,m)\)، والهدف النهائي هو
\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]
التنفيذات المحلية لا تحاكي سلسلة ماركوف خطوة بخطوة. بدلا من ذلك فهي تحسب التحليل الطيفي لسلسلة المواضع النسبية، ثم تجمع أنماط Fourier المتكافئة عبر أعداد الإشغال \(x_0,\dots,x_{n-1}\).
في مسألة الاجتماع لا تهم المواضع المطلقة بل المواضع النسبية فقط. إذا أزحنا جميع السائرين بالمقدار نفسه حول الدورة فلا يتغير شيء بالنسبة إلى حدث الاجتماع. لذلك يكون فضاء الحالات الطبيعي هو خارج القسمة
\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]
ولتكن \(\omega=e^{2\pi i/n}\). عندئذ يأخذ حرف Fourier على \((\mathbb{Z}/n\mathbb{Z})^m\) الشكل
\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]
حيث \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). هذا الحرف يهبط إلى فضاء القسمة بالضبط عندما يكون ثابتا تحت الإزاحة القطرية \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\)، أي عندما يتحقق الشرط
\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]
التنفيذات لا تحتفظ مباشرة بالمتجه المرتب \(k\) ذي الطول \(m\). ما تحتاجه فعلا هو عدد مرات ظهور كل باقي \(r\in\{0,1,\dots,n-1\}\). لذلك نعرّف
\[ x_r=\#\{j:k_j=r\}. \]
وعندئذ يجب أن تحقق المتجهات المسموح بها
\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]
إذن تتم عملية الجمع على المجموعة
\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]
قد تنتج متجهات تردد مرتبة كثيرة المتجه نفسه \(x\). عددها يعطى بمعامل متعدد الحدود
\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
وهذه بالضبط هي الكمية التي تبنيها التنفيذات تدريجيا من حاصل ضرب معاملات ثنائية:
\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]
في خطوة واحدة من سلسلة الاجتماع نختار أحد السائرين \(m\) باحتمال متساو، ثم يتحرك هذا السائر حافة واحدة إلى اليسار أو اليمين باحتمال \(1/2\) لكل جهة. بالنسبة إلى تردد Fourier منفرد \(r\)، يعطي مؤثر الانتقال العامل
\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]
وإذا كان النمط كله موصوفا بمتجه الإشغال \(x\)، فإن القيمة الذاتية الموافقة هي متوسط هذه العوامل:
\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]
ومن ثم تصبح صيغة متوسط زمن الوصول في سلسلة القسمة
\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]
وبشكل صريح تماما نحصل على
\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]
المتجه المستبعد \(x=(m,0,\dots,0)\) هو النمط الثابت. لهذا النمط تكون \(\lambda(x)=1\)، أي إنه يمثل الجزء الساكن ويجعل المقام صفرا. أما كل متجه مسموح آخر فيحقق \(\lambda(x)<1\)، لأن \(\cos(2\pi r/n)\le 1\) وتتحقق المساواة فقط عند \(r=0\).
عندما \(n=3\) و\(m=2\) تصبح القيود
\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]
الحل غير التافه الوحيد هو \(x=(0,1,1)\). وتكون مضاعفيته
\[ W(x)=\frac{2!}{1!\,1!}=2. \]
أما قيمته الذاتية فهي
\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]
ولذلك نحصل على
\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]
وهو بالضبط نفس المقدار الصغير الذي تتحقق منه التنفيذات.
تنشئ تنفيذات C++ وPython وJava أولا جدولا لمعاملات ثنائية الحد على نمط مثلث باسكال حتى \(m\). ثم تحسب مسبقا قائمة القيم \(\cos(2\pi r/n)\) من أجل \(r=0,1,\dots,n-1\). وهاتان القائمتان تكفيان لتقييم كل مساهمة طيفية مجمعة.
تقوم العودية الرئيسية بتوزيع الكتلة الكلية \(m\) على \(n\) من البواقي. وخلال ذلك تحتفظ بالكتلة غير الموزعة بعد، ومجموع البواقي الجزئي modulo \(n\)، ومجموع جيوب التمام الجزئي، والمضاعفية التوافقية الحالية. وعند الوصول إلى الباقي الأخير تفحص التنفيذات شرط التطابق، وتستبعد النمط التافه ذا التردد الصفري الخالص، ثم تحسب المقام \(1-\lambda(x)\) وتضيف الحد \(W(x)/(1-\lambda(x))\) إلى المجموع.
ولأن المضاعفية تُبنى تدريجيا من اختيارات ثنائية، فلا حاجة إلى إنشاء \(m!\) صراحة ولا إلى تعداد متجهات تردد ضخمة واحدا واحدا. الكود يعمل فقط على بيانات الإشغال المجمعة التي تظهر فعلا في الصيغة الرياضية.
بعد إنهاء قيمة واحدة \(F(n,m)\)، تضيفها الحلقات الخارجية إلى المجموع الكلي لكل \(2\le n\le 12\) و\(2\le m\le 12\). كما أن تنفيذ C++ يفحص عدة قيم صغيرة دقيقة قبل طباعة الجواب النهائي بالصيغة العلمية.
عند تثبيت \(n\) و\(m\)، تعدد العودية التركيبات الضعيفة للعدد \(m\) إلى \(n\) أجزاء. وعددها هو
\[ \binom{m+n-1}{n-1}. \]
لذلك يكون زمن التنفيذ لزوج واحد \((n,m)\) من هذا الرتبة، مع عمل ثابت لكل فرع ومعالجة أولية \(O(m^2)\) لبناء جدول المعاملات الثنائية. أما جدول جيوب التمام فيكلف فقط \(O(n)\).
ومن ثم فإن الكلفة الكلية للجواب النهائي هي
\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]
بينما الذاكرة تساوي \(O(m^2+n)\) لجدول المعاملات الثنائية وقائمة جيوب التمام، إضافة إلى عمق عودية مقداره \(O(n)\). والفائدة الأساسية أن الخوارزمية تجمع الحدود الطيفية المجمعة مباشرة بدلا من محاكاة رسم حالات أكبر أسيّا.