We colour the 24 visible stickers of a \(2\times 2\times 2\) Rubik's Cube using \(n\) available colours. Two colourings are considered equivalent if one can be transformed into the other by legal cube moves. The goal is to count the number \(N(n)\) of distinct orbit classes, with the published target \(n=10\) and the useful checkpoint \(N(2)=183\).
This is an orbit-counting problem for the cube move group acting on 24 sticker positions. The implementations evaluate the same Burnside average in two equivalent ways: one by direct enumeration of all reachable cube states, and one by compressing the sum according to the cycle type of the corner permutation.
A legal \(2\times 2\times 2\) state is determined by a permutation of the 8 corner cubies together with a twist value \(o_i\in\{0,1,2\}\) for each corner. The twists are constrained by
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
So the number of reachable states is
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
This is the group over which Burnside's lemma is averaged.
Each group element \(g\in G\) induces a permutation of the 24 stickers. Let \(c(g)\) be the number of cycles in that sticker permutation. A colouring is fixed by \(g\) if and only if every sticker cycle is monochromatic, so the number of fixed colourings is
$$\operatorname{Fix}(g)=n^{c(g)}.$$
Therefore the number of distinct colourings is
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
The entire problem is now reduced to understanding \(c(g)\) efficiently.
Write the corner permutation of \(g\) as disjoint cycles. Consider one such corner cycle of length \(\ell\). If the twists encountered around that cycle are \(t_1,\dots,t_\ell\), define its total twist residue by
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
After following a sticker once around those \(\ell\) corners, the sticker returns to the starting corner but rotated by \(S\). That gives exactly two possibilities:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
If \(S=0\), the 3 local sticker tracks remain separate, giving 3 sticker cycles of length \(\ell\). If \(S=1\) or \(2\), those 3 tracks merge into a single sticker cycle of length \(3\ell\).
Let the corner permutation have cycle type
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
If
$$k=\sum_{r=1}^{8} m_r$$
is the number of corner cycles, then the number of corner permutations with this type is
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
This is the standard formula for the number of permutations with a prescribed cycle decomposition.
For the \(k\) corner cycles, record only their total twist residues \(S_1,\dots,S_k\in\{0,1,2\}\). The global twist rule becomes
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
If the \(j\)-th corner cycle has length \(\ell_j\), then once \(S_j\) is fixed there are \(3^{\ell_j-1}\) actual twist assignments on that cycle. Multiplying over all cycles gives
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
So for a fixed cycle type \(\lambda\) and a fixed residue pattern \(S_1,\dots,S_k\) satisfying the congruence, there are exactly \(A(\lambda)\,3^{8-k}\) group elements with that local behaviour.
The sticker-cycle count contributed by the residue pattern is
$$c=\sum_{j=1}^{k}\phi(S_j).$$
Hence
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
This is the class-compressed form used by the Python and Java implementations. The C++ implementation evaluates the same quantity by enumerating every one of the \(8!\cdot 3^7\) reachable states directly and computing the corresponding 24-sticker cycle count.
Suppose one cycle of the corner permutation has length \(\ell=2\). It moves 2 corners and therefore 6 stickers.
If its total twist residue is \(S=0\), then those 6 stickers split into 3 separate 2-cycles, so this corner cycle contributes \(3\) to \(c(g)\).
If its total twist residue is \(S=1\) or \(2\), then the 3 sticker tracks feed into one another and all 6 stickers lie on a single 6-cycle, so the contribution is \(1\).
This local rule is the heart of the method: once the corner cycle structure and the twist sums modulo 3 are known, the number of fixed colourings is immediately \(n^{c(g)}\).
The C++, Python, and Java implementations all compute the Burnside numerator
$$\sum_{g\in G} n^{c(g)}$$
in big-integer arithmetic and divide by \(8!\cdot 3^7\) at the end.
The C++ implementation explicitly generates all 8! corner permutations and all \(3^7\) valid twist vectors, constructs the induced permutation on 24 stickers, counts its cycle decomposition, and accumulates a histogram by sticker-cycle count. Once the histogram is known, the orbit count is evaluated as
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$$
where \(f_k\) is the number of group elements having exactly \(k\) sticker cycles.
The Python and Java implementations avoid explicit 24-sticker permutations. Instead, they enumerate the partitions of 8, compute how many corner permutations have each cycle type, iterate over the admissible twist-sum residues for those cycles, and add the corresponding term \(n^c\) with multiplicity \(A(\lambda)\,3^{8-k}\). Both viewpoints are mathematically identical.
A practical checkpoint is
$$N(2)=183,$$
which confirms that the group size, twist constraint, and sticker-cycle logic are all consistent before evaluating the target case \(n=10\).
The C++ implementation performs a direct traversal of all
$$8!\cdot 3^7=88{,}179{,}840$$
reachable states. Counting cycles on 24 stickers takes \(O(24)\) per state, so the total work is \(O(8!\cdot 3^7\cdot 24)\), with small extra memory for the global histogram and thread-local accumulators.
The Python and Java implementations are much more compressed. They iterate over the 22 partitions of 8 and, for a partition with \(k\) parts, over at most \(3^k\le 3^8\) residue patterns. Since the cube size is fixed, this is effectively constant-time orbit counting apart from big-integer arithmetic. Memory usage is \(O(1)\) beyond a small collection of partitions and counters.
Wir färben die 24 sichtbaren Sticker eines \(2\times 2\times 2\)-Rubik-Würfels mit \(n\) verfügbaren Farben. Zwei Färbungen gelten als gleich, wenn sie durch legale Würfelzüge ineinander überführt werden können. Gesucht ist also die Anzahl \(N(n)\) der Orbitklassen, wobei für die Aufgabe \(n=10\) relevant ist und \(N(2)=183\) als wichtige Kontrolle dient.
Das ist ein Orbitproblem für die Zuggruppe des Würfels auf 24 Stickerpositionen. Die Implementierungen werten dasselbe Burnside-Mittel auf zwei äquivalente Arten aus: einmal durch vollständige Enumeration aller erreichbaren Zustände und einmal durch eine Verdichtung nach dem Zykeltyp der Eckenpermutation.
Ein legaler \(2\times 2\times 2\)-Zustand wird durch eine Permutation der 8 Ecksteine und eine Verdrehung \(o_i\in\{0,1,2\}\) für jede Ecke bestimmt. Diese Verdrehungen sind nicht unabhängig, sondern erfüllen
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
Daher hat die Gruppe die Größe
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
Über genau diese Gruppe mittelt Burnside.
Jedes Gruppenelement \(g\in G\) induziert eine Permutation der 24 Sticker. Sei \(c(g)\) die Anzahl ihrer Zyklen. Eine Färbung bleibt genau dann unter \(g\) fest, wenn jeder Stickerzyklus einfarbig ist. Also gilt
$$\operatorname{Fix}(g)=n^{c(g)}.$$
Damit folgt
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
Somit muss man nur noch \(c(g)\) effizient bestimmen.
Schreibe die Eckenpermutation von \(g\) als Produkt disjunkter Zyklen. Betrachte einen Eckzyklus der Länge \(\ell\). Wenn die entlang dieses Zyklus auftretenden Verdrehungen \(t_1,\dots,t_\ell\) sind, definieren wir die Gesamtverdrehung
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
Verfolgt man einen Sticker einmal rund um diese \(\ell\) Ecken, dann kehrt er in dieselbe Ecke zurück, aber um \(S\) verdreht. Daraus ergeben sich genau zwei Fälle:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
Für \(S=0\) bleiben die 3 lokalen Stickerbahnen getrennt und erzeugen 3 Stickerzyklen der Länge \(\ell\). Für \(S=1\) oder \(2\) verschmelzen diese 3 Bahnen zu genau einem Stickerzyklus der Länge \(3\ell\).
Sei der Zykeltyp der Eckenpermutation
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
Mit
$$k=\sum_{r=1}^{8} m_r$$
als Anzahl der Eckzyklen ist die Anzahl solcher Permutationen
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
Das ist die Standardformel für Permutationen mit vorgeschriebener Zykelstruktur.
Für die \(k\) Eckzyklen betrachtet man nur noch ihre Summenreste \(S_1,\dots,S_k\in\{0,1,2\}\). Die globale Verdrehungsbedingung wird zu
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
Hat der \(j\)-te Eckzyklus Länge \(\ell_j\), dann gibt es bei festem \(S_j\) genau \(3^{\ell_j-1}\) konkrete Verdrehungsbelegungen auf diesem Zyklus. Über alle Zyklen multipliziert ergibt das
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
Für festen Zykeltyp \(\lambda\) und festes Residuenmuster \(S_1,\dots,S_k\), das die Kongruenz erfüllt, existieren also genau \(A(\lambda)\,3^{8-k}\) Gruppenelemente mit diesem lokalen Verhalten.
Die Zahl der Stickerzyklen des Residuenmusters ist
$$c=\sum_{j=1}^{k}\phi(S_j).$$
Damit erhält man
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
Genau diese verdichtete Form benutzen die Python- und Java-Implementierungen. Die C++-Implementierung berechnet denselben Ausdruck, indem sie alle \(8!\cdot 3^7\) erreichbaren Zustände direkt aufzählt und für jeden Zustand die Zykluszahl der 24 Sticker bestimmt.
Angenommen, ein Zyklus der Eckenpermutation hat Länge \(\ell=2\). Dann bewegt er 2 Ecken und damit 6 Sticker.
Falls seine Gesamtverdrehung \(S=0\) ist, zerfallen diese 6 Sticker in 3 getrennte 2-Zyklen. Der Beitrag dieses Eckzyklus zu \(c(g)\) ist also \(3\).
Falls \(S=1\) oder \(2\) gilt, gehen die 3 Stickerbahnen ineinander über, und alle 6 Sticker bilden zusammen einen einzigen 6-Zyklus. Dann ist der Beitrag gleich \(1\).
Genau diese lokale Regel macht die Verdichtung möglich: Sind Zykelstruktur und Verdrehungssummen modulo 3 bekannt, so ist die Zahl fixer Färbungen sofort \(n^{c(g)}\).
Die C++, Python- und Java-Implementierungen berechnen alle den Burnside-Zähler
$$\sum_{g\in G} n^{c(g)}$$
mit Ganzzahlarithmetik beliebiger Genauigkeit und teilen erst am Ende durch \(8!\cdot 3^7\).
Die C++-Implementierung erzeugt explizit alle 8! Eckenpermutationen und alle \(3^7\) gültigen Verdrehungsvektoren, konstruiert daraus die induzierte Permutation auf 24 Stickern, zählt deren Zyklen und sammelt ein Histogramm nach Stickerzykluszahl. Danach wird
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k$$
ausgewertet, wobei \(f_k\) die Anzahl der Gruppenelemente mit genau \(k\) Stickerzyklen ist.
Die Python- und Java-Implementierungen vermeiden die explizite 24-Sticker-Permutation. Stattdessen durchlaufen sie die Partitionen von 8, berechnen die Anzahl der Eckenpermutationen zu jedem Zykeltyp, iterieren über die zulässigen Verdrehungssummen der Zyklen und addieren jeweils den Term \(n^c\) mit der Multiplizität \(A(\lambda)\,3^{8-k}\). Beide Sichtweisen sind mathematisch identisch.
Eine wichtige Kontrolle ist
$$N(2)=183,$$
denn damit sieht man, dass Gruppengröße, Verdrehungsbedingung und Stickerzykluslogik korrekt zusammenspielen, bevor der Zielwert für \(n=10\) berechnet wird.
Die C++-Implementierung traversiert direkt alle
$$8!\cdot 3^7=88{,}179{,}840$$
erreichbaren Zustände. Das Zählen der Zyklen auf 24 Stickern kostet \(O(24)\) pro Zustand, also insgesamt \(O(8!\cdot 3^7\cdot 24)\) Zeit. Der zusätzliche Speicher bleibt klein und beschränkt sich im Wesentlichen auf das Histogramm und threadlokale Zähler.
Die Python- und Java-Implementierungen sind deutlich kompakter. Sie iterieren nur über die 22 Partitionen von 8 und für eine Partition mit \(k\) Teilen über höchstens \(3^k\le 3^8\) Residuenmuster. Da die Würfelgröße fest ist, ist das praktisch konstante Laufzeit abgesehen von der Big-Integer-Arithmetik. Der Speicherbedarf ist \(O(1)\) abseits einer kleinen Sammlung von Partitionen und Zählern.
\(2\times 2\times 2\) Rubik küpün görünen 24 etiketini \(n\) farklı renkle boyuyoruz. İki boyama, yasal küp hamleleriyle birbirine dönüştürülebiliyorsa eşdeğer kabul edilir. Amaç, bu eşdeğerlik sınıflarının sayısı olan \(N(n)\) değerini bulmaktır. Sorudaki hedef \(n=10\) iken, \(N(2)=183\) değeri önemli bir kontrol noktasıdır.
Bu, küp hareket grubunun 24 etiket konumu üzerindeki etkisi altında bir yörünge sayma problemidir. Uygulamalar aynı Burnside ortalamasını iki eşdeğer biçimde hesaplar: biri tüm erişilebilir küp durumlarını doğrudan dolaşır, diğeri ise köşe permütasyonunun çevrim tipine göre toplamı sıkıştırır.
Geçerli bir \(2\times 2\times 2\) durum, 8 köşe küpçüğünün bir permütasyonu ve her köşe için \(o_i\in\{0,1,2\}\) burulma değeriyle belirlenir. Bu burulmalar bağımsız değildir; şu koşulu sağlamalıdır:
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
Dolayısıyla grubun büyüklüğü
$$|G|=8!\cdot 3^7=88{,}179{,}840$$
olur. Burnside ortalaması tam olarak bu grup üzerinde alınır.
Her \(g\in G\) elemanı 24 etiket üzerinde bir permütasyon oluşturur. Bu permütasyondaki çevrim sayısına \(c(g)\) diyelim. Bir boyama ancak ve ancak her etiket çevrimi tek renkliyse \(g\) tarafından sabit bırakılır. Bu yüzden sabit kalan boyama sayısı
$$\operatorname{Fix}(g)=n^{c(g)}$$
olur. Böylece
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}$$
elde edilir. Problem artık \(c(g)\)'yi verimli biçimde bulmaya indirgenmiştir.
\(g\)'nin köşe permütasyonunu ayrık çevrimler halinde yazalım. Uzunluğu \(\ell\) olan bir köşe çevrimi düşünelim. Bu çevrim boyunca görülen burulmalar \(t_1,\dots,t_\ell\) ise toplam burulma kalanı
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}$$
olarak tanımlanır. Bir etiketi bu \(\ell\) köşe boyunca bir tur izlediğimizde, etiket başlangıç köşesine geri döner ama \(S\) kadar dönmüş olur. Bundan tam iki durum çıkar:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
\(S=0\) ise 3 yerel etiket izi birbirinden ayrık kalır ve uzunluğu \(\ell\) olan 3 etiket çevrimi üretir. \(S=1\) veya \(2\) ise bu 3 iz birleşerek uzunluğu \(3\ell\) olan tek bir etiket çevrimi oluşturur.
Köşe permütasyonunun çevrim tipi
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8$$
olsun. Köşe çevrimlerinin sayısı
$$k=\sum_{r=1}^{8} m_r$$
ise, bu tipe sahip permütasyon sayısı
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}$$
şeklindedir. Bu, verilen çevrim ayrışımına sahip permütasyonların klasik sayım formülüdür.
\(k\) köşe çevriminin her biri için yalnızca toplam burulma kalanı \(S_1,\dots,S_k\in\{0,1,2\}\) önemlidir. Genel burulma kuralı
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}$$
şeklini alır. \(j\). köşe çevriminin uzunluğu \(\ell_j\) ise, \(S_j\) sabitken bu çevrim üzerindeki gerçek burulma ataması sayısı \(3^{\ell_j-1}\) olur. Tüm çevrimler çarpılınca
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}$$
elde edilir. Yani sabit bir \(\lambda\) çevrim tipi ve kongruans koşulunu sağlayan sabit bir \(S_1,\dots,S_k\) örüntüsü için tam olarak \(A(\lambda)\,3^{8-k}\) grup elemanı vardır.
Bu kalıntı örüntüsünün ürettiği etiket çevrimi sayısı
$$c=\sum_{j=1}^{k}\phi(S_j)$$
olur. Dolayısıyla
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
Python ve Java uygulamalarının kullandığı sıkıştırılmış form budur. C++ uygulaması ise aynı değeri, \(8!\cdot 3^7\) erişilebilir durumun tamamını doğrudan dolaşıp her biri için 24 etiket üzerindeki çevrim sayısını ölçerek hesaplar.
Köşe permütasyonundaki bir çevrimin uzunluğunun \(\ell=2\) olduğunu düşünelim. Bu çevrim 2 köşeyi ve dolayısıyla 6 etiketi hareket ettirir.
Toplam burulma kalanı \(S=0\) ise, bu 6 etiket 3 ayrı 2-çevrime ayrılır. Yani bu köşe çevriminin \(c(g)\)'ye katkısı \(3\) olur.
Toplam burulma kalanı \(S=1\) veya \(2\) ise, 3 etiket izi birbirine bağlanır ve 6 etiket tek bir 6-çevrim oluşturur. Bu durumda katkı \(1\)'dir.
Yöntemin özü tam olarak bu yerel kuraldır: köşe çevrim yapısı ve mod 3 burulma toplamları bilindiğinde, sabit kalan boyama sayısı hemen \(n^{c(g)}\) olur.
C++, Python ve Java uygulamalarının hepsi Burnside payını
$$\sum_{g\in G} n^{c(g)}$$
büyük tamsayı aritmetiğiyle hesaplar ve en sonunda \(8!\cdot 3^7\)'ye böler.
C++ uygulaması tüm 8! köşe permütasyonlarını ve tüm \(3^7\) geçerli burulma vektörlerini açıkça üretir, bunlardan 24 etiket üzerindeki indüklenen permütasyonu kurar, çevrim ayrışımını sayar ve etiket çevrimi sayısına göre bir histogram biriktirir. Histogram hazır olduğunda
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k$$
hesaplanır; burada \(f_k\), tam olarak \(k\) etiket çevrimi üreten grup elemanı sayısıdır.
Python ve Java uygulamaları açık 24-etiket permütasyonları kurmaz. Bunun yerine 8'in tamsayı bölünmelerini dolaşır, her çevrim tipi için köşe permütasyonu sayısını hesaplar, o çevrimler için izin verilen burulma-toplamı kalıntılarını gezer ve \(A(\lambda)\,3^{8-k}\) çokluğu ile \(n^c\) terimini toplar. İki bakış açısı matematiksel olarak aynıdır.
Önemli bir doğrulama değeri
$$N(2)=183$$
olup, bu sonuç hedef durum \(n=10\) hesaplanmadan önce grup büyüklüğünün, burulma kısıtının ve etiket çevrimi mantığının doğru olduğunu gösterir.
C++ uygulaması doğrudan
$$8!\cdot 3^7=88{,}179{,}840$$
erişilebilir durumun tamamını gezer. 24 etiket üzerinde çevrim saymak durum başına \(O(24)\) maliyetlidir; dolayısıyla toplam zaman \(O(8!\cdot 3^7\cdot 24)\) olur. Ek bellek ihtiyacı ise global histogram ve iş parçacığı yerel sayaçları dışında küçüktür.
Python ve Java uygulamaları çok daha sıkıştırılmıştır. Bunlar yalnızca 8'in 22 bölünmesini ve \(k\) parçalı bir bölünme için en fazla \(3^k\le 3^8\) kalıntı örüntüsünü dolaşır. Küp boyutu sabit olduğundan, büyük tamsayı üs alma ve toplama maliyetleri dışında çalışma süresi pratikte sabittir. Bölünmeler ve sayaçlar için tutulan küçük veri dışında bellek kullanımı \(O(1)\)'dir.
Coloreamos las 24 pegatinas visibles de un cubo de Rubik \(2\times 2\times 2\) con \(n\) colores disponibles. Dos coloraciones se consideran equivalentes si una puede transformarse en la otra mediante movimientos legales del cubo. El objetivo es contar el número \(N(n)\) de clases de órbita; en este problema interesa \(n=10\), y el valor \(N(2)=183\) sirve como comprobación importante.
Se trata de un problema de conteo de órbitas para la acción del grupo de movimientos del cubo sobre 24 posiciones de pegatinas. Las implementaciones evalúan el mismo promedio de Burnside de dos maneras equivalentes: una mediante enumeración directa de todos los estados alcanzables, y otra comprimiendo la suma según el tipo de ciclos de la permutación de esquinas.
Un estado legal de un cubo \(2\times 2\times 2\) queda determinado por una permutación de los 8 cubitos de esquina y por un giro \(o_i\in\{0,1,2\}\) en cada esquina. Esos giros no son independientes, sino que cumplen
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
Por tanto, el tamaño del grupo es
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
Ese es precisamente el grupo sobre el que se promedia en Burnside.
Cada elemento \(g\in G\) induce una permutación sobre las 24 pegatinas. Sea \(c(g)\) el número de ciclos de esa permutación. Una coloración queda fija por \(g\) exactamente cuando cada ciclo de pegatinas es monocromático, así que el número de coloraciones fijas es
$$\operatorname{Fix}(g)=n^{c(g)}.$$
En consecuencia,
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
El problema queda reducido a calcular \(c(g)\) de forma eficiente.
Escribimos la permutación de esquinas de \(g\) como producto de ciclos disjuntos. Consideremos un ciclo de esquinas de longitud \(\ell\). Si los giros encontrados a lo largo de ese ciclo son \(t_1,\dots,t_\ell\), definimos el residuo total de giro por
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
Al seguir una pegatina una vuelta completa por esas \(\ell\) esquinas, la pegatina vuelve a la esquina inicial pero rotada en \(S\). De ahí salen exactamente dos casos:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
Si \(S=0\), las 3 trayectorias locales de pegatinas permanecen separadas y producen 3 ciclos de longitud \(\ell\). Si \(S=1\) o \(2\), esas 3 trayectorias se fusionan en un único ciclo de longitud \(3\ell\).
Sea el tipo de ciclo de la permutación de esquinas
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
Si
$$k=\sum_{r=1}^{8} m_r$$
es el número de ciclos de esquinas, entonces el número de permutaciones con este tipo es
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
Esta es la fórmula clásica para contar permutaciones con descomposición cíclica prescrita.
Para los \(k\) ciclos de esquinas solo importan sus residuos totales \(S_1,\dots,S_k\in\{0,1,2\}\). La restricción global de giro se convierte en
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
Si el \(j\)-ésimo ciclo de esquinas tiene longitud \(\ell_j\), entonces, fijado \(S_j\), existen \(3^{\ell_j-1}\) asignaciones concretas de giro sobre ese ciclo. Multiplicando sobre todos los ciclos se obtiene
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
Por tanto, para un tipo de ciclo fijo \(\lambda\) y un patrón fijo \(S_1,\dots,S_k\) que cumpla la congruencia, hay exactamente \(A(\lambda)\,3^{8-k}\) elementos del grupo con ese comportamiento local.
El número de ciclos de pegatinas aportado por ese patrón de residuos es
$$c=\sum_{j=1}^{k}\phi(S_j).$$
Así,
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
Esta es la forma comprimida que utilizan las implementaciones en Python y Java. La implementación en C++ evalúa exactamente la misma cantidad recorriendo directamente los \(8!\cdot 3^7\) estados alcanzables y midiendo para cada uno el número de ciclos sobre las 24 pegatinas.
Supongamos que uno de los ciclos de la permutación de esquinas tiene longitud \(\ell=2\). Entonces mueve 2 esquinas y, por tanto, 6 pegatinas.
Si su residuo total de giro es \(S=0\), esas 6 pegatinas se separan en 3 ciclos distintos de longitud 2. La contribución de este ciclo de esquinas a \(c(g)\) es, por tanto, \(3\).
Si su residuo total de giro es \(S=1\) o \(2\), las 3 trayectorias de pegatinas se encadenan y las 6 pegatinas forman un único ciclo de longitud 6. En ese caso la contribución es \(1\).
Esta regla local es la clave de todo el método: una vez conocidos la estructura cíclica de las esquinas y las sumas de giro módulo 3, el número de coloraciones fijas es inmediatamente \(n^{c(g)}\).
Las implementaciones en C++, Python y Java calculan todas el numerador de Burnside
$$\sum_{g\in G} n^{c(g)}$$
con aritmética de enteros grandes y solo al final dividen por \(8!\cdot 3^7\).
La implementación en C++ genera explícitamente las 8! permutaciones de esquinas y los \(3^7\) vectores de giro válidos, construye la permutación inducida sobre 24 pegatinas, cuenta su descomposición en ciclos y acumula un histograma según el número de ciclos. Una vez construido el histograma, evalúa
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$$
donde \(f_k\) es el número de elementos del grupo que tienen exactamente \(k\) ciclos de pegatinas.
Las implementaciones en Python y Java evitan construir permutaciones explícitas sobre 24 pegatinas. En su lugar, enumeran las particiones de 8, calculan cuántas permutaciones de esquinas corresponden a cada tipo de ciclo, recorren los residuos admisibles de suma de giro para esos ciclos y añaden el término \(n^c\) con multiplicidad \(A(\lambda)\,3^{8-k}\). Ambas estrategias son matemáticamente equivalentes.
Una comprobación práctica es
$$N(2)=183,$$
lo que confirma que el tamaño del grupo, la restricción de giros y la lógica de ciclos de pegatinas son coherentes antes de evaluar el caso objetivo \(n=10\).
La implementación en C++ recorre directamente los
$$8!\cdot 3^7=88{,}179{,}840$$
estados alcanzables. Contar ciclos sobre 24 pegatinas cuesta \(O(24)\) por estado, de modo que el trabajo total es \(O(8!\cdot 3^7\cdot 24)\). La memoria adicional es pequeña y se limita esencialmente al histograma global y a acumuladores locales por hilo.
Las implementaciones en Python y Java están mucho más comprimidas. Recorren solo las 22 particiones de 8 y, para una partición con \(k\) partes, a lo sumo \(3^k\le 3^8\) patrones de residuos. Como el tamaño del cubo es fijo, esto equivale a tiempo constante salvo por el coste de la aritmética de enteros grandes. El uso de memoria es \(O(1)\) más allá de un pequeño conjunto de particiones y contadores.
我们用 \(n\) 种可用颜色给 \(2\times 2\times 2\) 魔方的 24 个可见贴纸着色。如果两种着色能够通过合法的魔方转动互相变换，就把它们视为同一种。本题要求的是不同等价类的个数 \(N(n)\)。题目的目标参数是 \(n=10\)，而 \(N(2)=183\) 是一个非常有用的校验值。
这是一个典型的群作用下的轨道计数问题。魔方的机械动作群作用在 24 个贴纸位置上。实现中实际上计算的是同一个 Burnside 平均值，只是有两种等价的求法：一种直接枚举所有可达状态，另一种按角块置换的循环类型压缩求和。
一个合法的 \(2\times 2\times 2\) 魔方状态，可以由 8 个角块的一个置换以及每个角块的扭转值 \(o_i\in\{0,1,2\}\) 唯一确定。角块扭转不是独立的，它们满足约束
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
因此状态总数，也就是这里要平均的群大小，为
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
这正是 Burnside 引理中的分母。
每个群元素 \(g\in G\) 都会在 24 个贴纸上诱导出一个置换。设这个贴纸置换的循环个数为 \(c(g)\)。如果一种着色在 \(g\) 的作用下保持不变，那么同一个贴纸循环中的所有位置必须是同色，所以固定着色数恰好是
$$\operatorname{Fix}(g)=n^{c(g)}.$$
于是不同着色等价类的数目满足
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
因此关键只剩下一件事：怎样高效地求出每个群元素对应的 \(c(g)\)。
把群元素 \(g\) 的角块置换写成若干个互不相交的循环。考虑其中一个长度为 \(\ell\) 的角块循环。设沿着这个循环依次遇到的角块扭转为 \(t_1,\dots,t_\ell\)，定义它的总扭转余数
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
把某一张贴纸沿着这 \(\ell\) 个角块跟踪一整圈之后，它会回到起始角块，但相对方向会额外旋转 \(S\)。因此只会出现两种情况：
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
如果 \(S=0\)，说明 3 条局部贴纸轨道彼此独立，于是这个角块循环在贴纸层面贡献 3 个长度为 \(\ell\) 的循环。若 \(S=1\) 或 \(2\)，3 条轨道会首尾相接，合并成 1 个长度为 \(3\ell\) 的贴纸循环。
设角块置换的循环类型为
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
记角块循环总数为
$$k=\sum_{r=1}^{8} m_r.$$
那么具有这种循环类型的角块置换个数是
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
这就是“给定循环分解的置换有多少个”的标准公式，也是压缩计数的第一部分。
对于这 \(k\) 个角块循环，真正影响贴纸循环数的不是每个角块的具体扭转，而只是每个循环的总扭转余数 \(S_1,\dots,S_k\in\{0,1,2\}\)。整体扭转约束等价于
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
如果第 \(j\) 个角块循环长度为 \(\ell_j\)，那么在固定 \(S_j\) 的前提下，这个循环内部有 \(3^{\ell_j-1}\) 种具体扭转赋值。对所有循环相乘可得
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
所以，对一个固定的循环类型 \(\lambda\) 和一个满足同余条件的固定余数模式 \(S_1,\dots,S_k\)，恰好有 \(A(\lambda)\,3^{8-k}\) 个群元素对应这种局部结构。
该余数模式对应的贴纸循环总数为
$$c=\sum_{j=1}^{k}\phi(S_j).$$
于是可以得到压缩公式
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
这正是 Python 和 Java 实现所使用的数学形式。C++ 实现并没有写成这种压缩求和，而是直接把全部 \(8!\cdot 3^7\) 个可达状态都枚举出来，逐个构造其 24 贴纸置换，再统计 \(c(g)\)。两者算的是完全同一个 Burnside 平均值。
假设角块置换中有一个长度 \(\ell=2\) 的循环。它会移动 2 个角块，因此涉及 6 张贴纸。
如果这个循环的总扭转余数 \(S=0\)，那么这 6 张贴纸会分裂成 3 个彼此独立的 2-循环，所以它对 \(c(g)\) 的贡献是 \(3\)。
如果 \(S=1\) 或 \(2\)，那么原来的 3 条贴纸轨道会连接起来，6 张贴纸合并成 1 个长度为 6 的循环，因此贡献变成 \(1\)。
这个局部规则就是整套方法成立的核心原因：只要知道角块循环结构以及各循环的扭转和模 3 的值，固定着色数就立刻是 \(n^{c(g)}\)。
C++、Python 和 Java 三个实现本质上都在计算 Burnside 分子
$$\sum_{g\in G} n^{c(g)}$$
并在最后除以 \(8!\cdot 3^7\)。由于结果很大，三个实现都使用了任意精度整数运算。
C++ 实现显式生成全部 8! 个角块置换和全部 \(3^7\) 个合法扭转向量，把每个状态转成 24 个贴纸上的置换，统计这个置换的循环个数，然后按“贴纸循环数等于多少”建立频数直方图。直方图得到以后，再计算
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$$
其中 \(f_k\) 表示恰好产生 \(k\) 个贴纸循环的群元素数量。
Python 和 Java 实现则不显式构造 24 贴纸置换。它们先枚举 8 的整数分拆，求出每种循环类型的角块置换个数，再遍历满足总扭转条件的循环余数模式，并按重数 \(A(\lambda)\,3^{8-k}\) 累加对应的 \(n^c\) 项。这种做法把大量等价结构合并了，但数学内容与直接枚举完全一致。
实现中的一个关键校验是
$$N(2)=183,$$
这个结果说明群大小、角块扭转约束和贴纸循环规则彼此吻合，因此再去计算目标情况 \(n=10\) 就是可信的。
C++ 实现直接遍历全部
$$8!\cdot 3^7=88{,}179{,}840$$
个可达状态。对每个状态，在 24 张贴纸上做循环分解的代价是 \(O(24)\)，因此总时间复杂度是 \(O(8!\cdot 3^7\cdot 24)\)。额外空间很小，主要是一个按贴纸循环数统计的直方图以及少量线程局部计数器。
Python 和 Java 实现则压缩得多。它们只遍历 8 的 22 个整数分拆，而一个有 \(k\) 个部分的分拆最多只需要检查 \(3^k\le 3^8\) 种循环余数模式。由于魔方大小固定，这在实践中可以看作常数时间，真正增长的主要是大整数幂和大整数加法的成本。除少量分拆和计数器外，空间复杂度基本是 \(O(1)\)。
Мы раскрашиваем 24 видимые наклейки кубика Рубика \(2\times 2\times 2\) с помощью \(n\) доступных цветов. Две раскраски считаются одинаковыми, если одну можно получить из другой допустимой последовательностью поворотов кубика. Нужно найти число \(N(n)\) различных классов эквивалентности. В задаче требуется случай \(n=10\), а значение \(N(2)=183\) служит важной проверкой.
Это задача на подсчет орбит действия группы ходов кубика на 24 позициях наклеек. Реализации вычисляют одно и то же среднее по лемме Бёрнсайда двумя эквивалентными способами: либо прямым перебором всех достижимых состояний, либо сжатием суммы по типу циклов перестановки углов.
Любое допустимое состояние кубика \(2\times 2\times 2\) задается перестановкой 8 угловых кубиков и ориентацией \(o_i\in\{0,1,2\}\) для каждого угла. Эти ориентации не независимы, а подчиняются условию
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
Поэтому размер группы равен
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
Именно по этой группе берется среднее в лемме Бёрнсайда.
Каждый элемент \(g\in G\) индуцирует перестановку 24 наклеек. Обозначим через \(c(g)\) число циклов этой перестановки. Раскраска фиксируется элементом \(g\) тогда и только тогда, когда каждая орбита наклеек одноцветна, поэтому число фиксированных раскрасок равно
$$\operatorname{Fix}(g)=n^{c(g)}.$$
Следовательно,
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
Значит, задача сводится к эффективному вычислению \(c(g)\).
Разложим перестановку углов элемента \(g\) на непересекающиеся циклы. Рассмотрим один цикл углов длины \(\ell\). Если по этому циклу встречаются ориентации \(t_1,\dots,t_\ell\), введем суммарный остаток ориентации
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
Если проследить одну наклейку по полному обходу этих \(\ell\) углов, она вернется в исходный угол, но будет повернута на \(S\). Отсюда возникают ровно два случая:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
При \(S=0\) три локальные дорожки наклеек остаются раздельными и дают 3 цикла наклеек длины \(\ell\). При \(S=1\) или \(2\) эти три дорожки сливаются в один цикл наклеек длины \(3\ell\).
Пусть тип циклов перестановки углов имеет вид
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
Если число циклов углов равно
$$k=\sum_{r=1}^{8} m_r,$$
то число перестановок такого типа равно
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
Это стандартная формула для числа перестановок с заданной циклической структурой.
Для \(k\) циклов углов важны только суммарные остатки \(S_1,\dots,S_k\in\{0,1,2\}\). Глобальное условие на ориентации переписывается как
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
Если длина \(j\)-го цикла углов равна \(\ell_j\), то при фиксированном \(S_j\) существует ровно \(3^{\ell_j-1}\) конкретных распределений ориентаций на этом цикле. Перемножая по всем циклам, получаем
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
Значит, для фиксированного типа \(\lambda\) и фиксированного набора остатков \(S_1,\dots,S_k\), удовлетворяющего сравнению, существует точно \(A(\lambda)\,3^{8-k}\) элементов группы с таким локальным поведением.
Число циклов наклеек, соответствующее этому набору остатков, равно
$$c=\sum_{j=1}^{k}\phi(S_j).$$
Поэтому
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
Именно этой сжатой формой пользуются реализации на Python и Java. Реализация на C++ вычисляет ту же величину напрямую: перебирает все \(8!\cdot 3^7\) достижимых состояний и для каждого определяет число циклов индуцированной перестановки 24 наклеек.
Предположим, что один из циклов перестановки углов имеет длину \(\ell=2\). Тогда он перемещает 2 угла и, следовательно, 6 наклеек.
Если его суммарный остаток ориентации \(S=0\), то эти 6 наклеек распадаются на 3 независимых 2-цикла. Значит, вклад этого цикла углов в \(c(g)\) равен \(3\).
Если \(S=1\) или \(2\), то три локальные дорожки склеиваются, и все 6 наклеек образуют один 6-цикл. В этом случае вклад равен \(1\).
Именно это локальное правило лежит в основе всего метода: как только известны структура циклов углов и суммы ориентаций по модулю 3, число фиксированных раскрасок сразу равно \(n^{c(g)}\).
Реализации на C++, Python и Java вычисляют один и тот же числитель Бёрнсайда
$$\sum_{g\in G} n^{c(g)}$$
с использованием арифметики больших целых чисел, а затем делят результат на \(8!\cdot 3^7\).
Реализация на C++ явно генерирует все 8! перестановок углов и все \(3^7\) допустимых векторов ориентаций, строит индуцированную перестановку 24 наклеек, считает ее циклы и накапливает гистограмму по числу циклов наклеек. После этого вычисляется
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$$
где \(f_k\) обозначает число элементов группы, имеющих ровно \(k\) циклов наклеек.
Реализации на Python и Java не строят явные перестановки 24 наклеек. Они перечисляют разбиения числа 8, вычисляют, сколько перестановок углов соответствует каждому типу циклов, проходят по допустимым остаткам сумм ориентаций и прибавляют член \(n^c\) с кратностью \(A(\lambda)\,3^{8-k}\). Это другой способ организовать тот же самый расчет.
Важная контрольная точка имеет вид
$$N(2)=183,$$
и она показывает, что размер группы, ограничение на ориентации и правило подсчета циклов наклеек согласованы до вычисления целевого значения при \(n=10\).
Реализация на C++ напрямую перебирает все
$$8!\cdot 3^7=88{,}179{,}840$$
достижимых состояний. Подсчет циклов на 24 наклейках занимает \(O(24)\) на состояние, поэтому общая трудоемкость равна \(O(8!\cdot 3^7\cdot 24)\). Дополнительная память мала и в основном ограничивается гистограммой и локальными счетчиками потоков.
Реализации на Python и Java значительно более сжаты. Они перебирают только 22 разбиения числа 8 и, для разбиения с \(k\) частями, не более \(3^k\le 3^8\) шаблонов остатков. Поскольку размер кубика фиксирован, это фактически постоянное время, если не считать стоимость больших целых степеней и сложений. Память имеет порядок \(O(1)\) сверх небольшого набора разбиений и счетчиков.
نلوّن الملصقات الظاهرة وعددها 24 في مكعب روبيك \(2\times 2\times 2\) باستخدام \(n\) ألوان متاحة. ويُعدّ تلوينان متكافئين إذا أمكن تحويل أحدهما إلى الآخر بحركات قانونية للمكعب. المطلوب هو إيجاد عدد أصناف التكافؤ \(N(n)\). في المسألة الفعلية نحتاج إلى الحالة \(n=10\)، بينما تمثل القيمة \(N(2)=183\) نقطة تحقق مهمة.
هذه مسألة عدّ مدارات تحت تأثير زمرة حركات المكعب على مواضع الملصقات الـ24. والتنفيذات المختلفة تحسب المتوسط نفسه الوارد في لمّة Burnside بطريقتين متكافئتين: إما بالتعداد المباشر لجميع الحالات الممكنة، أو بضغط المجموع وفق نوع الدورات في تبديل الزوايا.
أي حالة قانونية لمكعب \(2\times 2\times 2\) تتحدد بتبديل الزوايا الثماني وبقيمة اتجاه \(o_i\in\{0,1,2\}\) لكل زاوية. وهذه الاتجاهات ليست مستقلة، بل تحقق الشرط
$$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$$
ومن ثم يكون حجم الزمرة
$$|G|=8!\cdot 3^7=88{,}179{,}840.$$
وهذه هي الزمرة التي نأخذ عليها متوسط Burnside.
كل عنصر \(g\in G\) يولّد تبديلًا على الملصقات الـ24. ولتكن \(c(g)\) هي عدد الدورات في هذا التبديل. يكون التلوين ثابتًا تحت \(g\) إذا وفقط إذا كانت كل دورة من دورات الملصقات ذات لون واحد، ولذلك فإن عدد التلوينات الثابتة هو
$$\operatorname{Fix}(g)=n^{c(g)}.$$
إذن
$$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$$
وهكذا تنحصر المسألة في حساب \(c(g)\) بكفاءة.
نكتب تبديل الزوايا الموافق للعنصر \(g\) على صورة دورات منفصلة. ولننظر إلى دورة زوايا طولها \(\ell\). إذا كانت قيم الاتجاهات على امتداد هذه الدورة هي \(t_1,\dots,t_\ell\)، فنعرف الباقي الكلي للدوران بـ
$$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$$
عند تتبع ملصق واحد دورة كاملة حول هذه الزوايا \(\ell\)، يعود الملصق إلى الزاوية نفسها لكنه يكون قد دار بمقدار \(S\). ومن هنا تظهر حالتان فقط:
$$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$$
إذا كان \(S=0\)، تبقى المسارات الثلاثة المحلية للملصقات منفصلة، فنحصل على 3 دورات للملصقات طول كل منها \(\ell\). أما إذا كان \(S=1\) أو \(2\)، فإن هذه المسارات الثلاثة تندمج في دورة واحدة طولها \(3\ell\).
لنفرض أن نوع الدورات في تبديل الزوايا هو
$$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$$
وإذا كان عدد دورات الزوايا هو
$$k=\sum_{r=1}^{8} m_r,$$
فإن عدد التبديلات من هذا النوع يساوي
$$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$$
وهذه هي الصيغة القياسية لعدّ التبديلات ذات البنية الدورية المعطاة.
بالنسبة إلى دورات الزوايا \(k\)، فالذي يهم ليس اتجاه كل زاوية على حدة، بل فقط البواقي الكلية \(S_1,\dots,S_k\in\{0,1,2\}\) لكل دورة. ويتحول القيد العام على الاتجاهات إلى
$$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$$
إذا كان طول الدورة \(j\) هو \(\ell_j\)، فإن تثبيت \(S_j\) يترك \(3^{\ell_j-1}\) تعيينات فعلية للاتجاه داخل تلك الدورة. وبالضرب على جميع الدورات نحصل على
$$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$$
إذن، عند تثبيت نوع الدورات \(\lambda\) ونمط البواقي \(S_1,\dots,S_k\) الذي يحقق شرط التطابق بترديد 3، يوجد بالضبط \(A(\lambda)\,3^{8-k}\) عنصرًا في الزمرة له هذا السلوك المحلي.
عدد دورات الملصقات الناتج من هذا النمط يساوي
$$c=\sum_{j=1}^{k}\phi(S_j).$$
وعليه نحصل على
$$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$$
هذه هي الصيغة المضغوطة التي تعتمد عليها تنفيذا Python وJava. أما تنفيذ C++ فيحسب القيمة نفسها تعدادًا مباشرًا لكل الحالات الممكنة وعددها \(8!\cdot 3^7\)، ثم يستخرج لكل حالة عدد الدورات في تبديل الملصقات الـ24.
لنفترض أن إحدى دورات تبديل الزوايا طولها \(\ell=2\). عندئذٍ فهي تحرك زاويتين، أي 6 ملصقات.
إذا كان باقي الدوران الكلي لهذه الدورة هو \(S=0\)، فإن هذه الملصقات الست تنقسم إلى 3 دورات منفصلة طول كل منها 2، ولذلك تكون مساهمة هذه الدورة في \(c(g)\) مساوية لـ \(3\).
أما إذا كان \(S=1\) أو \(2\)، فإن المسارات الثلاثة للملصقات تتصل ببعضها وتصبح الملصقات الست كلها ضمن دورة واحدة طولها 6، فتكون المساهمة \(1\).
هذه القاعدة المحلية هي جوهر الطريقة كلها: متى عرفنا بنية دورات الزوايا ومجاميع الاتجاهات بترديد 3، أصبح عدد التلوينات الثابتة مباشرة هو \(n^{c(g)}\).
تحسب تنفيذات C++ وPython وJava جميعها بسط Burnside
$$\sum_{g\in G} n^{c(g)}$$
باستخدام حساب أعداد صحيحة كبيرة، ثم تقسم الناتج في النهاية على \(8!\cdot 3^7\).
يقوم تنفيذ C++ بتوليد جميع تبديلات الزوايا الثمانية وجميع متجهات الاتجاه الصحيحة وعددها \(3^7\)، ثم يبني التبديل الموافق على الملصقات الـ24، ويحسب تفكيكه إلى دورات، ويجمع هيستوغرامًا بحسب عدد دورات الملصقات. وبعد اكتمال هذا الهيستوغرام يحسب
$$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$$
حيث \(f_k\) هو عدد عناصر الزمرة التي تملك بالضبط \(k\) دورة للملصقات.
أما تنفيذات Python وJava فلا تبني تبديلات صريحة على 24 ملصقًا. بل تعدّد تجزئات العدد 8، وتحسب عدد تبديلات الزوايا في كل نوع دوري، ثم تمر على بواقي مجاميع الاتجاهات المسموح بها لتلك الدورات، وتضيف الحد \(n^c\) مع المضاعف \(A(\lambda)\,3^{8-k}\). وهاتان الطريقتان متكافئتان رياضيًا تمامًا.
ومن نقاط التحقق العملية
$$N(2)=183,$$
وهذا يؤكد أن حجم الزمرة، وقيد الاتجاهات، ومنطق دورات الملصقات كلها متوافقة قبل الانتقال إلى حساب الحالة المطلوبة عند \(n=10\).
يتتبع تنفيذ C++ مباشرة جميع الحالات الممكنة وعددها
$$8!\cdot 3^7=88{,}179{,}840.$$
وحساب دورات التبديل على 24 ملصقًا يكلف \(O(24)\) لكل حالة، لذلك يكون الزمن الكلي \(O(8!\cdot 3^7\cdot 24)\). أما الذاكرة الإضافية فهي صغيرة، وتقتصر تقريبًا على الهيستوغرام وبعض المجاميع المحلية الخاصة بالخيوط.
تنفيذا Python وJava أكثر ضغطًا بكثير. فهما يمران فقط على 22 تجزئة للعدد 8، ولتجزئة لها \(k\) أجزاء لا يلزم فحص أكثر من \(3^k\le 3^8\) نمطًا من بواقي الاتجاه. وبما أن حجم المكعب ثابت، يمكن عدّ هذا زمنًا ثابتًا عمليًا إذا أهملنا كلفة القوى والجمع في الأعداد الصحيحة الكبيرة. أما الذاكرة فهي \(O(1)\) عدا مجموعة صغيرة من التجزئات والعدادات.