Let \(H(n)\) denote the number of convex equiangular hexagons with integer side lengths and perimeter at most \(n\), where two hexagons are identified when they are congruent. The checkpoints \(H(6)=1\), \(H(12)=10\), and \(H(100)=31248\) show that the count grows quickly, so direct enumeration of all side sextuples is not practical.
The key observation is that an equiangular hexagon is determined by its six side lengths once the six edge directions are fixed. That turns the geometric problem into a counting problem on positive integer 6-tuples, followed by a quotient by the symmetries of a hexagon.
Write the side lengths in cyclic order as \((a,b,c,d,e,f)\). Because each exterior turn is \(60^\circ\), the edge directions are \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). Summing the six edge vectors and forcing the polygon to close produces the arithmetic structure used by the solution.
The \(y\)-components give
$$b+c=e+f.$$
The \(x\)-components give
$$2a+b-c-2d-e+f=0.$$
Eliminating \(b-e\) between these two relations yields the cleaner pair
$$a-d=c-f,\qquad b-e=f-c.$$
Every positive integer sextuple satisfying these two equations corresponds to an equiangular hexagon with those side lengths, and every such hexagon arises this way. So the problem becomes: count positive integer solutions with
$$a+b+c+d+e+f\le n,$$
then divide by congruence.
Before quotienting by congruence, we count ordered sextuples. Congruence classes are orbits under the dihedral group \(D_6\), which has 12 symmetries: 6 rotations and 6 reflections. Burnside's lemma says
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
where \(\operatorname{Fix}(g)\) is the number of admissible sextuples left unchanged by the symmetry \(g\).
The 12 symmetries split into conjugacy classes, so only a few distinct counts are needed:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
Here \(I\) is the identity count, \(R_1,R_2,R_3\) come from rotations by \(60^\circ,120^\circ,180^\circ\), and \(F_{\mathrm{even}},F_{\mathrm{odd}}\) are the two reflection types.
A rotation by \(60^\circ\) or \(300^\circ\) forces all six sides to be equal, so the fixed tuples are
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
Hence
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
A rotation by \(120^\circ\) or \(240^\circ\) forces the pattern
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n.$$
The number of positive pairs with \(x+y\le \lfloor n/3\rfloor\) is
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
A rotation by \(180^\circ\) forces
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
so
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
These are ordinary positive-composition counts.
For the identity symmetry we must count every ordered sextuple satisfying the closure equations. Introduce the difference parameter
$$\delta=a-d=c-f.$$
Then we may write
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
This automatically enforces both closure equations. The perimeter becomes
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
Positivity translates into
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
Let
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
After setting \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\) with \(u,v,w\ge 0\), we get
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
The number of nonnegative triples with sum at most \(R_\delta\) is
$$\binom{R_\delta+3}{3}.$$
Therefore
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
This is exactly the linear summation used by the implementations.
One reflection class fixes sextuples of the form
$$ (u,v,w,u+v-w,w,v).$$
Substituting this pattern into the closure equations shows that it is the general fixed form. Positivity requires
$$u+v-w\ge 1\iff w\le u+v-1,$$
and the perimeter condition is
$$2u+3v+w\le n.$$
So for each positive pair \((u,v)\), the third parameter \(w\) can range from \(1\) up to
$$\min(u+v-1,\ n-2u-3v).$$
The implementations do not iterate over \(w\). Instead, for each fixed \(v\), they split the \(u\)-range at the point where the minimum switches from \(u+v-1\) to \(n-2u-3v\). That turns the entire reflection class into a single linear-time arithmetic summation.
The other reflection class fixes sextuples of the simpler form
$$ (u,u,v,u,u,v).$$
Here the closure equations are automatic, and the perimeter condition is
$$4u+2v\le n.$$
If we set \(M=\lfloor n/2\rfloor\), this becomes
$$2u+v\le M.$$
For each \(u\ge 1\), the number of admissible positive \(v\) is \(M-2u\). Hence
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
Combining both reflection counts with the rotation counts and the identity count gives the final formula
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
This example matches one of the published checkpoints. First, the rotation terms are
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
For the identity term, only \(\delta=-2,-1,0,1,2\) contribute. Their values are
$$1,\ 4,\ 20,\ 4,\ 1,$$
so
$$I(12)=30.$$
For the two reflection classes, the corresponding sums give
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
Burnside then yields
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
which matches the stated checkpoint exactly.
The C++, Python, and Java implementations follow the Burnside decomposition directly. They first evaluate the three rotation contributions from their closed forms, because those require only a few integer divisions and binomial formulas.
Next, the implementation computes the identity contribution by looping over every feasible integer value of the difference parameter \(\delta\). For each \(\delta\), it derives the minimal positive starting values forced by positivity, converts the remaining freedom into a nonnegative triple \((u,v,w)\), and adds the stars-and-bars count \(\binom{R_\delta+3}{3}\) whenever \(R_\delta\ge 0\).
For the first reflection class, the implementation loops over one side parameter and uses a split point to sum the second parameter range in two arithmetic pieces, avoiding an expensive inner enumeration. For the second reflection class, it uses the direct one-dimensional formula coming from \(2u+v\le \lfloor n/2\rfloor\).
Finally, it combines the six class counts with the Burnside weights \(1,2,2,1,3,3\) and divides by 12. The numeric types differ by language, but all three versions use exact integer arithmetic rather than floating point.
The rotation terms and the second reflection class are \(O(1)\). The identity term is a single loop over \(2n+1\) possible values of \(\delta\), so it is \(O(n)\). The first reflection class is also evaluated by a single linear summation over the relevant side parameter range, again \(O(n)\). Therefore the overall running time is \(O(n)\).
The algorithm stores only a fixed number of counters and temporary arithmetic values, so the memory usage is \(O(1)\).
Sei \(H(n)\) die Anzahl konvexer gleichwinkliger Hexagone mit ganzzahligen Seitenlängen und Umfang höchstens \(n\), wobei kongruente Hexagone als gleich gelten. Die Kontrollwerte \(H(6)=1\), \(H(12)=10\) und \(H(100)=31248\) zeigen bereits, dass eine direkte Enumeration aller möglichen Seitensextupel nicht praktikabel ist.
Die entscheidende Beobachtung lautet: Sobald die sechs Kantenrichtungen feststehen, wird ein solches Hexagon allein durch seine sechs Seitenlängen bestimmt. Damit wird aus dem Geometrieproblem ein Problem über positive ganzzahlige 6-Tupel, gefolgt von einer Faktorisierung nach den Symmetrien des Hexagons.
Schreibe die Seitenlängen zyklisch als \((a,b,c,d,e,f)\). Da jeder Außenwinkel \(60^\circ\) beträgt, verlaufen die Kanten in den Richtungen \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). Die Bedingung, dass der Polygonzug sich schließt, liefert genau die linearen Relationen, auf denen die Lösung beruht.
Aus den \(y\)-Komponenten folgt
$$b+c=e+f.$$
Aus den \(x\)-Komponenten folgt
$$2a+b-c-2d-e+f=0.$$
Eliminiert man daraus \(b-e\), erhält man die handlichere Form
$$a-d=c-f,\qquad b-e=f-c.$$
Jedes positive ganzzahlige Sextupel, das diese beiden Gleichungen erfüllt, beschreibt genau ein gleichwinkliges Hexagon mit diesen Seitenlängen, und umgekehrt entsteht jedes relevante Hexagon auf diese Weise. Zu zählen sind also positive Lösungen mit
$$a+b+c+d+e+f\le n,$$
danach wird nach Kongruenz quotientiert.
Zunächst zählt man geordnete Sextupel. Kongruenzklassen sind die Bahnen unter der Diedergruppe \(D_6\) mit 12 Symmetrien: 6 Rotationen und 6 Spiegelungen. Nach dem Burnside-Lemma gilt
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
wobei \(\operatorname{Fix}(g)\) die Anzahl zulässiger Sextupel bezeichnet, die von der Symmetrie \(g\) festgehalten werden.
Die 12 Symmetrien zerfallen in Konjugationsklassen, daher braucht man nur wenige verschiedene Zählungen:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
Dabei ist \(I\) der Identitätsterm, \(R_1,R_2,R_3\) kommen von Rotationen um \(60^\circ,120^\circ,180^\circ\), und \(F_{\mathrm{even}},F_{\mathrm{odd}}\) sind die beiden Spiegelungstypen.
Eine Rotation um \(60^\circ\) oder \(300^\circ\) erzwingt gleiche Seiten:
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
Also
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
Eine Rotation um \(120^\circ\) oder \(240^\circ\) erzwingt das Muster
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n,$$
und damit
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
Eine Rotation um \(180^\circ\) erzwingt
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
weshalb
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
Diese drei Beiträge sind also reine positive-Kompositionszahlen.
Für die Identität müssen alle geordneten Sextupel gezählt werden, die die Schließungsgleichungen erfüllen. Führe den Differenzparameter
$$\delta=a-d=c-f$$
ein. Dann kann man schreiben
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
Damit sind beide Schließungsgleichungen automatisch erfüllt. Der Umfang wird zu
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
Aus der Positivität folgt
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
Setze
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
Mit \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\) und \(u,v,w\ge 0\) bleibt
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
Die Anzahl nichtnegativer Tripel mit Summe höchstens \(R_\delta\) ist
$$\binom{R_\delta+3}{3}.$$
Damit gilt
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
Genau diese lineare Summe wird in den Implementierungen ausgewertet.
Eine Spiegelungsklasse fixiert genau Sextupel der Form
$$ (u,v,w,u+v-w,w,v).$$
Setzt man diese Struktur in die Schließungsbedingungen ein, erhält man die allgemeine feste Form dieser Klasse. Positivität verlangt
$$u+v-w\ge 1\iff w\le u+v-1,$$
und der Umfang liefert
$$2u+3v+w\le n.$$
Für jedes positive Paar \((u,v)\) darf also \(w\) von \(1\) bis
$$\min(u+v-1,\ n-2u-3v)$$
laufen. Die Implementierungen durchlaufen \(w\) jedoch nicht einzeln, sondern teilen für jedes feste \(v\) den \(u\)-Bereich am Umschaltpunkt des Minimums in zwei arithmetische Bereiche. Dadurch bleibt auch dieser Beitrag linear.
Die andere Spiegelungsklasse fixiert das einfachere Muster
$$ (u,u,v,u,u,v).$$
Hier sind die Schließungsgleichungen automatisch erfüllt, und aus dem Umfang folgt
$$4u+2v\le n.$$
Mit \(M=\lfloor n/2\rfloor\) ist das äquivalent zu
$$2u+v\le M.$$
Für jedes \(u\ge 1\) gibt es also \(M-2u\) mögliche positive Werte für \(v\), also
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
Zusammen mit den Rotationen und dem Identitätsterm ergibt sich damit
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
Dieses Beispiel entspricht einem der Kontrollwerte. Zuerst die Rotationen:
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
Beim Identitätsterm tragen nur \(\delta=-2,-1,0,1,2\) bei. Die Beiträge lauten
$$1,\ 4,\ 20,\ 4,\ 1,$$
also
$$I(12)=30.$$
Für die beiden Spiegelungsklassen erhält man
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
Damit liefert Burnside
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
genau wie im Kontrollwert.
Die C++-, Python- und Java-Implementierungen folgen der Burnside-Zerlegung unmittelbar. Zuerst werden die drei Rotationsbeiträge aus ihren geschlossenen Formeln berechnet, da dafür nur einige ganzzahlige Divisionen und Binomialterme benötigt werden.
Danach summiert die Implementierung für den Identitätsterm über alle zulässigen ganzzahligen Werte des Differenzparameters \(\delta\). Für jedes \(\delta\) werden die kleinsten positiven Startwerte bestimmt, die von den Positivitätsbedingungen erzwungen werden. Anschließend wird der verbleibende Freiheitsgrad in ein nichtnegatives Dreifachtupel umgeschrieben und, falls \(R_\delta\ge 0\) ist, der Sterne-und-Balken-Term \(\binom{R_\delta+3}{3}\) addiert.
Für die erste Spiegelungsklasse wird über einen Seitenparameter iteriert, während der zweite Bereich durch eine Falltrennung in zwei arithmetische Summen ausgewertet wird. So wird eine teure innere Schleife vermieden. Für die zweite Spiegelungsklasse genügt die direkte eindimensionale Formel aus \(2u+v\le \lfloor n/2\rfloor\).
Am Ende werden alle Klassenbeiträge mit den Burnside-Gewichten \(1,2,2,1,3,3\) kombiniert und durch 12 geteilt. Die numerischen Datentypen unterscheiden sich je nach Sprache, aber alle drei Versionen arbeiten mit exakter Ganzzahlarithmetik und nicht mit Fließkommazahlen.
Die Rotationsbeiträge und der zweite Spiegelungstyp benötigen \(O(1)\) Zeit. Der Identitätsterm ist eine einzelne Schleife über \(2n+1\) mögliche Werte von \(\delta\) und kostet damit \(O(n)\). Der erste Spiegelungstyp wird ebenfalls durch eine lineare Summe ausgewertet und ist somit ebenfalls \(O(n)\). Insgesamt beträgt die Laufzeit also \(O(n)\).
Es werden nur einige Zähler und temporäre Rechenwerte gespeichert, daher ist der Speicherverbrauch \(O(1)\).
\(H(n)\), çevresi en fazla \(n\) olan, kenar uzunlukları pozitif tamsayı ve tüm iç açıları eşit olan konveks altıgenlerin, eşlik altında farklı sınıf sayısını göstersin. \(H(6)=1\), \(H(12)=10\) ve \(H(100)=31248\) kontrol değerleri, sayının hızla büyüdüğünü ve doğrudan taramanın uygun olmadığını gösterir.
Kritik fikir şudur: Altı kenarın yönleri sabit kabul edildiğinde böyle bir altıgeni belirlemek için sadece altı kenar uzunluğu yeterlidir. Böylece geometri problemi, pozitif tamsayı 6-lılarının sayılması ve ardından altıgen simetrileri altında özdeşleştirilmesi problemine dönüşür.
Kenarları çevresel sırayla \((a,b,c,d,e,f)\) olarak yazalım. Dış dönüş açısı her adımda \(60^\circ\) olduğu için kenar yönleri sırasıyla \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\) olur. Çokgenin kapanması, çözümün kullandığı aritmetik kısıtları verir.
\(y\)-bileşenlerini toplarsak
$$b+c=e+f$$
elde edilir. \(x\)-bileşenlerini toplarsak
$$2a+b-c-2d-e+f=0$$
bulunur. Bu iki bağıntı birlikte daha sade biçimde
$$a-d=c-f,\qquad b-e=f-c$$
şeklinde yazılabilir. Bu iki denklemi sağlayan her pozitif tamsayı sextuple, bu kenar uzunluklarına sahip bir eş açılı altıgen verir; tersine her uygun altıgen de bu biçimde temsil edilir. Dolayısıyla artık saymamız gereken şey
$$a+b+c+d+e+f\le n$$
koşullu pozitif çözümler ve bunların eşlik sınıflarıdır.
Önce sıralı 6-lıları sayarız. Eşlik sınıfları, 12 elemanlı dihedral grup \(D_6\) altındaki yörüngelerdir: 6 dönme ve 6 yansıma. Burnside lemasına göre
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g)$$
olur; burada \(\operatorname{Fix}(g)\), simetri \(g\) altında değişmeden kalan uygun 6-lı sayısıdır.
Bu 12 simetri eşlenik sınıflara ayrıldığı için sadece birkaç farklı terim gerekir:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
Burada \(I\) özdeşlik katkısı, \(R_1,R_2,R_3\) sırasıyla \(60^\circ,120^\circ,180^\circ\) dönmelerinin katkıları, \(F_{\mathrm{even}}\) ve \(F_{\mathrm{odd}}\) ise iki farklı yansıma sınıfıdır.
\(60^\circ\) veya \(300^\circ\) dönmesi tüm kenarları eşit olmaya zorlar:
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
Bu nedenle
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
\(120^\circ\) veya \(240^\circ\) dönmesi şu örüntüyü zorlar:
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n.$$
Pozitif \(x,y\) çiftleri için sonuç
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}$$
olur. \(180^\circ\) dönmesinde ise
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n$$
elde edilir ve dolayısıyla
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
Yani dönme terimlerinin tamamı standart pozitif bileşim sayılarıdır.
Özdeşlik için, kapanış denklemlerini sağlayan tüm sıralı 6-lıları saymamız gerekir. Bunun için fark parametresini
$$\delta=a-d=c-f$$
olarak tanımlayalım. O zaman
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta$$
şeklinde yazabiliriz. Böylece iki kapanış denklemi de otomatik sağlanır. Çevre
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n$$
olur. Pozitiflik koşulları ise
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta)$$
şeklindedir. Şimdi
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta)$$
diyelim. \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\) ve \(u,v,w\ge 0\) dönüşümüyle
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0)$$
kalır. Toplamı en çok \(R_\delta\) olan negatif olmayan üçlü sayısı
$$\binom{R_\delta+3}{3}$$
olduğundan
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}$$
elde edilir. Uygulamalar tam olarak bu lineer toplamı hesaplar.
Yansıma sınıflarından biri şu biçimde sabit kalan 6-lılar verir:
$$ (u,v,w,u+v-w,w,v).$$
Bu yapı kapanış denklemlerine yerleştirildiğinde genel sabit biçim olduğu görülür. Pozitiflik
$$u+v-w\ge 1\iff w\le u+v-1$$
koşulunu, çevre ise
$$2u+3v+w\le n$$
koşulunu verir. Dolayısıyla her pozitif \((u,v)\) çifti için \(w\),
$$1\le w\le \min(u+v-1,\ n-2u-3v)$$
aralığında değişebilir. Uygulamalar \(w\) üzerinde tek tek dönmez; bunun yerine, sabit \(v\) için minimumun hangi noktada dal değiştirdiğini bulup \(u\) aralığını iki aritmetik parçaya ayırır. Böylece bu sınıf da lineer sürede hesaplanır.
Diğer yansıma sınıfı daha basit bir örüntü verir:
$$ (u,u,v,u,u,v).$$
Burada kapanış denklemleri kendiliğinden sağlanır ve çevre koşulu
$$4u+2v\le n$$
olur. \(M=\lfloor n/2\rfloor\) tanımıyla bu
$$2u+v\le M$$
şeklindedir. Her \(u\ge 1\) için uygun pozitif \(v\) sayısı \(M-2u\) olduğundan
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u)$$
elde edilir. Sonuç olarak
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
Bu örnek, verilen kontrol değerlerinden biridir. Önce dönme terimleri:
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
Özdeşlik toplamında yalnızca \(\delta=-2,-1,0,1,2\) katkı verir ve bu katkılar
$$1,\ 4,\ 20,\ 4,\ 1$$
olduğundan
$$I(12)=30$$
çıkar. İki yansıma sınıfı için toplamlar
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6$$
sonucunu verir. Burnside ile
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10$$
elde edilir; bu da kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları Burnside ayrışımını doğrudan izler. Önce üç dönme katkısı kapalı formüllerden hesaplanır; burada yalnızca birkaç tam sayı bölmesi ve binom katsayısı gerekir.
Ardından özdeşlik katkısı için fark parametresi \(\delta\) üzerinde tüm uygun tamsayı değerler dolaşılır. Her \(\delta\) için pozitifliğin zorladığı en küçük başlangıç değerleri bulunur, kalan serbestlik negatif olmayan bir üçlü toplam problemine dönüştürülür ve \(R_\delta\ge 0\) olduğunda \(\binom{R_\delta+3}{3}\) terimi eklenir.
Birinci yansıma sınıfında uygulama bir kenar parametresi üzerinde döner ve ikinci parametre için oluşan aralığı iki aritmetik bölgeye ayırarak iç içe pahalı döngüden kaçınır. İkinci yansıma sınıfı ise \(2u+v\le \lfloor n/2\rfloor\) eşitsizliğinden gelen tek boyutlu kapalı formülle hesaplanır.
Son aşamada altı sınıfın tüm katkıları \(1,2,2,1,3,3\) Burnside katsayılarıyla birleştirilir ve 12'ye bölünür. Dil ayrıntıları farklı olsa da üç sürüm de kayan nokta değil, tam sayılı kesin aritmetik kullanır.
Dönme terimleri ve ikinci yansıma sınıfı \(O(1)\) zamanda hesaplanır. Özdeşlik katkısı \(2n+1\) olası \(\delta\) değeri üzerinden tek bir döngü olduğu için \(O(n)\) zaman alır. Birinci yansıma sınıfı da lineer bir toplamla değerlendirildiğinden o da \(O(n)\) olur. Böylece toplam çalışma süresi \(O(n)\)'dir.
Algoritma yalnızca sabit sayıda sayaç ve geçici aritmetik değişken tuttuğundan bellek kullanımı \(O(1)\)'dir.
Sea \(H(n)\) el número de hexágonos convexos equiangulares con lados enteros y perímetro a lo sumo \(n\), contando dos hexágonos como iguales cuando son congruentes. Los valores de control \(H(6)=1\), \(H(12)=10\) y \(H(100)=31248\) muestran que una enumeración directa de todas las sextuplas posibles de lados no es razonable.
La observación clave es que, una vez fijadas las seis direcciones de los lados, un hexágono de este tipo queda determinado por sus seis longitudes. Así, el problema geométrico se transforma en contar sextuplas positivas de enteros y después dividir por las simetrías del hexágono.
Escribamos las longitudes cíclicamente como \((a,b,c,d,e,f)\). Como el ángulo exterior es siempre \(60^\circ\), las direcciones sucesivas son \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). Imponer que la suma vectorial sea cero produce las relaciones aritméticas centrales de la solución.
Las componentes en \(y\) dan
$$b+c=e+f.$$
Las componentes en \(x\) dan
$$2a+b-c-2d-e+f=0.$$
Eliminando \(b-e\) entre ambas, obtenemos la forma más limpia
$$a-d=c-f,\qquad b-e=f-c.$$
Toda sextupla positiva que satisface estas dos ecuaciones corresponde a un hexágono equiangular con esas longitudes, y todo hexágono relevante aparece de este modo. Por tanto, primero contamos soluciones positivas con
$$a+b+c+d+e+f\le n,$$
y después identificamos las que son congruentes.
Antes de factorizar por congruencia, contamos sextuplas ordenadas. Las clases buscadas son las órbitas bajo el grupo diedral \(D_6\), que tiene 12 simetrías: 6 rotaciones y 6 reflexiones. La lema de Burnside dice que
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
donde \(\operatorname{Fix}(g)\) es el número de sextuplas admisibles fijas bajo la simetría \(g\).
Como las 12 simetrías se agrupan en clases de conjugación, basta con unos pocos conteos distintos:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
Aquí \(I\) es el término identidad, \(R_1,R_2,R_3\) corresponden a las rotaciones de \(60^\circ,120^\circ,180^\circ\), y \(F_{\mathrm{even}},F_{\mathrm{odd}}\) son los dos tipos de reflexión.
Una rotación de \(60^\circ\) o \(300^\circ\) obliga a que todos los lados sean iguales:
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
Por tanto,
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
Una rotación de \(120^\circ\) o \(240^\circ\) obliga al patrón
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n,$$
de donde
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
La rotación de \(180^\circ\) obliga a
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
y por ello
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
Los tres términos de rotación son, pues, conteos estándar de particiones positivas con suma acotada.
Para la identidad hay que contar todas las sextuplas ordenadas que satisfacen las ecuaciones de cierre. Introducimos el parámetro de diferencia
$$\delta=a-d=c-f.$$
Entonces podemos escribir
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
Esto hace automáticas las dos ecuaciones lineales. El perímetro pasa a ser
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
La positividad impone
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
Definamos
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
Al poner \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\) con \(u,v,w\ge 0\), queda
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
El número de ternas no negativas con suma a lo sumo \(R_\delta\) es
$$\binom{R_\delta+3}{3}.$$
Así obtenemos
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
Esta es exactamente la suma lineal que evalúan las implementaciones.
Una de las clases de reflexión fija sextuplas de la forma
$$ (u,v,w,u+v-w,w,v).$$
Al sustituir este patrón en las ecuaciones de cierre se comprueba que esa es la forma general fija de dicha clase. La positividad exige
$$u+v-w\ge 1\iff w\le u+v-1,$$
mientras que el perímetro da
$$2u+3v+w\le n.$$
Por tanto, para cada par positivo \((u,v)\), el parámetro \(w\) puede tomar los valores
$$1\le w\le \min(u+v-1,\ n-2u-3v).$$
Las implementaciones no recorren \(w\) explícitamente. En su lugar, para cada \(v\) fijo dividen el rango de \(u\) en el punto donde cambia el mínimo anterior y convierten todo el conteo en dos sumas aritméticas. Eso mantiene el coste lineal.
La otra clase de reflexión fija el patrón más simple
$$ (u,u,v,u,u,v).$$
Aquí las ecuaciones de cierre ya quedan satisfechas, y el perímetro se reduce a
$$4u+2v\le n.$$
Si definimos \(M=\lfloor n/2\rfloor\), esto equivale a
$$2u+v\le M.$$
Para cada \(u\ge 1\), el número de valores positivos admisibles de \(v\) es \(M-2u\). Por consiguiente,
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
Reuniendo ambos tipos de reflexión con las rotaciones y la identidad, llegamos a
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
Este ejemplo coincide con uno de los valores de control. Primero, las rotaciones:
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
En la identidad solo contribuyen \(\delta=-2,-1,0,1,2\), con valores
$$1,\ 4,\ 20,\ 4,\ 1,$$
de modo que
$$I(12)=30.$$
Para las dos clases de reflexión se obtiene
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
Aplicando Burnside,
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
exactamente el valor esperado.
Las implementaciones en C++, Python y Java siguen directamente la descomposición de Burnside. Primero calculan las tres contribuciones de rotación mediante sus fórmulas cerradas, ya que solo requieren divisiones enteras y coeficientes binomiales.
Después, para la identidad, la implementación recorre todos los valores enteros factibles del parámetro \(\delta\). Para cada uno, obtiene las cotas mínimas positivas impuestas por la positividad, traduce el resto de libertad a una terna no negativa y suma \(\binom{R_\delta+3}{3}\) cuando \(R_\delta\ge 0\).
En la primera clase de reflexión, la implementación itera sobre un parámetro de lado y resuelve el rango del otro mediante una partición en dos sumas aritméticas, con lo que evita un bucle interior costoso. La segunda clase de reflexión se resuelve con la fórmula unidimensional derivada de \(2u+v\le \lfloor n/2\rfloor\).
Finalmente, combina las seis contribuciones con los pesos de Burnside \(1,2,2,1,3,3\) y divide por 12. Aunque el tipo numérico cambia según el lenguaje, en todos los casos se usa aritmética entera exacta.
Las rotaciones y la segunda clase de reflexión se calculan en \(O(1)\). La identidad es un único bucle sobre \(2n+1\) valores posibles de \(\delta\), así que cuesta \(O(n)\). La primera clase de reflexión también se evalúa mediante una suma lineal, de modo que su coste es \(O(n)\). Por lo tanto, el tiempo total es \(O(n)\).
El algoritmo solo mantiene un número constante de acumuladores y variables temporales, así que el uso de memoria es \(O(1)\).
记 \(H(n)\) 为周长不超过 \(n\) 的凸等角整数边六边形的个数，其中全等的六边形只算一个。题目给出的检查值 \(H(6)=1\)、\(H(12)=10\)、\(H(100)=31248\) 已经说明，随着 \(n\) 增大，直接枚举所有边长六元组会迅速失去可行性。
这道题真正的突破点在于：一旦六条边的方向顺序固定，这样的六边形就完全由六条边长决定。因此几何问题可以改写成一个整数 6 元组计数问题，再用正六边形的对称群把全等情形合并掉。
按环绕顺序把六条边长写成 \((a,b,c,d,e,f)\)。由于外角始终是 \(60^\circ\)，六条边的方向依次是 \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\)。要求多边形闭合，也就是六个边向量之和为零，这会给出整个解法所依赖的线性约束。
先看纵向分量，得到
$$b+c=e+f.$$
再看横向分量，得到
$$2a+b-c-2d-e+f=0.$$
把这两式联立并消去 \(b-e\)，可以整理成更对称、更适合计数的形式：
$$a-d=c-f,\qquad b-e=f-c.$$
任何满足这两条方程的正整数六元组，都对应一个等角六边形；反过来，题目要求计数的对象也都可以这样表示。所以问题已经转化为：统计满足
$$a+b+c+d+e+f\le n$$
的正整数解，然后再按全等关系归并。
如果暂时不去掉全等，只统计“有顺序的边长六元组”，那么全等类就是这些六元组在二面体群 \(D_6\) 作用下的轨道。这个群一共有 12 个元素，也就是 6 个旋转和 6 个反射。Burnside 引理告诉我们：
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
其中 \(\operatorname{Fix}(g)\) 表示在对称 \(g\) 作用下保持不变的合法六元组个数。
因为 12 个对称按共轭类分组后只剩下少数几种不同情形，所以最终只需要求下面六类计数：
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
这里 \(I\) 是恒等变换的固定点数，\(R_1,R_2,R_3\) 分别对应 \(60^\circ,120^\circ,180^\circ\) 的旋转，\(F_{\mathrm{even}},F_{\mathrm{odd}}\) 则是两种不同类型的反射。
\(60^\circ\) 或 \(300^\circ\) 旋转会迫使六条边全部相等，因此固定点一定是
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
所以
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
\(120^\circ\) 或 \(240^\circ\) 旋转会迫使边长呈现交替模式
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n,$$
于是正整数对 \((x,y)\) 的个数就是
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
\(180^\circ\) 旋转对应的模式是
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
因此
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
这三个旋转项都只是“正整数和受限”的标准计数问题。
恒等变换下没有额外对称约束，因此必须统计所有满足闭合方程的有序六元组。最自然的参数是两组对边差值共同等于的那个量：
$$\delta=a-d=c-f.$$
一旦固定 \(\delta\)，就可以把六条边写成
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
这样写的好处是，两条闭合方程会自动满足。周长条件变成
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
由于六条边都必须是正整数，得到下界
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
记
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
然后令 \(\alpha=\alpha_0+u\)、\(\beta=\beta_0+v\)、\(\gamma=\gamma_0+w\)，其中 \(u,v,w\ge 0\)。这样剩下的唯一约束就是
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
而“非负三元组的和不超过 \(R_\delta\)”的个数正好是经典的 stars and bars 结果
$$\binom{R_\delta+3}{3}.$$
因此恒等项可以写成
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
这也是三种语言实现都在逐项累加的核心公式。
其中一类反射固定的六元组形状为
$$ (u,v,w,u+v-w,w,v).$$
把这个模式代回闭合方程，可以验证它确实描述了该反射类的全部固定点。现在只剩下正整数约束和周长约束。正整数条件要求
$$u+v-w\ge 1\iff w\le u+v-1,$$
而周长条件给出
$$2u+3v+w\le n.$$
所以对于任意正整数 \((u,v)\)，第三个参数 \(w\) 的合法范围是
$$1\le w\le \min(u+v-1,\ n-2u-3v).$$
如果直接三重循环，这一部分会很慢。实现中并不显式遍历 \(w\)，而是对固定的 \(v\) 找到最小值分支切换的位置，把 \(u\) 的区间拆成两段，用等差求和一次性加完。
另一类反射固定的模式更简单：
$$ (u,u,v,u,u,v).$$
这时闭合方程自动满足，周长约束直接化成
$$4u+2v\le n.$$
如果记 \(M=\lfloor n/2\rfloor\)，那么等价于
$$2u+v\le M.$$
于是对每个 \(u\ge 1\)，可选的正整数 \(v\) 恰好有 \(M-2u\) 个，所以
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
把两类反射、三类旋转以及恒等项一起代回 Burnside 引理，就得到最终闭式：
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
这个例子恰好对应题目给出的一个检查值。先算旋转项：
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
恒等项里，只有 \(\delta=-2,-1,0,1,2\) 有贡献，对应值依次为
$$1,\ 4,\ 20,\ 4,\ 1,$$
因此
$$I(12)=30.$$
两类反射的计数分别是
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
于是
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
与题目检查值完全一致。
C++、Python 和 Java 实现都严格按照上面的 Burnside 分解来写。它们先用封闭公式计算三个旋转项，因为这一步只需要几个整除和组合数公式。
接着，程序对恒等项遍历所有可能的整数 \(\delta\)。对每个 \(\delta\)，先算出由正整数条件强制产生的最小起点，再把剩余自由度改写成一个非负三元组的求和界，若 \(R_\delta\ge 0\) 就累加 \(\binom{R_\delta+3}{3}\)。
第一类反射是实现里的主要技巧点。程序只遍历一个边长参数，通过找到分界点，把另一个参数的贡献拆成两段等差和，从而避免显式三重枚举。第二类反射则直接使用由 \(2u+v\le \lfloor n/2\rfloor\) 得到的一维求和公式。
最后，程序按 Burnside 权重 \(1,2,2,1,3,3\) 组合六类固定点计数，再除以 12。三种语言使用的整数类型不同，但都保持精确整数运算，没有使用浮点近似。
三个旋转项和第二类反射都可以在 \(O(1)\) 时间内完成。恒等项需要遍历 \(2n+1\) 个可能的 \(\delta\)，因此是 \(O(n)\)。第一类反射同样通过线性求和完成，也是 \(O(n)\)。所以总时间复杂度为 \(O(n)\)。
整个算法只维护常数个计数器和临时变量，因此空间复杂度是 \(O(1)\)。
Обозначим через \(H(n)\) число выпуклых равноугольных шестиугольников с целыми длинами сторон и периметром не больше \(n\), считая конгруэнтные фигуры одинаковыми. Контрольные значения \(H(6)=1\), \(H(12)=10\) и \(H(100)=31248\) показывают, что прямой перебор всех возможных шестёрок сторон быстро становится непрактичным.
Ключевой факт состоит в том, что после фиксации шести направлений рёбер такой шестиугольник полностью определяется шестью длинами сторон. Поэтому геометрическая задача превращается в задачу о подсчёте положительных целочисленных 6-кортежей с последующим фактором по симметриям шестиугольника.
Запишем длины сторон по кругу как \((a,b,c,d,e,f)\). Поскольку внешний угол каждый раз равен \(60^\circ\), направления рёбер идут как \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). Условие замыкания ломаной даёт те самые линейные соотношения, на которых построено решение.
Из суммы \(y\)-компонент получаем
$$b+c=e+f.$$
Из суммы \(x\)-компонент получаем
$$2a+b-c-2d-e+f=0.$$
Исключая отсюда величину \(b-e\), приходим к более симметричной форме
$$a-d=c-f,\qquad b-e=f-c.$$
Любой положительный целочисленный 6-кортеж, удовлетворяющий этим двум равенствам, задаёт равноугольный шестиугольник с такими сторонами, и наоборот. Значит, сначала нужно посчитать положительные решения при условии
$$a+b+c+d+e+f\le n,$$
а затем отождествить конгруэнтные варианты.
До факторизации по конгруэнтности считаются упорядоченные шестёрки. Искомые классы являются орбитами действия диэдральной группы \(D_6\), у которой 12 симметрий: 6 вращений и 6 отражений. По лемме Бёрнсайда
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
где \(\operatorname{Fix}(g)\) обозначает число допустимых шестёрок, неподвижных относительно симметрии \(g\).
Так как эти 12 элементов разбиваются на классы сопряжённости, нужно вычислить лишь несколько разных величин:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
Здесь \(I\) — вклад тождества, \(R_1,R_2,R_3\) соответствуют поворотам на \(60^\circ,120^\circ,180^\circ\), а \(F_{\mathrm{even}},F_{\mathrm{odd}}\) — двум типам отражений.
Поворот на \(60^\circ\) или \(300^\circ\) заставляет все шесть сторон совпадать:
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
Следовательно,
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
Поворот на \(120^\circ\) или \(240^\circ\) даёт шаблон
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n,$$
поэтому
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
Поворот на \(180^\circ\) фиксирует
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
и отсюда
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
Таким образом, все вклады вращений являются обычными подсчётами положительных разложений суммы.
Для тождества нужно посчитать все упорядоченные шестёрки, удовлетворяющие уравнениям замыкания. Введём параметр разности
$$\delta=a-d=c-f.$$
Тогда можно записать
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
При такой записи обе линейные связи выполняются автоматически. Ограничение на периметр становится
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
Положительность сторон даёт нижние границы
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
Обозначим
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
Положив \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\), где \(u,v,w\ge 0\), получаем единственное оставшееся ограничение
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
Число неотрицательных троек с суммой не больше \(R_\delta\) равно
$$\binom{R_\delta+3}{3}.$$
Следовательно,
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
Именно эту линейную сумму и вычисляют реализации.
Один из классов отражений фиксирует 6-кортежи вида
$$ (u,v,w,u+v-w,w,v).$$
Подстановка этого шаблона в уравнения замыкания показывает, что так описываются все неподвижные точки данного класса. Положительность требует
$$u+v-w\ge 1\iff w\le u+v-1,$$
а ограничение на периметр даёт
$$2u+3v+w\le n.$$
Значит, для каждого положительного \((u,v)\) параметр \(w\) пробегает значения
$$1\le w\le \min(u+v-1,\ n-2u-3v).$$
В реализациях \(w\) не перебирается явно. Вместо этого при фиксированном \(v\) диапазон \(u\) разбивается в точке, где минимум переключается с одной границы на другую, после чего обе части суммируются арифметически. Это сохраняет линейную сложность.
Другой класс отражений фиксирует более простой шаблон
$$ (u,u,v,u,u,v).$$
Здесь уравнения замыкания выполняются автоматически, а периметр удовлетворяет
$$4u+2v\le n.$$
Если положить \(M=\lfloor n/2\rfloor\), получаем эквивалентное условие
$$2u+v\le M.$$
Для каждого \(u\ge 1\) существует ровно \(M-2u\) положительных значений \(v\), поэтому
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
Собирая всё вместе, получаем окончательное выражение
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
Этот пример совпадает с одним из контрольных значений задачи. Сначала вращения:
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
Во вкладе тождества ненулевыми оказываются только \(\delta=-2,-1,0,1,2\), и они дают
$$1,\ 4,\ 20,\ 4,\ 1,$$
откуда
$$I(12)=30.$$
Для двух классов отражений получаем
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
Тогда по Бёрнсайду
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
что в точности совпадает с контрольным значением.
Реализации на C++, Python и Java буквально следуют формуле Бёрнсайда. Сначала они вычисляют три вклада вращений по замкнутым формулам, поскольку здесь нужны только целочисленные деления и биномиальные коэффициенты.
Затем для вклада тождества программа перебирает все допустимые целые значения параметра \(\delta\). Для каждого \(\delta\) она находит минимальные положительные стартовые значения, навязанные условиями положительности, преобразует остаток свободы в задачу о неотрицательной тройке и, если \(R_\delta\ge 0\), добавляет вклад \(\binom{R_\delta+3}{3}\).
Для первого класса отражений реализация итерируется по одному параметру стороны и вычисляет вклад второго параметра через разбиение на два арифметических диапазона, избегая дорогого внутреннего перебора. Второй класс отражений считается по прямой одномерной формуле, следующей из неравенства \(2u+v\le \lfloor n/2\rfloor\).
В конце шесть вкладов объединяются с весами Бёрнсайда \(1,2,2,1,3,3\), после чего результат делится на 12. Числовые типы различаются между языками, но все версии используют точную целочисленную арифметику.
Вклады вращений и второй тип отражений вычисляются за \(O(1)\). Вклад тождества представляет собой один проход по \(2n+1\) значениям \(\delta\), то есть имеет сложность \(O(n)\). Первый тип отражений также оценивается одной линейной суммой, поэтому тоже работает за \(O(n)\). Следовательно, полная временная сложность равна \(O(n)\).
Алгоритм хранит только постоянное число счётчиков и временных величин, так что потребление памяти равно \(O(1)\).
لنرمز بـ \(H(n)\) إلى عدد السداسيات المحدبة متساوية الزوايا ذات الأضلاع الصحيحة والتي لا يزيد محيطها على \(n\)، مع اعتبار السداسيات المتطابقة شكلاً واحدًا. قيم التحقق \(H(6)=1\) و\(H(12)=10\) و\(H(100)=31248\) توضح أن العدد ينمو بسرعة، ولذلك فإن التعداد المباشر لجميع السداسيات الممكنة من أطوال الأضلاع ليس عمليًا.
الفكرة الحاسمة هي أن السداسي من هذا النوع يتحدد بالكامل بمجرد تثبيت ترتيب اتجاهات أضلاعه الستة، وعندها تكفي أطوال الأضلاع الستة لوصفه. وهكذا تتحول المسألة الهندسية إلى مسألة عدّ لمتتاليات صحيحة موجبة من ستة عناصر، ثم تقسيم هذا العدّ على تناظرات السداسي.
لنكتب أطوال الأضلاع بالترتيب الدوري على الصورة \((a,b,c,d,e,f)\). بما أن زاوية الدوران الخارجية تساوي دائمًا \(60^\circ\)، فإن اتجاهات الأضلاع تتتابع على الزوايا \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). وشرط انغلاق المضلع، أي أن مجموع المتجهات الستة يساوي الصفر، هو الذي يولّد القيود الخطية الأساسية في الحل.
من مركبات الاتجاه الرأسي نحصل على
$$b+c=e+f.$$
ومن مركبات الاتجاه الأفقي نحصل على
$$2a+b-c-2d-e+f=0.$$
وعند حذف المقدار \(b-e\) من هاتين العلاقتين نصل إلى الصيغة الأبسط
$$a-d=c-f,\qquad b-e=f-c.$$
كل سداسية من الأعداد الصحيحة الموجبة تحقق هاتين المعادلتين تمثل سداسيًا متساوي الزوايا بهذه الأضلاع، والعكس صحيح أيضًا. إذًا صار المطلوب أولًا هو عدّ الحلول الموجبة تحت القيد
$$a+b+c+d+e+f\le n,$$
ثم جمع المتطابقات في فئة واحدة.
قبل حذف التماثلات، نعدّ السداسيات المرتبة للأضلاع. فئات التطابق هي المدارات تحت تأثير الزمرة الثنائية \(D_6\) التي تملك 12 تماثلًا: 6 دورانات و6 انعكاسات. وتنص لمّة Burnside على أن
$$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$$
حيث \(\operatorname{Fix}(g)\) هو عدد السداسيات المقبولة التي تبقى ثابتة تحت التماثل \(g\).
وبما أن عناصر الزمرة تتجمع في أصناف اقتران، فلا نحتاج إلا إلى عدد قليل من العدّات المختلفة:
$$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$$
هنا \(I\) هو حدّ الهوية، و\(R_1,R_2,R_3\) تمثل مساهمات دورانات \(60^\circ\) و\(120^\circ\) و\(180^\circ\)، أما \(F_{\mathrm{even}}\) و\(F_{\mathrm{odd}}\) فهما نوعا الانعكاس المختلفان.
الدوران بمقدار \(60^\circ\) أو \(300^\circ\) يفرض أن تكون جميع الأضلاع متساوية:
$$ (x,x,x,x,x,x),\qquad 6x\le n.$$
ومن ثم
$$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$$
أما الدوران بمقدار \(120^\circ\) أو \(240^\circ\) فيفرض النمط
$$ (x,y,x,y,x,y),\qquad 3x+3y\le n,$$
فتكون النتيجة
$$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$$
وفي حالة الدوران \(180^\circ\) نحصل على
$$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$$
وبالتالي
$$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$$
إذن جميع حدود الدوران ليست أكثر من عدّ لتراكيب موجبة مجموعها مقيد.
في حدّ الهوية لا توجد مساواة إضافية بين الأضلاع، لذا يجب عدّ جميع السداسيات المرتبة التي تحقق معادلات الانغلاق فقط. نعرّف أولًا معامل الفرق
$$\delta=a-d=c-f.$$
وعندئذٍ يمكن كتابة الأضلاع على الصورة
$$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$$
$$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$$
بهذا التمثيل تصبح معادلات الانغلاق صحيحة تلقائيًا. أما شرط المحيط فيتحول إلى
$$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$$
ومن شرط الإيجابية نحصل على الحدود الدنيا
$$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$$
لنضع
$$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$$
$$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$$
ثم نكتب \(\alpha=\alpha_0+u\)، \(\beta=\beta_0+v\)، \(\gamma=\gamma_0+w\) حيث \(u,v,w\ge 0\). يبقى عندئذٍ القيد الوحيد
$$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$$
وعدد الثلاثيات غير السالبة التي لا يتجاوز مجموعها \(R_\delta\) هو
$$\binom{R_\delta+3}{3}.$$
لذلك يصبح حدّ الهوية
$$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$$
وهذه هي الصيغة التي تجمعها التطبيقات الثلاثة حدًا حدًا.
أحد صنفي الانعكاس يثبت السداسيات المرتبة من الشكل
$$ (u,v,w,u+v-w,w,v).$$
وعند إدخال هذا النمط في معادلات الانغلاق يتبين أنه الوصف العام لنقاط التثبيت في هذا الصنف. تفرض الإيجابية الشرط
$$u+v-w\ge 1\iff w\le u+v-1,$$
بينما يعطي المحيط
$$2u+3v+w\le n.$$
إذًا لكل زوج موجب \((u,v)\) يكون المجال الممكن لـ \(w\) هو
$$1\le w\le \min(u+v-1,\ n-2u-3v).$$
لا تقوم التطبيقات بالتكرار الصريح على \(w\). بل إنها، عند تثبيت \(v\)، تجد النقطة التي تتبدل عندها قيمة هذا الحد الأدنى، ثم تقسّم مجال \(u\) إلى جزأين وتحسب كل جزء بجمع حسابي مباشر. وهذا ما يبقي التعقيد خطيًا.
الصنف الآخر من الانعكاسات يثبت النمط الأبسط
$$ (u,u,v,u,u,v).$$
هنا تتحقق معادلات الانغلاق تلقائيًا، ويصبح شرط المحيط
$$4u+2v\le n.$$
وإذا عرفنا \(M=\lfloor n/2\rfloor\)، فهذا يكافئ
$$2u+v\le M.$$
وعليه، لكل \(u\ge 1\) يوجد بالضبط \(M-2u\) قيم موجبة ممكنة لـ \(v\)، ومن ثم
$$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$$
وعند جمع حدّي الانعكاس مع حدود الدوران وحدّ الهوية نحصل على الصيغة النهائية
$$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$$
هذا المثال يطابق إحدى قيم التحقق المذكورة. أولًا نحسب حدود الدوران:
$$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$$
في حدّ الهوية، القيم غير الصفرية تظهر فقط عند \(\delta=-2,-1,0,1,2\)، وتعطي
$$1,\ 4,\ 20,\ 4,\ 1,$$
ومن ثم
$$I(12)=30.$$
أما مجموعا صنفي الانعكاس فهما
$$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$$
وبالتالي
$$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$$
وهو بالضبط نفس مقدار التحقق.
تتبع تطبيقات C++ وPython وJava هذا التحليل نفسه خطوةً بخطوة. فهي تبدأ بحساب حدود الدوران الثلاثة من صيغ مغلقة، لأن هذه المرحلة لا تحتاج إلا إلى قسمة صحيحة وبعض معاملات ثنائية بسيطة.
بعد ذلك تحسب مساهمة الهوية عبر المرور على كل قيمة صحيحة ممكنة للمعامل \(\delta\). ولكل قيمة، تستخرج الحدود الدنيا المفروضة من شرط الإيجابية، ثم تعيد صياغة الحرية المتبقية على شكل ثلاثي غير سالب، وإذا كان \(R_\delta\ge 0\) تضيف المقدار \(\binom{R_\delta+3}{3}\).
وفي صنف الانعكاس الأول، لا يكرر التنفيذ على جميع القيم الداخلية بشكل مباشر، بل يستخدم نقطة فصل تقسم المجال إلى مجموعين حسابيين، وبذلك يتجنب تكرارًا داخليًا مكلفًا. أما صنف الانعكاس الثاني فيحسبه من الصيغة أحادية البعد الناتجة عن المتباينة \(2u+v\le \lfloor n/2\rfloor\).
وأخيرًا يجمع جميع المساهمات بالأوزان \(1,2,2,1,3,3\) الخاصة بلمّة Burnside ثم يقسم على 12. وعلى الرغم من اختلاف أنواع الأعداد بين اللغات، فإن جميع النسخ تعتمد على حساب صحيح دقيق لا على الأعداد العائمة.
حدود الدوران والصنف الثاني من الانعكاس يُحسبان في \(O(1)\). أما حدّ الهوية فهو حلقة واحدة على \(2n+1\) قيمة محتملة لـ \(\delta\)، ولذلك زمنه \(O(n)\). والصنف الأول من الانعكاس يُقيَّم كذلك بمجموع خطي، فيكون \(O(n)\) أيضًا. إذن الزمن الكلي للخوارزمية هو \(O(n)\).
لا تحتفظ الخوارزمية إلا بعدد ثابت من المجاميع والقيم المؤقتة، ولذلك يكون استهلاك الذاكرة \(O(1)\).