The solution counts admissible unlabelled coloured trees on \(n\) vertices and asks for \(g(10000)\) modulo
$$10^9+7.$$
The colour rules encoded by the implementations are:
red vertices may have degree at most \(4\), blue vertices degree at most \(3\), yellow vertices degree at most \(3\), and an edge joining two yellow vertices is forbidden. The first checkpoints are
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
A direct isomorphism test over all coloured trees of size \(10000\) is hopeless, so the program instead uses ordinary generating functions, cycle-index formulas for multisets, and the dissymmetry theorem for trees.
The counting is done in three stages: first count planted trees, then count vertex-rooted trees, and finally recover the unrooted objects.
Let \(R(x)\), \(B(x)\), and \(Y(x)\) be the ordinary generating functions for planted trees whose distinguished root vertex is red, blue, or yellow. A planted tree has one distinguished parent edge above the root, so one incidence of the root is already used.
Define the aggregate series
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
Here \(A(x)\) is the class of all planted trees, while \(N(x)\) is the class of planted trees whose root is not yellow. The second series is needed because a yellow root is not allowed to touch a yellow neighbour.
Since the parent edge already occupies one slot, the root of a planted tree can accept only
red: \(0,1,2,3\) children, blue: \(0,1,2\) children, yellow: \(0,1,2\) non-yellow children.
When the root receives an unordered collection of child subtrees, we must count multisets rather than ordered tuples. For ordinary generating functions, the cycle-index formulas for the symmetric groups give
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
These are exactly the multiset operators that appear in the program.
Therefore the planted-tree equations are
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
The factor \(x\) accounts for the root itself, and the constant \(1\) means that the root may have no children.
To count trees rooted at a vertex rather than at a parent edge, the root regains its full degree budget. Let \(V_R(x)\), \(V_B(x)\), and \(V_Y(x)\) denote the generating functions for vertex-rooted admissible trees. Then
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
Adding the three root colours gives the full vertex-rooted series
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
This matches the second stage of the implementations.
If we root a tree at a directed edge, the edge splits the tree into an ordered pair of planted trees. Without the colour restriction this would give \(A(x)^2\). The only forbidden case is when both exposed roots are yellow, so the directed edge-rooted series is
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
For an undirected edge root, the two sides are an unordered pair. Burnside's lemma gives
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
The extra terms \(A(x^2)\) and \(Y(x^2)\) represent the fixed points of swapping the two sides: both halves must be identical, and the yellow-yellow case is still excluded.
For trees, the classical dissymmetry theorem says that
$$\text{unrooted}=\text{vertex-rooted}+\text{edge-rooted}-\text{directed-edge-rooted}.$$
Translated into generating functions,
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
The desired sequence is therefore
$$g(n)=\left[x^n\right]G(x).$$
This identity is exactly what the final correction stage computes.
For \(n=3\), the only tree shape is a path of length \(2\). Up to isomorphism, the middle vertex determines the adjacency pattern.
If the middle vertex is red, the two leaves form an unordered multiset chosen from \(\{R,B,Y\}\). There are
$$\binom{3+2-1}{2}=6$$
such multisets.
If the middle vertex is blue, the same count applies, again giving \(6\).
If the middle vertex is yellow, each neighbour must be non-yellow, so the two leaves form an unordered multiset from \(\{R,B\}\). That gives
$$\binom{2+2-1}{2}=3.$$
Hence
$$g(3)=6+6+3=15,$$
which agrees with the validation values used by the implementation.
The C++, Python, and Java implementations all follow the same pipeline. First they build coefficient tables for the planted series up to size \(10000\). When constructing size \(n\), they read multiset contributions at size \(n-1\) because the root contributes one vertex.
During that first pass, the implementation incrementally maintains square convolutions of the aggregated planted series. Those precomputed quadratic terms are then reused to obtain the degree-\(2\) and degree-\(3\) multiset contributions efficiently.
In the second pass, the implementation constructs shifted copies corresponding to \(F(x^2)\), \(F(x^3)\), and \(F(x^4)\), together with the cubic and quartic convolution terms required by the cycle-index formulas. That produces the full vertex-rooted counts.
Finally it forms the directed edge-rooted and undirected edge-rooted series, applies
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
and extracts the coefficient of \(x^{10000}\) modulo \(10^9+7\). The C++ implementation parallelizes some of the largest convolutions, but the mathematical formula is identical in all three languages.
Let \(N=10000\). The dominant work comes from quadratic convolutions and from the incremental updates that build the square series. Both stages are \(O(N^2)\) time overall. Only a fixed number of coefficient arrays of length \(N+1\) are stored, so the memory usage is \(O(N)\).
Die Lösung zählt zulässige unmarkierte gefärbte Bäume mit \(n\) Knoten und sucht den Wert \(g(10000)\) modulo
$$10^9+7.$$
Die von den Implementierungen kodierten Farbregeln lauten:
rote Knoten haben Grad höchstens \(4\), blaue Knoten Grad höchstens \(3\), gelbe Knoten Grad höchstens \(3\), und eine Kante zwischen zwei gelben Knoten ist verboten. Die ersten Kontrollwerte sind
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
Eine direkte Erzeugung aller Isomorphieklassen bei \(n=10000\) ist unmöglich. Deshalb arbeitet das Programm mit gewöhnlichen erzeugenden Funktionen, Zyklusindex-Formeln für Multimengen und dem Dissymmetriesatz für Bäume.
Die Zählung läuft in drei Schritten: zuerst gepflanzte Bäume, dann knotengerichtete Bäume, danach Rückgewinnung der ungerichteten Klasse.
Seien \(R(x)\), \(B(x)\) und \(Y(x)\) die gewöhnlichen erzeugenden Funktionen der gepflanzten Bäume, deren ausgezeichnete Wurzel rot, blau oder gelb ist. Bei einem gepflanzten Baum gibt es oberhalb der Wurzel bereits eine ausgezeichnete Elternkante, also ist eine Inzidenz der Wurzel schon belegt.
Definiere die Summenserien
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
Dabei beschreibt \(A(x)\) alle gepflanzten Bäume, während \(N(x)\) genau die gepflanzten Bäume mit nichtgelber Wurzel zählt. Diese zweite Serie wird benötigt, weil eine gelbe Wurzel keinen gelben Nachbarn haben darf.
Da die Elternkante bereits einen Platz verbraucht, kann die Wurzel eines gepflanzten Baums nur noch
rot: \(0,1,2,3\) Kinder, blau: \(0,1,2\) Kinder, gelb: \(0,1,2\) nichtgelbe Kinder
tragen.
Wenn an die Wurzel eine ungeordnete Sammlung von Teilbäumen gehängt wird, müssen Multimengen und nicht geordnete Tupel gezählt werden. Für gewöhnliche erzeugende Funktionen liefern die Zyklusindex-Formeln der symmetrischen Gruppen
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
Genau diese Multimengenoperatoren werden im Programm ausgewertet.
Damit lauten die Gleichungen für gepflanzte Bäume
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
Der Faktor \(x\) zählt die Wurzel selbst, und die Konstante \(1\) steht für den Fall ohne Kinder.
Für einen an einem Knoten verwurzelten Baum steht das volle Gradbudget wieder zur Verfügung. Seien \(V_R(x)\), \(V_B(x)\) und \(V_Y(x)\) die erzeugenden Funktionen der zulässigen knotengerichteten Bäume. Dann gilt
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
Die Summe über alle Wurzelfarben ist
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
Das ist genau die zweite Stufe der Implementierung.
Wurzelt man einen Baum an einer gerichteten Kante, zerfällt er in ein geordnetes Paar gepflanzter Bäume. Ohne Farbbeschränkung ergäbe das \(A(x)^2\). Verboten ist nur der Fall, dass beide freiliegenden Wurzeln gelb sind, also
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
Für eine ungerichtete Kantenwurzel sind die beiden Seiten ein ungeordnetes Paar. Burnside liefert
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
Die Zusatzterme \(A(x^2)\) und \(Y(x^2)\) zählen die Fixpunkte des Vertauschens beider Seiten: beide Hälften müssen identisch sein, und der gelb-gelb-Fall bleibt ausgeschlossen.
Für Bäume besagt der klassische Dissymmetriesatz
$$\text{ungerichtet}=\text{knotengerichtet}+\text{kantengewurzelt}-\text{gerichtet-kantengewurzelt}.$$
Als erzeugende Funktion wird daraus
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
Die gesuchte Folge ist also
$$g(n)=\left[x^n\right]G(x).$$
Genau diese Identität wird in der Schlussphase des Programms ausgewertet.
Für \(n=3\) gibt es als Baumform nur einen Pfad der Länge \(2\). Bis auf Isomorphie bestimmt der mittlere Knoten die Adjazenzstruktur.
Ist der mittlere Knoten rot, bilden die beiden Blätter eine ungeordnete Multimenge aus \(\{R,B,Y\}\). Das sind
$$\binom{3+2-1}{2}=6$$
Möglichkeiten.
Ist der mittlere Knoten blau, erhält man dieselbe Zahl, also wieder \(6\).
Ist der mittlere Knoten gelb, müssen beide Nachbarn nichtgelb sein. Die Blätter bilden dann eine ungeordnete Multimenge aus \(\{R,B\}\), also
$$\binom{2+2-1}{2}=3.$$
Somit
$$g(3)=6+6+3=15,$$
genau wie in den Kontrollwerten der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst bauen sie Koeffiziententabellen für die gepflanzten Serien bis Größe \(10000\) auf. Beim Aufbau eines Objekts der Größe \(n\) werden die Multimengenterme an der Stelle \(n-1\) gelesen, weil die Wurzel selbst einen Knoten beiträgt.
Während dieses ersten Durchlaufs hält die Implementierung Quadratfaltungen der aggregierten Serien inkrementell aktuell. Diese vorberechneten quadratischen Terme werden anschließend wiederverwendet, um die Beiträge der Multimengen der Größe \(2\) und \(3\) effizient zu erhalten.
Im zweiten Durchlauf werden verschobene Serien für \(F(x^2)\), \(F(x^3)\) und \(F(x^4)\) erzeugt sowie die kubischen und quartischen Faltungsterme der Zyklusindex-Formeln berechnet. Daraus entstehen die vollständigen knotengerichteten Zählfunktionen.
Zum Schluss bildet die Implementierung die gerichteten und ungerichteten kantengewurzelten Serien, setzt
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
und liest den Koeffizienten von \(x^{10000}\) modulo \(10^9+7\) aus. Die C++-Version parallelisiert einige der größten Faltungen, mathematisch sind aber alle drei Sprachfassungen identisch.
Mit \(N=10000\) wird die Laufzeit von quadratischen Faltungen und den inkrementellen Updates der Quadratserien dominiert. Insgesamt ergibt sich \(O(N^2)\) Zeit. Gespeichert wird nur eine feste Anzahl von Koeffizientenfeldern der Länge \(N+1\), also \(O(N)\) Speicher.
Çözüm, \(n\) köşeli izinli etiketsiz renkli ağaçları sayıyor ve \(g(10000)\) değerini
$$10^9+7$$
modunda istiyor. Uygulamalardan çıkan renk kuralları şunlardır:
kırmızı köşelerin derecesi en fazla \(4\), mavi köşelerin derecesi en fazla \(3\), sarı köşelerin derecesi en fazla \(3\), ayrıca iki sarı köşe arasında kenar bulunamaz. İlk kontrol değerleri
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249$$
şeklindedir. \(10000\) düğüme kadar bütün izomorfi sınıflarını doğrudan üretmek mümkün olmadığı için program, sıradan üreteç fonksiyonları, çoklu kümeler için cycle-index formülleri ve ağaçlar için dissymmetry teoremi kullanır.
Sayım üç aşamada yapılır: önce planted ağaçlar, sonra köklenmiş ağaçlar, en sonda da köksüz sınıf elde edilir.
\(R(x)\), \(B(x)\) ve \(Y(x)\), ayırt edilmiş kök köşesi sırasıyla kırmızı, mavi ve sarı olan planted ağaçların sıradan üreteç fonksiyonları olsun. Planted ağaçta kökün üst tarafında ayırt edilmiş bir ebeveyn kenarı vardır; yani kökün bir bağlanma hakkı zaten kullanılmıştır.
Toplam serileri
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x)$$
diye tanımlayalım. Burada \(A(x)\) bütün planted ağaçları, \(N(x)\) ise kökü sarı olmayan planted ağaçları sayar. İkinci seri gerekir, çünkü sarı bir kök sarı bir komşuya bağlanamaz.
Ebeveyn kenarı bir derece yuvasını işgal ettiği için planted ağaç kökü ancak şu kadar çocuk alabilir:
kırmızı: \(0,1,2,3\), mavi: \(0,1,2\), sarı: \(0,1,2\) ama hepsi sarı olmayan çocuklar.
Köke takılan alt ağaçların sırası önemli değildir; dolayısıyla sıralı dizi değil çoklu küme sayılır. Sıradan üreteç fonksiyonlarında simetrik grupların cycle-index formülleri
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}$$
şeklindedir. Program tam olarak bu çoklu küme operatörlerini hesaplar.
Buna göre planted ağaç denklemleri
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right)$$
olur. Buradaki \(x\) kökün kendisini, sabit \(1\) ise çocuksuz olasılığı temsil eder.
Ağaç bir köşede köklendiğinde kök artık tam derece bütçesini kullanabilir. \(V_R(x)\), \(V_B(x)\), \(V_Y(x)\) sırasıyla kökü kırmızı, mavi, sarı olan köklenmiş ağaçların üreteç fonksiyonları olsun. O zaman
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right)$$
elde edilir. Toplam köklenmiş seri
$$V(x)=V_R(x)+V_B(x)+V_Y(x)$$
şeklindedir. Uygulamanın ikinci ana aşaması tam olarak budur.
Bir ağaç yönlü bir kenarda köklenirse, bu kenar ağacı sıralı iki planted ağaç parçasına ayırır. Renk yasağı olmasa \(A(x)^2\) gelirdi. Yasaklanan tek durum, iki açık kökün de sarı olmasıdır. Bu yüzden yönlü kenar-köklü seri
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2$$
olur.
Yönsüz kenar kökünde iki taraf artık sırasız bir çifttir. Burnside lemması
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}$$
formülünü verir. Buradaki \(A(x^2)\) ve \(Y(x^2)\) terimleri, iki yarının yer değiştirmesine sabit kalan durumları sayar: iki taraf aynı planted ağaç olmalı ve sarı-sarı durum yine çıkarılmalıdır.
Ağaçlar için klasik dissymmetry teoremi şunu söyler:
$$\text{köksüz}=\text{köşe-köklü}+\text{kenar-köklü}-\text{yönlü-kenar-köklü}.$$
Üreteç fonksiyonlarıyla bu,
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x)$$
demektir. İstenen dizi de
$$g(n)=\left[x^n\right]G(x)$$
olarak elde edilir. Son düzeltme aşaması programda tam bu eşitliği uygular.
\(n=3\) için tek ağaç biçimi uzunluğu \(2\) olan bir yoldur. İzomorfiye göre orta köşe bütün komşuluk yapısını belirler.
Orta köşe kırmızıysa, iki yaprak \(\{R,B,Y\}\) kümesinden seçilen sırasız bir çoklu küme oluşturur. Bunun sayısı
$$\binom{3+2-1}{2}=6$$
olur.
Orta köşe maviyse aynı hesap yine \(6\) verir.
Orta köşe sarıysa iki komşu da sarı olmayan renkte olmalıdır. Bu kez yapraklar \(\{R,B\}\) kümesinden seçilen sırasız bir çoklu kümedir ve
$$\binom{2+2-1}{2}=3$$
sonucu çıkar.
Dolayısıyla
$$g(3)=6+6+3=15,$$
ki bu, uygulamanın doğrulama değerleriyle aynıdır.
C++, Python ve Java uygulamaları aynı boru hattını izler. Önce \(10000\)'e kadar planted serilerin katsayı tabloları kurulur. Boyutu \(n\) olan bir nesne hesaplanırken çoklu küme katkıları \(n-1\) katsayısından okunur; çünkü kök tek başına bir köşe ekler.
Bu ilk geçiş sırasında uygulama, toplam planted serilerin kare konvolüsyonlarını artımlı biçimde güncel tutar. Böylece derece \(2\) ve derece \(3\) çoklu küme terimleri, daha önce hesaplanmış ikinci dereceden katkılar yeniden kullanılarak elde edilir.
İkinci geçişte \(F(x^2)\), \(F(x^3)\), \(F(x^4)\) karşılıkları olan kaydırılmış diziler oluşturulur; ayrıca cycle-index formüllerindeki kübik ve dördüncü dereceden konvolüsyon terimleri hesaplanır. Bunlar tam köklenmiş sayımları verir.
Son olarak uygulama yönlü kenar-köklü ve yönsüz kenar-köklü serileri kurar,
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x)$$
eşitliğini uygular ve \(x^{10000}\) katsayısını \(10^9+7\) modunda alır. C++ sürümü en büyük konvolüsyonların bir kısmını paralelleştirir; fakat üç dilde de kullanılan matematik aynıdır.
\(N=10000\) için baskın maliyet, karesel konvolüsyonlar ve kare serileri oluşturan artımlı güncellemelerdir. Toplam süre \(O(N^2)\) olur. Bellekte uzunluğu \(N+1\) olan sabit sayıda katsayı dizisi tutulduğu için alan kullanımı \(O(N)\)'dir.
La solución cuenta árboles coloreados no etiquetados y admisibles con \(n\) vértices, y pide el valor \(g(10000)\) módulo
$$10^9+7.$$
Las reglas de color codificadas por las implementaciones son:
los vértices rojos tienen grado como máximo \(4\), los azules como máximo \(3\), los amarillos como máximo \(3\), y una arista entre dos vértices amarillos está prohibida. Los primeros valores de control son
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
Enumerar directamente todas las clases de isomorfía hasta \(n=10000\) no es viable. Por eso el programa usa funciones generadoras ordinarias, fórmulas de índice cíclico para multiconjuntos y el teorema de disimetría para árboles.
El recuento se hace en tres capas: primero árboles plantados, luego árboles enraizados en un vértice y, al final, recuperación de los objetos no enraizados.
Sean \(R(x)\), \(B(x)\) y \(Y(x)\) las funciones generadoras ordinarias de los árboles plantados cuya raíz distinguida es roja, azul o amarilla. Un árbol plantado tiene una arista padre distinguida por encima de la raíz, así que una incidencia de la raíz ya está ocupada.
Definimos
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
Aquí \(A(x)\) representa todos los árboles plantados y \(N(x)\) los que tienen raíz no amarilla. Esta segunda serie es necesaria porque una raíz amarilla no puede estar conectada con un vecino amarillo.
Como la arista padre ya consume una posición, la raíz de un árbol plantado puede recibir solo
rojo: \(0,1,2,3\) hijos, azul: \(0,1,2\) hijos, amarillo: \(0,1,2\) hijos no amarillos.
Cuando a la raíz se le adjunta una colección no ordenada de subárboles, hay que contar multiconjuntos y no tuplas ordenadas. Para funciones generadoras ordinarias, las fórmulas de índice cíclico de los grupos simétricos dan
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
Esos son exactamente los operadores de multiconjuntos que evalúa el programa.
Por tanto, las ecuaciones de los árboles plantados son
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
El factor \(x\) cuenta la propia raíz y la constante \(1\) representa el caso sin hijos.
Si el árbol está enraizado en un vértice, la raíz recupera todo su presupuesto de grado. Sean \(V_R(x)\), \(V_B(x)\) y \(V_Y(x)\) las funciones generadoras de los árboles admisibles enraizados en un vértice con raíz roja, azul o amarilla. Entonces
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
Sumando los tres colores de raíz obtenemos
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
Esta es la segunda gran fase del cálculo.
Si enraizamos el árbol en una arista orientada, la arista lo divide en un par ordenado de árboles plantados. Sin restricción de color aparecería \(A(x)^2\). El único caso prohibido es que las dos raíces expuestas sean amarillas, así que la serie de arista-orientada es
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
Para una arista no orientada, los dos lados forman un par no ordenado. El lema de Burnside da
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
Los términos \(A(x^2)\) y \(Y(x^2)\) cuentan los puntos fijos al intercambiar ambos lados: las dos mitades deben ser idénticas, y el caso amarillo-amarillo sigue excluyéndose.
Para árboles, el teorema clásico de disimetría afirma que
$$\text{no enraizado}=\text{enraizado en vértice}+\text{enraizado en arista}-\text{enraizado en arista orientada}.$$
En funciones generadoras, esto se convierte en
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
La sucesión buscada es entonces
$$g(n)=\left[x^n\right]G(x).$$
Esa identidad es exactamente la corrección final que aplican las implementaciones.
Para \(n=3\), la única forma de árbol es un camino de longitud \(2\). Hasta isomorfismo, el vértice central determina toda la estructura de adyacencia.
Si el vértice central es rojo, las dos hojas forman un multiconjunto no ordenado tomado de \(\{R,B,Y\}\). Hay
$$\binom{3+2-1}{2}=6$$
posibilidades.
Si el vértice central es azul, el mismo recuento vuelve a dar \(6\).
Si el vértice central es amarillo, ambos vecinos deben ser no amarillos. En ese caso las hojas forman un multiconjunto no ordenado de \(\{R,B\}\), lo que produce
$$\binom{2+2-1}{2}=3.$$
Por tanto,
$$g(3)=6+6+3=15,$$
en acuerdo con los valores de validación usados por la implementación.
Las implementaciones en C++, Python y Java siguen la misma tubería. Primero construyen tablas de coeficientes para las series plantadas hasta tamaño \(10000\). Cuando se monta un objeto de tamaño \(n\), las contribuciones de multiconjuntos se leen en tamaño \(n-1\), porque la raíz aporta un vértice.
Durante esa primera pasada, la implementación mantiene de forma incremental las convoluciones cuadráticas de las series plantadas agregadas. Esos términos cuadrados ya disponibles se reutilizan para obtener con eficiencia las contribuciones de multiconjuntos de tamaño \(2\) y \(3\).
En la segunda pasada se construyen copias desplazadas que representan \(F(x^2)\), \(F(x^3)\) y \(F(x^4)\), junto con los términos cúbicos y cuárticos exigidos por las fórmulas de índice cíclico. De ahí salen los recuentos completos enraizados en vértice.
Al final, la implementación forma las series enraizadas en arista orientada y no orientada, aplica
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
y extrae el coeficiente de \(x^{10000}\) módulo \(10^9+7\). La versión en C++ paraleliza algunas de las convoluciones más grandes, pero la fórmula matemática es la misma en los tres lenguajes.
Sea \(N=10000\). El trabajo dominante proviene de convoluciones cuadráticas y de las actualizaciones incrementales que construyen las series cuadradas. En conjunto, el tiempo es \(O(N^2)\). Solo se almacenan un número fijo de arreglos de coeficientes de longitud \(N+1\), por lo que la memoria es \(O(N)\).
这套解法计算满足限制条件的无标号彩色树，并要求得到 \(g(10000)\) 在
$$10^9+7$$
模数下的值。由实现中的递推关系可以读出颜色规则：
红色顶点的度数最多为 \(4\)，蓝色顶点的度数最多为 \(3\)，黄色顶点的度数最多为 \(3\)，并且不允许出现一条连接两个黄色顶点的边。前几个校验值是
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
如果直接枚举 \(10000\) 个顶点以内的所有彩色树并逐一做同构判定，代价会高得不可接受。因此程序改用普通生成函数、对称群循环指数给出的多重集公式，以及树的 dissymmetry theorem 来完成计数。
整个计数过程分成三层：先数 planted tree，再数以顶点为根的树，最后恢复无根对象。
设 \(R(x)\)、\(B(x)\)、\(Y(x)\) 分别表示根顶点颜色为红、蓝、黄的 planted tree 的普通生成函数。所谓 planted tree，可以理解为根的上方预留了一条“父边”，因此根顶点已经占用了一个连接位置。
再定义两个总和级数
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
其中 \(A(x)\) 表示所有 planted tree，\(N(x)\) 表示根不是黄色的 planted tree。之所以需要 \(N(x)\)，是因为黄色顶点不能与黄色顶点相邻，所以黄色根只能连接到红色或蓝色根的子树。
由于父边已经占掉了一个度数位置，planted tree 的根还能接收的子树个数只有：
红色根可以接 \(0,1,2,3\) 棵子树，蓝色根可以接 \(0,1,2\) 棵子树，黄色根可以接 \(0,1,2\) 棵且这些子树的根都不能是黄色。
根下面挂接的是一组无序子树，因此不能把它们当成有序序列来数，而要当成多重集来数。普通生成函数下，来自对称群的循环指数公式给出
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
这些公式正是程序里出现的二元、三元、四元无序挂接项。
于是 planted tree 满足
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
这里前面的 \(x\) 代表根顶点本身，常数项 \(1\) 表示根可以没有任何子树。
当树根放在一个真正的顶点上时，根不再预留父边，因此它可以使用完整的度数上限。设 \(V_R(x)\)、\(V_B(x)\)、\(V_Y(x)\) 分别表示根颜色为红、蓝、黄的顶点根树的生成函数，则有
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
把三种根颜色加起来，就得到全部顶点根树的生成函数
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
这对应实现中的第二个大阶段。
如果把树根放在一条有向边上，这条边会把整棵树拆成一个有序的 planted tree 对。若没有颜色限制，对应的生成函数就是 \(A(x)^2\)。但其中“左右两端根都为黄色”的情况必须删除，因此有向边根树的生成函数为
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
若树根放在一条无向边上，那么两侧不再是有序对，而是无序对。根据 Burnside 引理，得到
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
其中 \(A(x^2)\) 和 \(Y(x^2)\) 对应交换两侧后保持不变的情况，也就是左右两边完全相同的 planted tree；同时仍然要去掉黄色-黄色那一类固定点。
对树来说，经典的 dissymmetry theorem 告诉我们：
$$\text{无根树}=\text{顶点根树}+\text{无向边根树}-\text{有向边根树}.$$
写成生成函数就是
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
于是目标数列满足
$$g(n)=\left[x^n\right]G(x).$$
程序最后的修正部分正是在逐项实现这条公式。
当 \(n=3\) 时，唯一的树形只有一条长度为 \(2\) 的路径。按无标号同构分类，中间那个顶点的颜色决定了整个对象。
如果中间顶点是红色，那么两侧叶子构成从 \(\{R,B,Y\}\) 中选出的一个无序多重集，其数量为
$$\binom{3+2-1}{2}=6.$$
如果中间顶点是蓝色，完全同理，也是 \(6\) 种。
如果中间顶点是黄色，那么它的两个邻点都不能是黄色，因此叶子只能从 \(\{R,B\}\) 中选成一个无序多重集，数量为
$$\binom{2+2-1}{2}=3.$$
因此总数是
$$g(3)=6+6+3=15,$$
正好与实现中使用的校验值一致。
C++、Python 和 Java 三份实现遵循完全相同的流程。第一步是把 planted tree 的系数表一直构造到大小 \(10000\)。在构造大小为 \(n\) 的对象时，程序会读取大小 \(n-1\) 的多重集项，因为根本身已经贡献了一个顶点。
在这一阶段里，实现会增量维护若干平方卷积结果，也就是聚合 planted 系列与自身的二次组合项。这样在后面求二元和三元无序挂接时，可以直接复用这些已知量，而不必每次从头展开。
第二步中，程序显式构造 \(F(x^2)\)、\(F(x^3)\)、\(F(x^4)\) 这些“缩放后”系列对应的系数数组，再配合立方卷积和四次卷积项，完整实现循环指数公式中的所有组成部分，从而得到顶点根树的计数。
最后，程序形成有向边根树和无向边根树的系数，应用
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
并取出 \(x^{10000}\) 的系数，再对 \(10^9+7\) 取模。C++ 版本对几项最大的卷积做了并行化，但三种语言实现的数学内容完全一致。
记 \(N=10000\)。主要耗时来自二次卷积以及构造平方系列时的增量更新，总时间复杂度为 \(O(N^2)\)。程序只保存固定数量、长度为 \(N+1\) 的系数数组，因此空间复杂度为 \(O(N)\)。
Решение считает допустимые неразмеченные раскрашенные деревья на \(n\) вершинах и требует найти \(g(10000)\) по модулю
$$10^9+7.$$
Из рекуррентных формул в реализации видно, что действуют такие ограничения:
красная вершина имеет степень не больше \(4\), синяя не больше \(3\), жёлтая не больше \(3\), и ребро между двумя жёлтыми вершинами запрещено. Первые контрольные значения равны
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
Прямой перебор всех классов изоморфизма до \(10000\) вершин нереалистичен. Поэтому программа использует обычные производящие функции, формулы циклического индекса для мультимножеств и теорему о диссимметрии для деревьев.
Подсчёт устроен в три слоя: сначала считаются planted trees, затем деревья с корнем в вершине, после чего восстанавливается неукоренённый класс.
Пусть \(R(x)\), \(B(x)\) и \(Y(x)\) обозначают обычные производящие функции planted trees, у которых выделенная корневая вершина соответственно красная, синяя или жёлтая. У planted tree над корнем уже есть выделенное родительское ребро, то есть один инцидентный корню слот уже занят.
Введём суммарные серии
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
Здесь \(A(x)\) описывает все planted trees, а \(N(x)\) только те, у которых корень не жёлтый. Вторая серия нужна потому, что жёлтая вершина не может быть соседней с жёлтой.
Так как родительское ребро уже занимает одну степень, корень planted tree может иметь только
для красного: \(0,1,2,3\) детей, для синего: \(0,1,2\) детей, для жёлтого: \(0,1,2\) детей и все они должны быть нежёлтыми.
Поддеревья, прикреплённые к корню, образуют неупорядоченную коллекцию, поэтому считать нужно мультимножества, а не упорядоченные кортежи. Для обычных производящих функций формулы циклического индекса симметрических групп дают
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
Именно эти операторы мультимножеств вычисляет программа.
Отсюда уравнения для planted trees:
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
Множитель \(x\) отвечает за сам корень, а константа \(1\) соответствует случаю без детей.
Если корень ставится в вершину, а не на родительское ребро, то вершина снова получает полный допустимый бюджет степени. Обозначим через \(V_R(x)\), \(V_B(x)\), \(V_Y(x)\) производящие функции допустимых деревьев с корнем в вершине соответствующего цвета. Тогда
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
Полная серия деревьев с корнем в вершине равна
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
Это ровно второй основной этап вычисления.
Если укоренить дерево в ориентированном ребре, оно распадается на упорядоченную пару planted trees. Без цветового ограничения получилось бы \(A(x)^2\). Нужно исключить только случай, когда оба открытых корня жёлтые, поэтому
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
Для неориентированного ребра стороны образуют уже неупорядоченную пару. По лемме Бёрнсайда
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
Слагаемые \(A(x^2)\) и \(Y(x^2)\) описывают неподвижные точки перестановки двух половин: обе половины должны совпадать, и случай жёлтый-жёлтый по-прежнему исключается.
Для деревьев классическая теорема о диссимметрии утверждает:
$$\text{неукоренённые}=\text{с корнем в вершине}+\text{с корнем в ребре}-\text{с корнем в ориентированном ребре}.$$
На языке производящих функций это даёт
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
Следовательно, искомая последовательность задаётся формулой
$$g(n)=\left[x^n\right]G(x).$$
Именно эту формулу реализует финальная поправка в программе.
При \(n=3\) возможна только одна форма дерева: путь длины \(2\). С точностью до изоморфизма всё определяется цветом средней вершины.
Если средняя вершина красная, то два листа образуют неупорядоченное мультимножество из \(\{R,B,Y\}\). Таких мультимножеств
$$\binom{3+2-1}{2}=6.$$
Если средняя вершина синяя, получается тот же результат, снова \(6\).
Если средняя вершина жёлтая, оба соседа обязаны быть нежёлтыми. Тогда листья образуют неупорядоченное мультимножество из \(\{R,B\}\), а его число равно
$$\binom{2+2-1}{2}=3.$$
Итак,
$$g(3)=6+6+3=15,$$
что совпадает с проверочными значениями, используемыми в реализации.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они строят таблицы коэффициентов для planted series до размера \(10000\). Когда строится объект размера \(n\), вклады мультимножеств читаются при размере \(n-1\), поскольку сам корень уже даёт одну вершину.
Во время этого первого прохода реализация инкрементально поддерживает квадратные свёртки агрегированных planted series. Эти заранее посчитанные квадратичные члены затем повторно используются для эффективного получения вкладов мультимножеств размера \(2\) и \(3\).
На втором проходе строятся сдвинутые массивы, соответствующие \(F(x^2)\), \(F(x^3)\) и \(F(x^4)\), а также кубические и четвёртые свёрточные члены из формул циклического индекса. Из них формируются полные счётчики деревьев с корнем в вершине.
После этого реализация составляет серии для ориентированного и неориентированного корня в ребре, применяет
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
и извлекает коэффициент при \(x^{10000}\) по модулю \(10^9+7\). Версия на C++ распараллеливает часть самых крупных свёрток, но математическая формула одинакова во всех трёх языках.
Пусть \(N=10000\). Основное время уходит на квадратичные свёртки и на инкрементальные обновления, из которых строятся квадратные серии. Поэтому общее время равно \(O(N^2)\). Хранится лишь фиксированное число массивов коэффициентов длины \(N+1\), так что память составляет \(O(N)\).
يحسب هذا الحل عدد الأشجار الملوّنة غير الموسومة التي تحقق القيود المطلوبة، ثم يطلب قيمة \(g(10000)\) بترديد
$$10^9+7.$$
ومن العلاقات العودية في التنفيذ يمكن قراءة قواعد الألوان الآتية:
درجة الرأس الأحمر لا تتجاوز \(4\)، ودرجة الرأس الأزرق لا تتجاوز \(3\)، ودرجة الرأس الأصفر لا تتجاوز \(3\)، كما أن وجود ضلع يصل بين رأسين أصفرين ممنوع. وقيم التحقق الأولى هي
$$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$$
التعداد المباشر لجميع أصناف التشاكل حتى \(10000\) رأس غير عملي تمامًا، لذلك يعتمد البرنامج على الدوال المولدة العادية، وصيغ مؤشر الدورات الخاصة بالمتعددات غير المرتبة، ثم على مبرهنة عدم التناظر الخاصة بالأشجار.
تجري عملية العد على ثلاث مراحل: أولًا عد الأشجار المزروعة، ثم الأشجار المجذّرة عند رأس، ثم استرجاع الأجسام غير المجذّرة.
لتكن \(R(x)\) و\(B(x)\) و\(Y(x)\) هي الدوال المولدة العادية للأشجار المزروعة التي يكون رأس الجذر المميز فيها أحمر أو أزرق أو أصفر على الترتيب. في الشجرة المزروعة توجد ضلع أب مميز فوق الجذر، وهذا يعني أن إحدى إمكانات الاتصال عند الجذر مستعملة مسبقًا.
نعرّف الآن السلسلتين الجامعتين
$$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$$
تمثل \(A(x)\) جميع الأشجار المزروعة، بينما تمثل \(N(x)\) الأشجار المزروعة التي لا يكون جذرها أصفر. والحاجة إلى \(N(x)\) نابعة من أن الجذر الأصفر لا يجوز أن يتصل بجار أصفر.
وبما أن ضلع الأب قد استهلك موضعًا واحدًا من درجة الجذر، فإن جذر الشجرة المزروعة لا يستطيع أن يستقبل إلا:
للأحمر: \(0,1,2,3\) أبناء، وللأزرق: \(0,1,2\) أبناء، وللأصفر: \(0,1,2\) أبناء بشرط أن تكون جذورهم غير صفراء.
عندما نعلّق مجموعة غير مرتبة من الأشجار الفرعية تحت الجذر، فنحن لا نعد ترتيبات مرتبة بل متعددات غير مرتبة. وبالنسبة إلى الدوال المولدة العادية تعطينا صيغ مؤشر الدورات للزمر التناظرية ما يلي:
$$\Phi_1(F)=F(x),$$
$$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$$
$$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$$
$$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$$
وهذه هي بالضبط مؤثرات المتعددات غير المرتبة التي يحسبها التنفيذ.
ومن ثم تصبح معادلات الأشجار المزروعة
$$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$$
$$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$$
ويمثل العامل \(x\) الجذر نفسه، أما الثابت \(1\) فيمثل حالة عدم وجود أبناء.
عندما يكون الجذر رأسًا فعليًا داخل الشجرة، فإنه يستعيد حد الدرجة الكامل الخاص به. ولتكن \(V_R(x)\) و\(V_B(x)\) و\(V_Y(x)\) هي الدوال المولدة للأشجار المسموح بها المجذّرة عند رأس أحمر أو أزرق أو أصفر. عندئذٍ نحصل على
$$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$$
$$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$$
$$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$$
وبجمع الألوان الثلاثة نحصل على السلسلة الكلية للأشجار المجذّرة عند رأس:
$$V(x)=V_R(x)+V_B(x)+V_Y(x).$$
وهذه هي المرحلة الكبرى الثانية في التنفيذ.
إذا جذرنا الشجرة على ضلع موجه، فإن هذا الضلع يقسمها إلى زوج مرتب من الأشجار المزروعة. ومن دون قيد اللون سنحصل على \(A(x)^2\). لكن الحالة التي يكون فيها الجذران المكشوفان أصفرين ممنوعة، ولذلك تكون سلسلة الأشجار المجذّرة على ضلع موجه
$$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$$
أما إذا كان الجذر على ضلع غير موجه، فإن الجانبين يشكلان زوجًا غير مرتب. وتعطي لمّة بيرنسايد
$$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$$
والحدان \(A(x^2)\) و\(Y(x^2)\) يصفان النقاط الثابتة تحت تبديل الجانبين: يجب أن يكون النصفان متماثلين تمامًا، مع استمرار استبعاد حالة أصفر-أصفر.
بالنسبة إلى الأشجار تقول مبرهنة عدم التناظر الكلاسيكية إن
$$\text{unrooted}=\text{vertex-rooted}+\text{edge-rooted}-\text{directed-edge-rooted}.$$
وبلغة الدوال المولدة تصبح هذه الهوية
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$$
إذن المتتالية المطلوبة تعطى بالمعادلة
$$g(n)=\left[x^n\right]G(x).$$
وهذا هو بالضبط التصحيح النهائي الذي تطبقه الشيفرة.
عندما \(n=3\)، لا يوجد إلا شكل شجري واحد هو مسار طوله \(2\). وحتى التشاكل، يحدد لون الرأس الأوسط الجسم كله.
إذا كان الرأس الأوسط أحمر، فإن الورقتين تشكلان متعددًا غير مرتب مأخوذًا من \(\{R,B,Y\}\)، وعدده
$$\binom{3+2-1}{2}=6.$$
وإذا كان الرأس الأوسط أزرق، نحصل على العدد نفسه، أي \(6\).
أما إذا كان الرأس الأوسط أصفر، فيجب أن يكون الجاران غير أصفرين، فتتشكل الورقتان من متعدد غير مرتب مأخوذ من \(\{R,B\}\)، وعدده
$$\binom{2+2-1}{2}=3.$$
إذًا
$$g(3)=6+6+3=15,$$
وهو ما يطابق قيم التحقق المستخدمة في التنفيذ.
تتبع تطبيقات C++ وPython وJava المسار نفسه. في البداية تبني جداول المعاملات الخاصة بسلاسل الأشجار المزروعة حتى الحجم \(10000\). وعند بناء جسم حجمه \(n\)، تقرأ مساهمات المتعددات غير المرتبة عند الحجم \(n-1\)، لأن الجذر نفسه يضيف رأسًا واحدًا.
وخلال هذا المرور الأول تحافظ الشيفرة بشكل تزايدي على التفافات تربيعية للسلاسل المجمعة الخاصة بالأشجار المزروعة. ثم يعاد استخدام هذه الحدود التربيعية المحسوبة مسبقًا من أجل الحصول بكفاءة على مساهمات المتعددات ذات الحجم \(2\) و\(3\).
وفي المرور الثاني تُبنى نسخ مزاحة تمثل \(F(x^2)\) و\(F(x^3)\) و\(F(x^4)\)، إلى جانب حدود الالتفاف التكعيبية والرباعية اللازمة لصيغ مؤشر الدورات. ومن هذه الحدود تتكون أعداد الأشجار المجذّرة عند رأس بالكامل.
وفي النهاية تشكّل الشيفرة سلاسل التجذير على ضلع موجه وعلى ضلع غير موجه، ثم تطبق
$$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$$
وتستخرج معامل \(x^{10000}\) بترديد \(10^9+7\). وتقوم نسخة C++ بموازاة بعض أكبر عمليات الالتفاف، لكن الصيغة الرياضية نفسها مشتركة بين اللغات الثلاث.
إذا رمزنا إلى \(10000\) بـ \(N\)، فإن الكلفة المهيمنة تأتي من الالتفافات التربيعية ومن التحديثات التزايدية التي تبني السلاسل المربعة. لذلك يكون الزمن الكلي \(O(N^2)\). أما الذاكرة فتبقى \(O(N)\)، لأن التنفيذ يحتفظ بعدد ثابت من مصفوفات المعاملات ذات الطول \(N+1\).