For even \(n\), let \(P(n)\) be the number of permutations of \(2,3,\dots,n\) in which every adjacent pair is coprime. The target computation is \(P(34)\) modulo \(83456729\). A direct search grows far too quickly, so the implementations convert the problem into an exact count of Hamiltonian cycles in a balanced bipartite graph and then evaluate that count with a determinant/permanent inclusion-exclusion identity.
Write \(n=2m\). Introduce the odd side
$$U=\{1,3,5,\dots,2m-1\}$$
and the even side
$$V=\{2,4,6,\dots,2m\}.$$
Define the \(m\times m\) bipartite adjacency matrix \(B\) by
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{otherwise}. \end{cases}$$
The key point is that the original permutations of \(2,\dots,2m\) can be re-expressed as alternating structures in this augmented graph.
Among the numbers \(2,3,\dots,2m\), there are \(m\) even numbers and \(m-1\) odd numbers. Two even numbers can never be adjacent in a valid permutation, because their gcd is at least \(2\). Therefore every valid permutation must alternate parity. Since the evens are more numerous by one, the parity pattern is forced to be
$$E-O-E-O-\dots-O-E.$$
So the problem is not counting arbitrary coprime permutations; it is counting alternating even-odd paths whose endpoints are both even.
The number \(1\) is coprime to every even number, so adding it on the odd side balances the bipartition. If
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
is a valid permutation of \(2,\dots,2m\), then inserting \(1\) between the two endpoints produces the alternating cycle
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
Conversely, deleting \(1\) from such a cycle recovers a valid permutation. Thus \(P(2m)\) is exactly the number of Hamiltonian cycles in the balanced bipartite graph \((U,V)\), read from the distinguished vertex \(1\).
Any alternating cycle in a bipartite graph can be colored with two alternating edge colors. That splits the cycle into two perfect matchings, say \(M_1\) and \(M_2\). Conversely, the union of two perfect matchings is a spanning \(2\)-regular bipartite subgraph, so it is a disjoint union of even cycles.
A single Hamiltonian cycle is therefore the special case in which the ordered pair \((M_1,M_2)\) produces exactly one cycle rather than several disconnected cycles. The permanent counts perfect matchings without signs, while the determinant supplies the signs needed to cancel the unwanted multi-cycle decompositions.
Let the distinguished odd vertex be \(1\). For subsets \(I\subseteq U\setminus\{1\}\) and \(J\subseteq V\) with \(|I|=|J|=k\), denote by \(B_{I,J}\) the selected \(k\times k\) submatrix and by \(B_{\bar I,\bar J}\) the complementary \((m-k)\times(m-k)\) submatrix, where \(\bar I=U\setminus I\) still contains the distinguished vertex \(1\). The exact identity evaluated by the code is
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
The squared permanent counts ordered pairs of perfect matchings on the complementary block. The squared determinant creates the sign-reversing correction that removes disconnected cycle covers and leaves only Hamiltonian cycles through the distinguished row.
If two selectable odd vertices have identical neighborhoods, then choosing both of them inside a determinant block would create two equal rows, so the determinant would vanish. The same is true for equal columns. That means the determinant part only needs one representative from each row class and each column class, with a multiplicity factor recording how many interchangeable choices exist.
The permanent part is different: repeated columns do not vanish there. Instead, the implementations use a grouped form of Ryser's formula. If a column class has size \(s\) and exactly \(t\) columns from that class are selected in a Ryser subset, then there are
$$\binom{s}{t}$$
ways to make that choice, and the row sums depend only on \(t\), not on which particular columns were taken.
Here \(m=2\), so
$$U=\{1,3\},\qquad V=\{2,4\}.$$
Every odd-even pair is coprime, hence
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
After anchoring the count at \(1\), only one non-distinguished odd row remains selectable. The formula has two types of contribution:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
and
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
Therefore
$$P(4)=4-2=2,$$
corresponding to the two valid permutations \((2,3,4)\) and \((4,3,2)\). This is the smallest checkpoint used by the implementations.
The C++, Python, and Java implementations first build the \(m\times m\) coprimality matrix between \(U\) and \(V\), together with binomial coefficients up to \(m\). They then classify rows by equal support masks, remove one copy of the distinguished row \(1\), and classify columns in the same way by applying the same mask logic to the transpose.
For every \(k\), the implementation enumerates all choices of \(k\) row classes and \(k\) column classes. The determinant block is formed from the chosen representatives; if its determinant is \(0\), that branch is discarded immediately. Otherwise the code squares the determinant, applies the sign \((-1)^k\), and multiplies by the class multiplicities.
The complementary block is then sent to a grouped permanent routine. The determinant is computed with fraction-free elimination modulo \(83456729\). The permanent is computed with Ryser's formula, but columns with identical support masks are grouped: a small prefix of classes is handled by explicit bitmask subsets, and the remaining large classes are handled recursively by choosing only how many columns are selected from each class. Each choice contributes a binomial factor \(\binom{s}{t}\).
Finally the code multiplies
$$\text{multiplicity}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
for each branch and accumulates the result modulo \(83456729\). The implementations include small checkpoints such as \(P(4)=2\) and \(P(10)=576\), and the C++ version also cross-checks tiny cases by brute force.
Let \(m=n/2\). If \(R\) and \(C\) are the numbers of distinct selectable row and column classes, the outer enumeration examines
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
class pairs. A determinant on a \(k\times k\) block costs \(O(k^3)\). For the complementary block of size \(r=m-k\), naive Ryser would cost \(O(r2^r)\), but grouping identical columns reduces the subset space to roughly
$$2^b\prod_i (s_i+1),$$
where \(b<10\) is the explicitly enumerated prefix size and the \(s_i\) are the remaining column-class sizes. The permanent stage then spends about \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) arithmetic operations. Memory usage is polynomial in the current block size, plus the explicit subset table of size \(2^b\). For the target case \(n=34\), this compression is what makes the exact count practical.
Für gerades \(n\) sei \(P(n)\) die Anzahl der Permutationen von \(2,3,\dots,n\), bei denen jedes benachbarte Paar teilerfremd ist. Gesucht ist \(P(34)\) modulo \(83456729\). Direkte Enumeration wächst viel zu schnell, deshalb verwandeln die Implementierungen das Problem in eine exakte Zählung von Hamilton-Kreisen in einem balancierten bipartiten Graphen und werten diese Zählung anschließend mit einer Determinanten-/Permanenten-Identität per Inklusion-Exklusion aus.
Schreibe \(n=2m\). Führe die ungerade Seite
$$U=\{1,3,5,\dots,2m-1\}$$
und die gerade Seite
$$V=\{2,4,6,\dots,2m\}$$
ein. Die \(m\times m\)-Adjazenzmatrix \(B\) sei definiert durch
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{sonst}. \end{cases}$$
Der entscheidende Punkt ist, dass sich die ursprünglichen Permutationen von \(2,\dots,2m\) als alternierende Strukturen in diesem erweiterten Graphen schreiben lassen.
Unter den Zahlen \(2,3,\dots,2m\) gibt es \(m\) gerade und \(m-1\) ungerade Zahlen. Zwei gerade Zahlen können niemals benachbart sein, denn ihr ggT ist mindestens \(2\). Also muss jede gültige Permutation nach Parität alternieren. Weil es genau eine gerade Zahl mehr gibt, ist das Muster fest vorgegeben:
$$E-O-E-O-\dots-O-E.$$
Gesucht sind also nicht beliebige teilerfremde Permutationen, sondern alternierende Gerade-Ungerade-Pfade mit geraden Endpunkten.
Die Zahl \(1\) ist zu jeder geraden Zahl teilerfremd und balanciert deshalb die bipartite Aufteilung aus. Ist
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
eine gültige Permutation von \(2,\dots,2m\), so erhält man durch Einfügen von \(1\) zwischen die beiden Endpunkte den alternierenden Kreis
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
Umgekehrt liefert das Entfernen von \(1\) wieder eine gültige Permutation. Damit ist \(P(2m)\) genau die Anzahl der Hamilton-Kreise im balancierten bipartiten Graphen \((U,V)\), gelesen vom ausgezeichneten Knoten \(1\) aus.
Jeder alternierende Kreis in einem bipartiten Graphen lässt sich mit zwei abwechselnden Kantenfarben färben. Dadurch zerfällt er in zwei perfekte Matchings \(M_1\) und \(M_2\). Umgekehrt ist die Vereinigung zweier perfekter Matchings ein aufspannender \(2\)-regulärer bipartiter Teilgraph und damit eine disjunkte Vereinigung gerader Kreise.
Ein einzelner Hamilton-Kreis ist also genau der Spezialfall, in dem das geordnete Paar \((M_1,M_2)\) nur einen einzigen Kreis erzeugt. Die Permanente zählt perfekte Matchings ohne Vorzeichen, während die Determinante die Vorzeichen liefert, mit denen unerwünschte Mehrkreis-Zerlegungen weggekürzt werden.
Der ausgezeichnete ungerade Knoten sei \(1\). Für Teilmengen \(I\subseteq U\setminus\{1\}\) und \(J\subseteq V\) mit \(|I|=|J|=k\) bezeichne \(B_{I,J}\) den gewählten \(k\times k\)-Block und \(B_{\bar I,\bar J}\) den komplementären \((m-k)\times(m-k)\)-Block, wobei \(\bar I=U\setminus I\) weiterhin den ausgezeichneten Knoten \(1\) enthält. Die exakt ausgewertete Identität lautet
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
Das Quadrat der Permanenten zählt geordnete Paare perfekter Matchings auf dem komplementären Block. Das Quadrat der Determinante erzeugt die vorzeichenbehaftete Korrektur, die disjunkte Kreisüberdeckungen eliminiert und nur Hamilton-Kreise durch die ausgezeichnete Zeile übrig lässt.
Haben zwei wählbare ungerade Knoten dieselbe Nachbarschaft, dann würden in einem Determinantenblock zwei gleiche Zeilen auftreten, also wäre die Determinante null. Dasselbe gilt für gleiche Spalten. Deshalb braucht der Determinantenteil nur einen Repräsentanten je Zeilenklasse und Spaltenklasse; die Anzahl austauschbarer Möglichkeiten erscheint als Multiplikitätsfaktor.
Beim Permanenten-Teil ist die Lage anders: Dort verschwinden wiederholte Spalten nicht. Deshalb verwenden die Implementierungen eine gruppierte Form der Ryser-Formel. Hat eine Spaltenklasse Größe \(s\) und werden in einer Ryser-Teilmenge genau \(t\) Spalten aus dieser Klasse gewählt, dann gibt es
$$\binom{s}{t}$$
Möglichkeiten dafür, und die Zeilensummen hängen nur von \(t\) ab, nicht von den konkret ausgewählten Spalten.
Hier ist \(m=2\), also
$$U=\{1,3\},\qquad V=\{2,4\}.$$
Jedes ungerade-gerade Paar ist teilerfremd, daher
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
Nach der Verankerung bei \(1\) bleibt genau eine nicht-ausgezeichnete ungerade Zeile wählbar. Die Formel hat zwei Beitragstypen:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
und
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
Damit folgt
$$P(4)=4-2=2,$$
also genau die beiden gültigen Permutationen \((2,3,4)\) und \((4,3,2)\). Das ist zugleich der kleinste Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen bauen zunächst die \(m\times m\)-Koprimalitätsmatrix zwischen \(U\) und \(V\) sowie die Binomialkoeffizienten bis \(m\) auf. Anschließend gruppieren sie Zeilen mit gleicher Bitmaske der Nachbarschaft, entfernen eine Kopie der ausgezeichneten Zeile \(1\) und bestimmen die Spaltenklassen analog über die transponierte Matrix.
Für jedes \(k\) enumeriert die Implementierung alle Wahlen von \(k\) Zeilenklassen und \(k\) Spaltenklassen. Aus den gewählten Repräsentanten wird der Determinantenblock gebildet; ist seine Determinante \(0\), wird der Zweig sofort verworfen. Andernfalls wird die Determinante quadriert, mit dem Vorzeichen \((-1)^k\) versehen und mit den Klassenmultiplikitäten multipliziert.
Der komplementäre Block geht dann in eine gruppierte Permanentenroutine. Die Determinante wird per bruchfreier Elimination modulo \(83456729\) berechnet. Die Permanente wird mit der Ryser-Formel berechnet, wobei Spalten mit gleicher Bitmaske zusammengefasst werden: Ein kleiner Präfix von Klassen wird explizit per Bitmaske enumeriert, während für die übrigen großen Klassen rekursiv nur die Anzahl ausgewählter Spalten bestimmt wird. Jede solche Wahl trägt einen Binomialfaktor \(\binom{s}{t}\).
Am Ende akkumuliert der Code für jeden Zweig den Ausdruck
$$\text{Multiplikität}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
modulo \(83456729\). Kleine Kontrollwerte wie \(P(4)=2\) und \(P(10)=576\) sind eingebaut; die C++-Implementierung vergleicht außerdem winzige Fälle zusätzlich mit einer Brute-Force-Zählung.
Sei \(m=n/2\). Wenn \(R\) und \(C\) die Anzahl verschiedener wählbarer Zeilen- und Spaltenklassen sind, betrachtet die äußere Enumeration
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
Klassenpaare. Eine Determinante auf einem \(k\times k\)-Block kostet \(O(k^3)\). Für den komplementären Block der Größe \(r=m-k\) würde naives Ryser \(O(r2^r)\) kosten; durch das Zusammenfassen gleicher Spalten schrumpft der Zustandsraum jedoch auf ungefähr
$$2^b\prod_i (s_i+1),$$
wobei \(b<10\) die explizit enumerierte Präfixgröße und \(s_i\) die Größen der übrigen Spaltenklassen sind. Die Permanentenphase benötigt damit ungefähr \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) arithmetische Operationen. Der Speicherbedarf bleibt polynomial in der aktuellen Blockgröße, zuzüglich einer expliziten Teilmengentabelle der Größe \(2^b\). Für den Zielwert \(n=34\) macht erst diese Kompression die exakte Berechnung praktikabel.
Çift \(n\) için \(P(n)\), \(2,3,\dots,n\) sayılarının öyle permütasyonlarının sayısıdır ki her komşu çift aralarında asaldır. Hedef hesap \(P(34)\) değerini \(83456729\) modunda bulmaktır. Doğrudan tarama aşırı hızlı büyüdüğü için uygulamalar problemi dengeli bir iki parçalı graf üzerinde Hamilton çevrimi sayımına dönüştürüyor ve sonra bu sayımı determinant/permanent temelli bir dahil etme-çıkarma özdeşliğiyle hesaplıyor.
\(n=2m\) yazalım. Tek tarafı
$$U=\{1,3,5,\dots,2m-1\}$$
ve çift tarafı
$$V=\{2,4,6,\dots,2m\}$$
olarak tanımlayalım. \(m\times m\) boyutlu iki parçalı komşuluk matrisi \(B\) şu şekilde verilsin:
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{aksi halde}. \end{cases}$$
Asıl fikir, \(2,\dots,2m\) üzerindeki permütasyonları bu genişletilmiş graf içindeki dönüşümlü yapılara çevirmektir.
\(2,3,\dots,2m\) arasında \(m\) tane çift ve \(m-1\) tane tek sayı vardır. İki çift sayı komşu olamaz; çünkü EBOB'ları en az \(2\) olur. Bu yüzden her geçerli permütasyon parite bakımından dönüşümlü olmak zorundadır. Çift sayılar bir tane fazla olduğundan desen zorunlu olarak
$$E-O-E-O-\dots-O-E$$
şeklindedir. Yani saydığımız nesne keyfi bir coprime permütasyon değil, uçları çift olan tek-çift dönüşümlü bir yoldur.
\(1\) sayısı her çift sayı ile aralarında asal olduğu için tek tarafa eklendiğinde iki parçalı yapı dengelenir. Eğer
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
\(2,\dots,2m\) için geçerli bir permütasyonsa, uçların arasına \(1\) ekleyerek şu dönüşümlü çevrimi elde ederiz:
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
Tersine, böyle bir çevrimden \(1\) çıkarılınca geçerli bir permütasyon geri kazanılır. Dolayısıyla \(P(2m)\), \(1\) ayırt edilmiş düğümünden okunan dengeli iki parçalı \((U,V)\) grafındaki Hamilton çevrimlerinin sayısıdır.
İki parçalı bir graftaki her dönüşümlü çevrim, kenarlar sırayla iki renge boyanarak iki perfect matching'e ayrılabilir. Buna \(M_1\) ve \(M_2\) diyelim. Tersine, iki perfect matching'in birleşimi tüm düğümleri kapsayan \(2\)-düzenli bir iki parçalı altgraf üretir; bu da ayrık çift uzunluklu çevrimlerin birleşimidir.
Tek bir Hamilton çevrimi, işte bu birleşimin yalnızca bir çevrim oluşturduğu özel durumdur. Permanent işaret kullanmadan perfect matching sayar; determinant ise birden fazla ayrık çevrimden gelen katkıları iptal etmek için gereken işaret yapısını sağlar.
Ayırt edilmiş tek düğüm \(1\) olsun. \(|I|=|J|=k\) olacak şekilde \(I\subseteq U\setminus\{1\}\) ve \(J\subseteq V\) seçelim. \(B_{I,J}\) seçilen \(k\times k\) bloğu, \(B_{\bar I,\bar J}\) ise \(\bar I=U\setminus I\) kümesi hâlâ \(1\)'i içerirken kalan \((m-k)\times(m-k)\) tamamlayıcı bloğu göstersin. Kodun kullandığı tam özdeşlik şudur:
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
Permanent'in karesi, tamamlayıcı blok üzerindeki sıralı perfect matching çiftlerini sayar. Determinant'ın karesi ise işaretli düzeltmeyi getirir; böylece ayrık çevrim örtüleri silinir ve yalnızca ayırt edilmiş satırdan geçen Hamilton çevrimleri kalır.
Seçilebilir iki tek düğümün komşulukları aynıysa, ikisini bir determinant bloğuna birlikte koymak aynı iki satır üretir ve determinant sıfır olur. Aynı durum eş satırlar için değil, eş sütunlar için de geçerlidir. Bu yüzden determinant kısmında her satır sınıfından ve sütun sınıfından yalnızca bir temsilci gerekidir; kaç farklı ama eşdeğer seçim olduğu ise çarpan olarak tutulur.
Permanent tarafında tekrar eden sütunlar yok olmaz. Bu nedenle uygulamalar Ryser formülünün gruplanmış bir sürümünü kullanır. Bir sütun sınıfının büyüklüğü \(s\) ve bir Ryser altkümesinde bu sınıftan seçilen sütun sayısı \(t\) ise, bu seçim sayısı
$$\binom{s}{t}$$
kadardır; ayrıca satır toplamları sadece \(t\)'ye bağlıdır, hangi sütunların seçildiğine değil.
Burada \(m=2\), dolayısıyla
$$U=\{1,3\},\qquad V=\{2,4\}.$$
Her tek-çift çifti aralarında asal olduğundan
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
Sayımı \(1\)'e sabitledikten sonra seçilebilir tek ayırt edilmemiş tek satır kalır. Formülde iki tür katkı vardır:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
ve
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
Böylece
$$P(4)=4-2=2$$
elde edilir. Bunlar \((2,3,4)\) ve \((4,3,2)\) permütasyonlarıdır; uygulamaların en küçük kontrol noktası da budur.
C++, Python ve Java uygulamaları önce \(U\) ile \(V\) arasındaki \(m\times m\) aralarında asallık matrisini ve \(m\)'e kadar binom katsayılarını kurar. Sonra aynı destek maskesine sahip satırları sınıflandırır, ayırt edilmiş \(1\) satırının bir kopyasını çıkarır ve aynı mantığı transpoza uygulayarak sütun sınıflarını elde eder.
Her \(k\) için uygulama \(k\) satır sınıfı ve \(k\) sütun sınıfı seçimlerini dolaşır. Seçilen temsilcilerden determinant bloğu kurulur; determinant \(0\) ise dal hemen atılır. Aksi halde determinant karesi alınır, \((-1)^k\) işareti uygulanır ve sınıf çokluklarıyla çarpılır.
Tamamlayıcı blok daha sonra gruplanmış permanent yordamına gönderilir. Determinant, \(83456729\) modunda kesirsiz eliminasyonla hesaplanır. Permanent ise Ryser formülüyle hesaplanır; fakat aynı destek maskesine sahip sütunlar birleştirilir. Küçük bir sınıf öneki açık bitmask ile gezilir, geri kalan büyük sınıflarda ise yalnızca her sınıftan kaç sütun seçildiği özyinelemeli olarak belirlenir. Her seçim \(\binom{s}{t}\) çarpanını getirir.
Son olarak kod her dal için
$$\text{çokluk}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
ifadesini \(83456729\) modunda toplar. \(P(4)=2\) ve \(P(10)=576\) gibi küçük kontrol değerleri kullanılır; C++ sürümü ayrıca çok küçük örnekleri brute force ile de doğrular.
\(m=n/2\) olsun. \(R\) ve \(C\) seçilebilir satır ve sütun sınıflarının sayılarıysa dış enumerasyon
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
adet sınıf çifti inceler. \(k\times k\) bir blok determinantı \(O(k^3)\) maliyetlidir. \(r=m-k\) boyutlu tamamlayıcı blok için saf Ryser \(O(r2^r)\) sürerdi; fakat aynı sütunları gruplayınca durum uzayı yaklaşık olarak
$$2^b\prod_i (s_i+1)$$
seviyesine düşer. Burada \(b<10\) açıkça enumerate edilen önek büyüklüğü, \(s_i\) ise kalan sütun sınıflarının boyutlarıdır. Permanent aşaması böylece yaklaşık \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) aritmetik işlem harcar. Bellek kullanımı mevcut blok boyutunda polinomiktir; buna ek olarak \(2^b\) büyüklüğünde açık altküme tablosu bulunur. \(n=34\) hedefi için tam hesabı uygulanabilir kılan şey bu sıkıştırmadır.
Para \(n\) par, \(P(n)\) es el número de permutaciones de \(2,3,\dots,n\) en las que cada par adyacente es coprimo. El objetivo es calcular \(P(34)\) módulo \(83456729\). Una búsqueda directa crece demasiado rápido, así que las implementaciones transforman el problema en un conteo exacto de ciclos hamiltonianos en un grafo bipartito balanceado y luego evalúan ese conteo mediante una identidad de inclusión-exclusión con determinantes y permanentes.
Escribamos \(n=2m\). Introducimos el lado impar
$$U=\{1,3,5,\dots,2m-1\}$$
y el lado par
$$V=\{2,4,6,\dots,2m\}.$$
La matriz de adyacencia bipartita \(B\), de tamaño \(m\times m\), queda definida por
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{en otro caso}. \end{cases}$$
La idea central es reexpresar las permutaciones originales de \(2,\dots,2m\) como estructuras alternantes dentro de este grafo aumentado.
Entre \(2,3,\dots,2m\) hay \(m\) números pares y \(m-1\) impares. Dos pares nunca pueden ser adyacentes en una permutación válida, porque su gcd es al menos \(2\). Por tanto, toda permutación válida debe alternar paridad. Como hay un par más que impares, el patrón queda forzado:
$$E-O-E-O-\dots-O-E.$$
Así, el problema real no es contar permutaciones coprimas arbitrarias, sino caminos alternantes par-impar cuyos dos extremos son pares.
El número \(1\) es coprimo con todo número par, de modo que al añadirlo al lado impar la bipartición queda balanceada. Si
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
es una permutación válida de \(2,\dots,2m\), entonces al insertar \(1\) entre sus extremos obtenemos el ciclo alternante
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
En sentido contrario, eliminar \(1\) de un ciclo así devuelve una permutación válida. Por lo tanto, \(P(2m)\) coincide exactamente con el número de ciclos hamiltonianos del grafo bipartito balanceado \((U,V)\), leído desde el vértice distinguido \(1\).
Cualquier ciclo alternante de un grafo bipartito puede colorearse con dos colores alternos en sus aristas. Eso lo descompone en dos emparejamientos perfectos, digamos \(M_1\) y \(M_2\). Recíprocamente, la unión de dos emparejamientos perfectos es un subgrafo bipartito \(2\)-regular que cubre todos los vértices, así que es una unión disjunta de ciclos pares.
Un único ciclo hamiltoniano es justamente el caso especial en el que el par ordenado \((M_1,M_2)\) produce un solo ciclo en vez de varios. La permanente cuenta emparejamientos perfectos sin signos; el determinante aporta los signos necesarios para cancelar las descomposiciones con múltiples ciclos.
Sea \(1\) el vértice impar distinguido. Para subconjuntos \(I\subseteq U\setminus\{1\}\) y \(J\subseteq V\) con \(|I|=|J|=k\), denotemos por \(B_{I,J}\) el bloque seleccionado de tamaño \(k\times k\) y por \(B_{\bar I,\bar J}\) el bloque complementario de tamaño \((m-k)\times(m-k)\), donde \(\bar I=U\setminus I\) todavía contiene al vértice distinguido \(1\). La identidad exacta usada por el código es
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
La permanente al cuadrado cuenta pares ordenados de emparejamientos perfectos en el bloque complementario. El determinante al cuadrado introduce la corrección con signo que elimina las cubiertas por varios ciclos desconectados y deja solo los ciclos hamiltonianos que pasan por la fila distinguida.
Si dos vértices impares seleccionables tienen exactamente el mismo vecindario, entonces elegir ambos dentro de un bloque de determinante produciría dos filas iguales y el determinante sería cero. Lo mismo ocurre con columnas iguales. Por eso, en la parte determinantal solo hace falta un representante por cada clase de filas y de columnas, multiplicando luego por la cantidad de elecciones intercambiables.
La parte de la permanente es distinta: allí las columnas repetidas no se anulan. En su lugar, las implementaciones usan una forma agrupada de la fórmula de Ryser. Si una clase de columnas tiene tamaño \(s\) y en un subconjunto de Ryser se seleccionan exactamente \(t\) columnas de esa clase, el número de elecciones es
$$\binom{s}{t}$$
y las sumas por fila dependen solo de \(t\), no de qué columnas concretas fueron elegidas.
Aquí \(m=2\), así que
$$U=\{1,3\},\qquad V=\{2,4\}.$$
Todo par impar-par es coprimo, luego
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
Tras anclar el conteo en \(1\), solo queda una fila impar no distinguida que puede seleccionarse. La fórmula tiene dos tipos de aportes:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
y
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
Por lo tanto,
$$P(4)=4-2=2,$$
que corresponde a las dos permutaciones válidas \((2,3,4)\) y \((4,3,2)\). Es el control más pequeño usado por las implementaciones.
Las implementaciones en C++, Python y Java construyen primero la matriz \(m\times m\) de coprimalidad entre \(U\) y \(V\), junto con los coeficientes binomiales hasta \(m\). Después agrupan las filas por máscara de soporte idéntica, eliminan una copia de la fila distinguida \(1\) y obtienen las clases de columnas aplicando la misma lógica a la traspuesta.
Para cada \(k\), la implementación enumera todas las elecciones de \(k\) clases de fila y \(k\) clases de columna. El bloque de determinante se forma con los representantes elegidos; si su determinante vale \(0\), esa rama se descarta inmediatamente. En caso contrario, el código eleva el determinante al cuadrado, aplica el signo \((-1)^k\) y multiplica por las multiplicidades de las clases.
El bloque complementario se envía a una rutina de permanente agrupada. El determinante se calcula mediante eliminación libre de fracciones módulo \(83456729\). La permanente se calcula con la fórmula de Ryser, pero agrupando columnas con la misma máscara de soporte: un prefijo pequeño de clases se maneja con subconjuntos explícitos por bitmask, mientras que las clases grandes restantes se recorren recursivamente eligiendo solo cuántas columnas se toman de cada clase. Cada elección aporta un factor \(\binom{s}{t}\).
Al final, el código acumula para cada rama
$$\text{multiplicidad}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
módulo \(83456729\). También incorpora comprobaciones pequeñas como \(P(4)=2\) y \(P(10)=576\); la versión en C++ además verifica casos diminutos por fuerza bruta.
Sea \(m=n/2\). Si \(R\) y \(C\) son los números de clases distintas de filas y columnas seleccionables, la enumeración exterior examina
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
pares de clases. Un determinante de tamaño \(k\times k\) cuesta \(O(k^3)\). Para el bloque complementario de tamaño \(r=m-k\), Ryser ingenuo costaría \(O(r2^r)\), pero al agrupar columnas idénticas el espacio de subconjuntos baja aproximadamente a
$$2^b\prod_i (s_i+1),$$
donde \(b<10\) es el tamaño del prefijo enumerado explícitamente y \(s_i\) son los tamaños de las clases de columnas restantes. La etapa de la permanente consume así alrededor de \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) operaciones aritméticas. La memoria es polinómica en el tamaño del bloque actual, más la tabla explícita de subconjuntos de tamaño \(2^b\). Para el caso objetivo \(n=34\), esta compresión es lo que vuelve factible el cálculo exacto.
对偶数 \(n\)，记 \(P(n)\) 为 \(2,3,\dots,n\) 的排列个数，要求任意相邻两项互素。目标是求 \(P(34)\bmod 83456729\)。直接枚举会爆炸，因此实现并不是做暴力搜索，而是先把问题改写成一个平衡二分图中的哈密顿环计数，再用一个“行列式 + permanent + 容斥”的精确公式来求值。
设 \(n=2m\)。把奇数侧定义为
$$U=\{1,3,5,\dots,2m-1\}$$
把偶数侧定义为
$$V=\{2,4,6,\dots,2m\}.$$
再定义一个 \(m\times m\) 的二分图邻接矩阵 \(B\)：
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{否则}. \end{cases}$$
核心思想是：原问题中的排列，可以一一对应到这个增广图里的交替结构。
在 \(2,3,\dots,2m\) 中，一共有 \(m\) 个偶数和 \(m-1\) 个奇数。两个偶数绝不可能在合法排列中相邻，因为它们的最大公约数至少是 \(2\)。因此任何合法排列都必须奇偶交替。又因为偶数比奇数正好多一个，所以奇偶模式根本没有自由度，只能是
$$E-O-E-O-\dots-O-E.$$
这一步很关键：我们真正要数的，不是“任意相邻互素排列”，而是“以偶数开头、以偶数结尾的交替路径”。
数字 \(1\) 与每个偶数都互素，所以把 \(1\) 加到奇数侧后，二分图两侧就平衡了。如果原排列是
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1},$$
那么把 \(1\) 插到两个端点之间，就得到交替环
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
反过来，任何经过全部顶点且包含 \(1\) 的这样的交替环，在删掉 \(1\) 之后，就会变回原问题中的一个合法排列。于是，\(P(2m)\) 恰好等于二分图 \((U,V)\) 中、以顶点 \(1\) 为锚点读取时的哈密顿环数量。
二分图中的一个交替环，可以把边按走环时的奇偶位置分成两组，于是得到两个完美匹配 \(M_1\) 和 \(M_2\)。反过来，两个完美匹配的并，会得到一个覆盖全部顶点的 \(2\)-正则二分子图，因此它一定是若干个偶环的并。
所以，“单个哈密顿环”正是“两个完美匹配合起来只形成一个环，而不是多个不连通环”的特殊情形。permanent 负责无符号地统计完美匹配，determinant 则提供带符号的抵消机制，用来消掉那些分裂成多个环的情况。
把特殊的奇侧顶点记为 \(1\)。对任意满足 \(|I|=|J|=k\) 的集合
$$I\subseteq U\setminus\{1\},\qquad J\subseteq V,$$
记 \(B_{I,J}\) 为选中的 \(k\times k\) 子块，记 \(B_{\bar I,\bar J}\) 为补块，其中 \(\bar I=U\setminus I\) 仍然包含顶点 \(1\)。实现所计算的精确公式是
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
补块上的 permanent 平方，统计的是有序的完美匹配对；determinant 平方提供交错符号，从而把“多个小环的覆盖”抵消掉，最终只保留经过特殊行的哈密顿环。
如果两个可选奇顶点拥有完全相同的邻接集合，那么在 determinant 子块里同时选中它们，就会出现两行完全相同，因此行列式必为 \(0\)。列也是同理。于是 determinant 部分实际上只需要每个“相同支持掩码”的行类、列类各取一个代表元，再乘上这个类的可选数量即可。
但 permanent 部分不能这么直接丢掉重复列，因为重复列在 permanent 中仍然有贡献。实现采用的是按列类分组的 Ryser 公式。若某个列类大小为 \(s\)，而在某个 Ryser 子集中从这一类里选了 \(t\) 列，那么这样的选法共有
$$\binom{s}{t}$$
种，而且每一行的和只依赖于 \(t\)，并不依赖于具体选中了哪几列。
此时 \(m=2\)，因此
$$U=\{1,3\},\qquad V=\{2,4\}.$$
每一对奇偶数都互素，所以
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
把计数锚定在 \(1\) 上之后，只剩下一条非特殊奇行可以进入 determinant 部分。公式分成两类贡献：
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
以及
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
所以
$$P(4)=4-2=2.$$
这两个排列就是 \((2,3,4)\) 与 \((4,3,2)\)。它也是实现中最小的校验点之一。
C++、Python 和 Java 实现首先构造 \(U\) 与 \(V\) 之间的 \(m\times m\) 互素矩阵，并预计算到 \(m\) 为止的二项式系数。随后，它们按照支持掩码对行分组，删去特殊行 \(1\) 的一份拷贝，再对转置矩阵做同样的掩码分组，从而得到列类。
对每个 \(k\)，实现会枚举所有 \(k\) 个行类与 \(k\) 个列类的选择。选中代表元后形成 determinant 子块；如果行列式为 \(0\)，这一支立即剪掉。否则，就把行列式平方、乘上符号 \((-1)^k\)，再乘上对应的类重数。
补块随后送入一个分组的 permanent 例程。determinant 用模 \(83456729\) 下的无分式消元计算。permanent 使用 Ryser 公式，但把支持掩码相同的列合并处理：一小段前缀类用显式 bitmask 子集枚举，剩余的大类则递归地只枚举“这一类选了多少列”。每个这样的选择都会带来一个 \(\binom{s}{t}\) 因子。
最后，程序对每一支累计
$$\text{重数}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
并始终在模 \(83456729\) 下运算。实现中还包含 \(P(4)=2\)、\(P(10)=576\) 等小校验，C++ 版本还会对极小规模做暴力核对。
记 \(m=n/2\)。如果压缩后可选行类和列类的数量分别是 \(R\) 与 \(C\)，那么外层枚举要考察
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
个类对子。一个 \(k\times k\) determinant 的代价是 \(O(k^3)\)。对大小为 \(r=m-k\) 的补块，朴素 Ryser 需要 \(O(r2^r)\)；而按相同列类压缩之后，子集状态空间大致降为
$$2^b\prod_i (s_i+1),$$
其中 \(b<10\) 是显式枚举的前缀大小，\(s_i\) 是剩余列类的大小。因此 permanent 阶段大约消耗 \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) 次算术操作。内存是当前块规模的多项式量级，再加上一张大小为 \(2^b\) 的显式子集表。对于目标 \(n=34\)，正是这种压缩让精确计算变得可行。
Для чётного \(n\) функция \(P(n)\) обозначает число перестановок \(2,3,\dots,n\), в которых каждая соседняя пара взаимно проста. Нужно вычислить \(P(34)\) по модулю \(83456729\). Прямой перебор слишком велик, поэтому реализации переводят задачу в точный подсчёт гамильтоновых циклов в сбалансированном двудольном графе, а затем вычисляют этот счёт с помощью тождества включения-исключения, содержащего определители и перманенты.
Пусть \(n=2m\). Введём нечётную долю
$$U=\{1,3,5,\dots,2m-1\}$$
и чётную долю
$$V=\{2,4,6,\dots,2m\}.$$
Определим двудольную матрицу смежности \(B\) размера \(m\times m\):
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{иначе}. \end{cases}$$
Главная идея состоит в том, что исходные перестановки чисел \(2,\dots,2m\) естественно переписываются как чередующиеся структуры в этом расширенном графе.
Среди чисел \(2,3,\dots,2m\) имеется \(m\) чётных и \(m-1\) нечётных. Два чётных числа не могут стоять рядом в допустимой перестановке, потому что их НОД не меньше \(2\). Значит, любая допустимая перестановка обязана чередовать чётность. Поскольку чётных на одно больше, шаблон полностью фиксирован:
$$E-O-E-O-\dots-O-E.$$
Итак, фактически мы считаем не произвольные перестановки с попарной взаимной простотой соседей, а чередующиеся пути чётное-нечётное с чётными концами.
Число \(1\) взаимно просто с любым чётным числом, поэтому его добавление в нечётную долю балансирует двудольный граф. Если
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
является допустимой перестановкой чисел \(2,\dots,2m\), то вставка \(1\) между концами даёт чередующийся цикл
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
И наоборот, удаление вершины \(1\) из такого цикла возвращает допустимую перестановку. Следовательно, \(P(2m)\) в точности равно числу гамильтоновых циклов в сбалансированном двудольном графе \((U,V)\), считываемых от выделенной вершины \(1\).
Любой чередующийся цикл в двудольном графе можно раскрасить по рёбрам в два попеременных цвета. Тогда он распадается на два совершенных паросочетания \(M_1\) и \(M_2\). Обратно, объединение двух совершенных паросочетаний образует натягивающий \(2\)-регулярный двудольный подграф, то есть дизъюнктное объединение чётных циклов.
Один гамильтонов цикл — это именно тот случай, когда упорядоченная пара \((M_1,M_2)\) создаёт ровно один цикл, а не несколько несвязных. Перманент считает совершенные паросочетания без знаков, а определитель вносит знаки, необходимые для сокращения нежелательных многоцикловых разложений.
Пусть выделенная нечётная вершина равна \(1\). Для множеств \(I\subseteq U\setminus\{1\}\) и \(J\subseteq V\) с \(|I|=|J|=k\) обозначим через \(B_{I,J}\) выбранный блок \(k\times k\), а через \(B_{\bar I,\bar J}\) — дополнительный блок размера \((m-k)\times(m-k)\), где \(\bar I=U\setminus I\) по-прежнему содержит вершину \(1\). Точное тождество, используемое в коде, таково:
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
Квадрат перманента считает упорядоченные пары совершенных паросочетаний на дополнительном блоке. Квадрат определителя создаёт знакопеременную поправку, которая уничтожает покрытия несколькими несвязными циклами и оставляет только гамильтоновы циклы, проходящие через выделенную строку.
Если две выбираемые нечётные вершины имеют одинаковые окрестности, то при одновременном выборе в детерминантный блок возникают две одинаковые строки, а значит определитель равен нулю. То же верно и для одинаковых столбцов. Поэтому в детерминантной части нужен только один представитель от каждого класса строк и столбцов, а число взаимозаменяемых вариантов учитывается отдельным множителем.
В части с перманентом повторяющиеся столбцы не исчезают. Поэтому реализации применяют сгруппированную форму формулы Райзера. Если класс столбцов имеет размер \(s\), а в выбранном подмножестве Райзера из этого класса взято ровно \(t\) столбцов, то число способов равно
$$\binom{s}{t},$$
а суммы по строкам зависят только от \(t\), а не от конкретного выбора столбцов.
Здесь \(m=2\), поэтому
$$U=\{1,3\},\qquad V=\{2,4\}.$$
Каждая нечётно-чётная пара взаимно проста, так что
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
После фиксации вершины \(1\) остаётся только одна невыделенная нечётная строка, которую можно выбирать. Формула даёт два типа вкладов:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
и
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
Следовательно,
$$P(4)=4-2=2,$$
что соответствует двум допустимым перестановкам \((2,3,4)\) и \((4,3,2)\). Это минимальная контрольная точка, используемая реализациями.
Реализации на C++, Python и Java сначала строят матрицу взаимной простоты размера \(m\times m\) между множествами \(U\) и \(V\), а также биномиальные коэффициенты до \(m\). Затем строки группируются по одинаковым маскам опоры, из этих классов убирается одна копия выделенной строки \(1\), а классы столбцов строятся аналогично по транспонированной матрице.
Для каждого \(k\) реализация перебирает все выборы \(k\) классов строк и \(k\) классов столбцов. Из выбранных представителей формируется детерминантный блок; если его определитель равен нулю, ветвь немедленно отбрасывается. Иначе код возводит определитель в квадрат, применяет знак \((-1)^k\) и умножает на кратности классов.
Дополнительный блок затем передаётся в сгруппированную процедуру вычисления перманента. Определитель считается методом бездробного исключения по модулю \(83456729\). Перманент вычисляется по формуле Райзера, но столбцы с одинаковой маской опоры объединяются: небольшой префикс классов перебирается явными битовыми масками, а для оставшихся крупных классов рекурсивно выбирается лишь количество столбцов, взятых из каждого класса. Каждый такой выбор вносит множитель \(\binom{s}{t}\).
В конце код суммирует по всем ветвям выражение
$$\text{кратность}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
по модулю \(83456729\). В реализации присутствуют проверки вроде \(P(4)=2\) и \(P(10)=576\); версия на C++ дополнительно сверяет совсем маленькие случаи полным перебором.
Пусть \(m=n/2\). Если \(R\) и \(C\) — числа различных выбираемых классов строк и столбцов, то внешний перебор рассматривает
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
пар классов. Определитель блока \(k\times k\) стоит \(O(k^3)\). Для дополнительного блока размера \(r=m-k\) наивная формула Райзера требовала бы \(O(r2^r)\), но группировка одинаковых столбцов уменьшает пространство подмножеств примерно до
$$2^b\prod_i (s_i+1),$$
где \(b<10\) — размер явно перебираемого префикса, а \(s_i\) — размеры остальных классов столбцов. Поэтому стадия вычисления перманента тратит примерно \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) арифметических операций. Память остаётся полиномиальной по текущему размеру блока, плюс явная таблица подмножеств размера \(2^b\). Для целевого случая \(n=34\) именно это сжатие делает точный расчёт практичным.
لـ \(n\) زوجي، نرمز بـ \(P(n)\) إلى عدد تبديلات الأعداد \(2,3,\dots,n\) التي يكون فيها كل زوج متجاور متباينًا أوليًا. المطلوب هو حساب \(P(34)\) بترديد \(83456729\). العد المباشر ينمو بسرعة كبيرة جدًا، لذلك تحوّل التطبيقات المسألة إلى عدّ دقيق للدورات الهاملتونية في رسم ثنائي الأجزاء متوازن، ثم تحسب هذا العدد عبر صيغة شمول واستبعاد تعتمد على المحدد و permanent.
لنكتب \(n=2m\). نعرّف الجهة الفردية بـ
$$U=\{1,3,5,\dots,2m-1\}$$
والجهة الزوجية بـ
$$V=\{2,4,6,\dots,2m\}.$$
ثم نعرّف مصفوفة تجاور ثنائية الأجزاء \(B\) من الحجم \(m\times m\) كما يلي:
$$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{otherwise}. \end{cases}$$
الفكرة الأساسية هي أن التبديلات الأصلية على \(2,\dots,2m\) يمكن إعادة صياغتها كبنى متناوبة داخل هذا الرسم الموسّع.
بين الأعداد \(2,3,\dots,2m\) يوجد \(m\) عددًا زوجيًا و\(m-1\) عددًا فرديًا. لا يمكن لعددين زوجيين أن يكونا متجاورين في تبديل صالح، لأن القاسم المشترك الأكبر لهما لا يقل عن \(2\). لذلك يجب أن يكون كل تبديل صالح متناوبًا في التكافؤ. وبما أن عدد الأزواج أكبر بواحد، فإن النمط يصبح مفروضًا بالكامل:
$$E-O-E-O-\dots-O-E.$$
إذًا ما نعدّه فعليًا ليس تبديلات coprime عامة، بل مسارات متناوبة زوجي-فردي يبدأ طرفاها وينتهيان بعدد زوجي.
العدد \(1\) متباين أوليًا مع كل عدد زوجي، ولذلك فإن إضافته إلى الجهة الفردية تجعل الرسم الثنائي متوازنًا. إذا كان
$$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$$
تبديلًا صالحًا للأعداد \(2,\dots,2m\)، فإن إدراج \(1\) بين الطرفين يعطي الدورة المتناوبة
$$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$$
وبالعكس، فإن حذف \(1\) من مثل هذه الدورة يعيد تبديلًا صالحًا. لذلك فإن \(P(2m)\) يساوي تمامًا عدد الدورات الهاملتونية في الرسم الثنائي المتوازن \((U,V)\) عند قراءتها انطلاقًا من الرأس المميز \(1\).
كل دورة متناوبة في رسم ثنائي الأجزاء يمكن تلوين أضلاعها بلونين بالتناوب، وبذلك تنقسم إلى مطابقَتين تامتين \(M_1\) و\(M_2\). وبالعكس، فإن اتحاد مطابقَتين تامتين يعطي رسمًا ثنائيًا ممتدًا من الدرجة \(2\)، وبالتالي فهو اتحاد منفصل لعدة دورات زوجية.
الحالة التي نريدها هي الحالة الخاصة التي ينتج فيها الزوج المرتب \((M_1,M_2)\) دورة واحدة فقط، لا عدة دورات منفصلة. permanent يعدّ المطابقات التامة من غير إشارات، بينما يزوّدنا المحدد بالإشارات اللازمة لإلغاء التفكيكات متعددة الدورات.
ليكن الرأس الفردي المميز هو \(1\). إذا أخذنا مجموعتين \(I\subseteq U\setminus\{1\}\) و\(J\subseteq V\) بحيث \(|I|=|J|=k\)، فإن \(B_{I,J}\) تمثل الكتلة المختارة ذات الحجم \(k\times k\)، و\(B_{\bar I,\bar J}\) تمثل الكتلة المتممة ذات الحجم \((m-k)\times(m-k)\)، حيث إن \(\bar I=U\setminus I\) ما زالت تحتوي الرأس \(1\). الصيغة الدقيقة التي يحسبها التنفيذ هي
$$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$$
مربع permanent يعدّ الأزواج المرتبة من المطابقات التامة على الكتلة المتممة، ومربع المحدد يضيف التصحيح الإشاري الذي يزيل الأغطية المؤلفة من دورات منفصلة متعددة، ولا يُبقي إلا الدورات الهاملتونية المارة عبر الصف المميز.
إذا كان لرأسين فرديين قابلين للاختيار نفس مجموعة الجيران تمامًا، فإن اختيارهما معًا داخل كتلة determinant يعطي صفين متطابقين، وبالتالي يكون المحدد صفرًا. وينطبق الشيء نفسه على الأعمدة المتطابقة. لذا فإن جزء المحدد يحتاج فقط إلى ممثل واحد من كل فئة صفوف ومن كل فئة أعمدة، مع ضرب النتيجة في عدد الاختيارات المتكافئة داخل الفئة.
أما في جزء permanent فلا تختفي الأعمدة المتكررة. لذلك تستخدم التطبيقات صيغة Ryser مجمعة حسب فئات الأعمدة. إذا كان حجم فئة أعمدة ما هو \(s\)، وتم اختيار \(t\) أعمدة منها داخل مجموعة Ryser، فإن عدد الطرق الممكنة هو
$$\binom{s}{t}$$
كما أن مجاميع الصفوف تعتمد فقط على \(t\)، لا على أي الأعمدة المحددة قد اختيرت.
هنا \(m=2\)، ومن ثم
$$U=\{1,3\},\qquad V=\{2,4\}.$$
كل زوج فردي-زوجي متباين أوليًا، لذا
$$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$$
بعد تثبيت العد عند \(1\)، لا يبقى إلا صف فردي غير مميز واحد يمكن اختياره في جزء المحدد. عندئذٍ توجد فئتان من المساهمات:
$$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$$
و
$$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$$
إذًا
$$P(4)=4-2=2,$$
وهذا يطابق التبديلين الصالحين \((2,3,4)\) و\((4,3,2)\). كما أنه أصغر اختبار مرجعي مستخدم في التطبيقات.
تنشئ تطبيقات C++ وPython وJava أولًا مصفوفة coprime بحجم \(m\times m\) بين \(U\) و\(V\)، كما تبني معاملات ثنائية حتى \(m\). بعد ذلك تُجمّع الصفوف ذات أقنعة الدعم المتطابقة، ثم تُزال نسخة واحدة من الصف المميز الموافق لـ \(1\)، وتُبنى فئات الأعمدة بالطريقة نفسها عبر المصفوفة المنقولة.
لكل \(k\)، ينفذ التطبيق جميع اختيارات \(k\) من فئات الصفوف و\(k\) من فئات الأعمدة. تُشكَّل كتلة determinant من الممثلين المختارين؛ فإذا كان المحدد صفرًا، تُهمل تلك الشعبة فورًا. وإلا فإن الكود يربع المحدد، ويطبق الإشارة \((-1)^k\)، ثم يضرب في مضاعفات الفئات.
بعد ذلك تُرسل الكتلة المتممة إلى روتين permanent مجمّع. يُحسب المحدد بأسلوب حذف خالٍ من الكسور تحت الترديد \(83456729\). أما permanent فيُحسب بصيغة Ryser مع تجميع الأعمدة ذات أقنعة الدعم المتساوية: جزء صغير من الفئات يُعالج بتمثيل صريح بالبتات، بينما تُعالج الفئات الكبيرة الباقية تكراريًا باختيار عدد الأعمدة المأخوذة من كل فئة فقط. وكل اختيار من هذا النوع يضيف عاملًا من الشكل \(\binom{s}{t}\).
وفي النهاية، يجمع البرنامج في كل شعبة المقدار
$$\text{multiplicity}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$$
بترديد \(83456729\). كما تتضمن التطبيقات اختبارات صغيرة مثل \(P(4)=2\) و\(P(10)=576\)، بينما تتحقق نسخة C++ أيضًا من الحالات الصغيرة جدًا بالعد المباشر.
إذا كتبنا \(m=n/2\)، ولتكن \(R\) و\(C\) هما عددا فئات الصفوف والأعمدة القابلة للاختيار بعد الضغط، فإن الحلقة الخارجية تفحص
$$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$$
زوجًا من الفئات. كلفة محدد بحجم \(k\times k\) هي \(O(k^3)\). أما الكتلة المتممة ذات الحجم \(r=m-k\)، فكانت صيغة Ryser الساذجة ستكلف \(O(r2^r)\)، لكن تجميع الأعمدة المتطابقة يخفض فضاء المجموعات الفرعية تقريبًا إلى
$$2^b\prod_i (s_i+1),$$
حيث إن \(b<10\) هو حجم المقدمة التي تُعدّ صراحة، و\(s_i\) هي أحجام فئات الأعمدة المتبقية. لذلك تستهلك مرحلة permanent ما يقارب \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) عملية حسابية. استخدام الذاكرة كثير حدود في حجم الكتلة الحالية، مع جدول صريح للمجموعات الفرعية بحجم \(2^b\). وفي الحالة الهدف \(n=34\)، هذا الضغط هو ما يجعل العد الدقيق عمليًا.