Let \(U(n)\) denote the number of unlabeled unrooted trees with \(n\) vertices such that every edge joins vertices of different degrees. These are the peerless trees. The required answer is
$$\sum_{n=3}^{50} U(n).$$
The first values produced by the recurrence are \(U(3)=1\), \(U(4)=1\), \(U(5)=2\), and \(U(7)=6\), and one useful checkpoint is
$$\sum_{n=3}^{10} U(n)=74.$$
The difficulty is that these are free, unlabeled trees, so the children of a vertex form an unordered collection. The solution therefore counts isomorphism types by multisets of rooted subtrees instead of trying to generate adjacency structures directly.
The implementations first count rooted versions of the objects and only at the end recover the free trees. The key invariant is local: if an edge connects a vertex of degree \(d\), then the subtree attached across that edge must have root degree different from \(d\).
Let \(P_d(n)\) be the number of planted peerless trees with \(n\) vertices whose root has degree \(d\). “Planted” means that the root is viewed as having a distinguished parent edge above it. That reserved edge already contributes 1 to the root degree, so inside the subtree the root has exactly \(d-1\) children.
Also define the total number of planted trees of size \(n\) by
$$T(n)=\sum_{e\ge 1} P_e(n).$$
If the parent vertex has degree \(d\), then among planted trees of size \(s\) only those whose root degree is not \(d\) may be attached. Hence the number of admissible child types of size \(s\) is
$$A_d(s)=T(s)-P_d(s).$$
This is the whole degree constraint at the attachment point: every internal edge inside the child subtree was already peerless before the attachment, so only the new parent-child edge has to be checked.
Fix \(d\) and \(n\). To build an object counted by \(P_d(n)\), choose an unordered multiset of \(d-1\) admissible child trees whose total size is \(n-1\). If \(q_s\) children have size \(s\), then the constraints are
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
For a fixed size \(s\), there are \(A_d(s)\) available isomorphism types, and choosing \(q_s\) children from those types with repetition allowed gives the stars-and-bars factor
$$\binom{A_d(s)+q_s-1}{q_s}.$$
Therefore
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
An equivalent generating-function form is
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
The implementations do not expand that product symbolically; they extract the coefficient directly by dynamic programming over the pair “number of chosen children” and “total size used”.
Now root the tree at an actual vertex instead of a planted edge. If the root degree is \(d\), then the root has \(d\) children, not \(d-1\). Once the admissible counts \(A_d(s)\) are known, the same multiset mechanism applies:
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
where \(V(n)\) counts peerless trees on \(n\) vertices with a distinguished root vertex.
Next root the tree at an oriented edge. Removing that directed edge splits the tree into an ordered pair of planted trees of sizes \(\ell\) and \(n-\ell\). If we temporarily ignore the degree condition on the marked edge, this gives
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
When the two halves are glued back together, their roots become adjacent, so equal root degrees are forbidden. The bad pairs are exactly
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Thus the number of directed-edge-rooted peerless trees is
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Let \(E(n)\) be the number of peerless trees rooted at an undirected edge. For trees, the standard dissymmetry identity gives
$$U(n)=V(n)+E(n)-D(n).$$
In a peerless tree the endpoints of a marked edge always have different degrees, so the two orientations of that edge are genuinely distinct. Therefore every edge-rooted object corresponds to exactly two directed-edge-rooted objects, which means
$$D(n)=2E(n).$$
Substituting into the dissymmetry identity yields the formula used by the implementations:
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
The recurrence gives \(V(5)=6\) and \(D(5)=8\), so
$$U(5)=6-\frac{8}{2}=2.$$
Those two trees are the 4-star and the unique tree with degree sequence \(3,2,1,1,1\). The 5-vertex path is excluded because its middle edge joins two degree-2 vertices. This small case shows why the method counts rooted versions first and then corrects the overcount caused by marked edges.
The C++, Python, and Java implementations fill the planted counts in increasing order of \(n\). When size \(n\) is processed, every value \(P_d(s)\) and \(T(s)\) with \(s<n\) is already known, so the admissible counts \(A_d(s)=T(s)-P_d(s)\) are available immediately.
For each requested root degree, the implementation runs a two-dimensional DP whose state records how many children have been chosen and what total subtree size they contribute. Processing the child sizes one by one reproduces the product of binomial factors \(\binom{A_d(s)+q_s-1}{q_s}\) without enumerating any trees explicitly.
After the planted table is complete, the same DP is reused for the vertex-rooted counts \(V(n)\). The directed-edge counts \(D(n)\) are then computed from the convolution formula above, followed by the subtraction of same-degree pairs. Finally the implementation applies \(U(n)=V(n)-D(n)/2\) for each \(n\) and adds \(U(3)+U(4)+\cdots+U(50)\). All arithmetic is exact integer arithmetic.
Let \(N=50\). The stored tables \(P_d(n)\), \(T(n)\), \(V(n)\), and \(U(n)\) require \(O(N^2)\) memory overall, and each individual multiset DP uses another \(O(N^2)\) working table.
The dominant cost is the repeated coefficient-extraction DP for the planted and vertex-rooted states. A safe coarse upper bound for the full program is \(O(N^6)\) time; the directed-edge correction is only \(O(N^3)\) and is smaller. Because \(N\) is just 50 and many impossible states are skipped immediately, the exact computation is entirely practical.
Sei \(U(n)\) die Anzahl unlabeleter, ungerichteter Bäume mit \(n\) Knoten, in denen jede Kante Knoten unterschiedlicher Grade verbindet. Das sind die peerless trees. Gesucht ist
$$\sum_{n=3}^{50} U(n).$$
Die Rekursion liefert unter anderem \(U(3)=1\), \(U(4)=1\), \(U(5)=2\) und \(U(7)=6\), sowie als nützliche Kontrolle
$$\sum_{n=3}^{10} U(n)=74.$$
Die Schwierigkeit besteht darin, dass freie, unlabelte Bäume ungeordnete Objekte sind: Die Kinder eines Knotens bilden keine Liste, sondern eine ungeordnete Menge mit Wiederholungen. Deshalb zählt die Lösung Isomorphietypen über Multimengen von Wurzelunterbäumen.
Die Implementierungen zählen zuerst geeignete gerootete Varianten und gewinnen erst am Ende die freien Bäume zurück. Die entscheidende lokale Invariante lautet: Liegt an einer Kante ein Knoten vom Grad \(d\), dann muss der auf der anderen Seite angehängte Teilbaum an seiner Wurzel einen von \(d\) verschiedenen Grad besitzen.
Sei \(P_d(n)\) die Anzahl gepflanzter peerless Bäume mit \(n\) Knoten, deren Wurzel Grad \(d\) hat. „Gepflanzt“ bedeutet, dass über der Wurzel eine ausgezeichnete Elternkante mitgedacht wird. Diese reservierte Kante zählt bereits zum Wurzelgrad, also hat die Wurzel innerhalb des Teilbaums genau \(d-1\) Kinder.
Weiter definieren wir die Gesamtzahl gepflanzter Bäume der Größe \(n\) durch
$$T(n)=\sum_{e\ge 1} P_e(n).$$
Hat der Elternknoten Grad \(d\), dann dürfen von den gepflanzten Bäumen der Größe \(s\) genau diejenigen angehängt werden, deren Wurzelgrad nicht \(d\) ist. Also ist die Anzahl zulässiger Kindtypen der Größe \(s\)
$$A_d(s)=T(s)-P_d(s).$$
Mehr muss an der Klebestelle nicht geprüft werden: Jede innere Kante des Kindteilbaums war schon vorher peerless, also ist nur die neu entstehende Eltern-Kind-Kante relevant.
Fixiere \(d\) und \(n\). Um ein Objekt aus \(P_d(n)\) zu bauen, wählen wir eine ungeordnete Multimenge aus \(d-1\) zulässigen Kindbäumen mit Gesamtgröße \(n-1\). Wenn \(q_s\) Kinder die Größe \(s\) haben, gelten
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
Für eine feste Größe \(s\) gibt es \(A_d(s)\) verfügbare Isomorphietypen. Die Anzahl der Möglichkeiten, daraus \(q_s\) Kinder mit Wiederholung zu wählen, ist
$$\binom{A_d(s)+q_s-1}{q_s}.$$
Daher
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
Äquivalent kann man das als Koeffizientenextraktion schreiben:
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
Die Implementierungen expandieren dieses Produkt nicht symbolisch, sondern berechnen den Koeffizienten direkt per dynamischer Programmierung über „wie viele Kinder sind schon gewählt?“ und „welche Gesamtgröße ist schon erreicht?“.
Nun wird an einem echten Knoten statt an einer gepflanzten Kante gewurzelt. Hat die Wurzel Grad \(d\), so besitzt sie \(d\) Kinder und nicht \(d-1\). Sobald \(A_d(s)\) bekannt ist, gilt derselbe Multimengenmechanismus:
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
wobei \(V(n)\) peerless Bäume mit \(n\) Knoten und ausgezeichneter Wurzel zählt.
Als Nächstes wird an einer orientierten Kante gewurzelt. Entfernt man diese gerichtete Kante, zerfällt der Baum in ein geordnetes Paar gepflanzter Bäume der Größen \(\ell\) und \(n-\ell\). Ignoriert man zunächst die Gradbedingung über der Schnittkante, erhält man
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
Beim Wiederzusammenkleben werden die beiden Wurzeln benachbart, also sind gleiche Wurzelgrade verboten. Die unzulässigen Paare sind genau
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Damit ist die Anzahl gerichteter-kantenwurzeliger peerless Bäume
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Sei \(E(n)\) die Anzahl peerless Bäume mit ausgezeichneter ungerichteter Kante. Für Bäume liefert die Dissymmetrie-Identität
$$U(n)=V(n)+E(n)-D(n).$$
In einem peerless Baum haben die Endpunkte einer markierten Kante immer verschiedene Grade, daher sind ihre beiden Orientierungen wirklich verschieden. Also entspricht jedes kantengewurzelte Objekt genau zwei gerichteten-kantengewurzelten Objekten, also
$$D(n)=2E(n).$$
Eingesetzt ergibt das die in den Implementierungen verwendete Formel
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
Die Rekursion ergibt \(V(5)=6\) und \(D(5)=8\). Also
$$U(5)=6-\frac{8}{2}=2.$$
Diese beiden Bäume sind der 4-Stern und der eindeutige Baum mit Gradfolge \(3,2,1,1,1\). Der Pfad auf 5 Knoten ist ausgeschlossen, weil seine mittlere Kante zwei Knoten vom Grad 2 verbindet. Das kleine Beispiel zeigt gut den Gesamtplan: Zuerst sind die gerooteten Objekte einfach zu zählen, danach entfernt eine Korrektur die Mehrfachzählung über markierte Kanten.
Die C++-, Python- und Java-Implementierungen füllen die gepflanzten Zählwerte in aufsteigender Reihenfolge von \(n\). Wenn Größe \(n\) bearbeitet wird, sind alle Werte \(P_d(s)\) und \(T(s)\) für \(s<n\) bereits bekannt, also auch sofort die zulässigen Anzahlen \(A_d(s)=T(s)-P_d(s)\).
Für jeden gewünschten Wurzelgrad läuft eine zweidimensionale DP, deren Zustand speichert, wie viele Kinder bereits gewählt wurden und welche Gesamtgröße diese Kinder haben. Das schrittweise Verarbeiten der Kindgrößen reproduziert genau das Produkt der Binomialfaktoren \(\binom{A_d(s)+q_s-1}{q_s}\), ohne je Bäume explizit aufzuzählen.
Nachdem die gepflanzte Tabelle fertig ist, wird dieselbe DP für die knotenwurzeligen Zählungen \(V(n)\) wiederverwendet. Die gerichteten Kantenzählungen \(D(n)\) entstehen dann aus der Faltungsformel oben und der anschließenden Subtraktion der gleichgradigen Paare. Zum Schluss setzt die Implementierung für jedes \(n\) die Beziehung \(U(n)=V(n)-D(n)/2\) ein und addiert \(U(3)+U(4)+\cdots+U(50)\). Die gesamte Rechnung bleibt exakte Ganzzahlarithmetik.
Sei \(N=50\). Die gespeicherten Tabellen \(P_d(n)\), \(T(n)\), \(V(n)\) und \(U(n)\) benötigen insgesamt \(O(N^2)\) Speicher, und jede einzelne Multimengen-DP verwendet zusätzlich eine Arbeitstabelle der Größe \(O(N^2)\).
Der dominante Aufwand liegt in den wiederholten Koeffizienten-DPs für die gepflanzten und knotenwurzeligen Zustände. Eine sichere grobe obere Schranke für das Gesamtprogramm ist \(O(N^6)\) Laufzeit; die Korrektur über gerichtete Kanten kostet nur \(O(N^3)\) und ist kleiner. Da \(N=50\) sehr klein ist und viele unmögliche Zustände sofort übersprungen werden, ist die exakte Berechnung problemlos praktikabel.
\(U(n)\), \(n\) düğümlü, etiketsiz ve köksüz ağaçlar arasında her kenarın uçlarında farklı dereceler bulunanların sayısı olsun. Bunlar peerless tree olarak adlandırılıyor. İstenen değer
$$\sum_{n=3}^{50} U(n).$$
Özyineleme ilk olarak \(U(3)=1\), \(U(4)=1\), \(U(5)=2\) ve \(U(7)=6\) değerlerini verir; ayrıca yararlı bir kontrol de
$$\sum_{n=3}^{10} U(n)=74$$
eşitliğidir. Zorluk, bunların serbest ve etiketsiz ağaçlar olmasıdır; yani bir düğümün çocukları sıralı değil, tekrara izin veren düzensiz bir çoklu küme oluşturur. Bu yüzden çözüm, ağaçları tek tek üretmek yerine köklü alt ağaç tiplerinin çoklu kümelerini sayar.
Uygulamalar önce köklü sürümleri sayıyor, köksüz ağaç sayısını ise en sonda geri çıkarıyor. Temel yerel değişmez şudur: Derecesi \(d\) olan bir düğüme bağlanan alt ağacın kök derecesi \(d\) olamaz.
\(P_d(n)\), kök derecesi \(d\) olan ve \(n\) düğüm içeren planted peerless ağaç sayısı olsun. Buradaki “planted” ifadesi, kökün üstünde ayırt edilmiş bir ebeveyn kenarı varmış gibi düşünülmesi demektir. Bu ayrılmış kenar kökün derecesine zaten 1 katkı yaptığı için, alt ağacın içinde kökün gerçek çocuk sayısı \(d-1\) olur.
Ayrıca boyutu \(n\) olan toplam planted ağaç sayısını
$$T(n)=\sum_{e\ge 1} P_e(n)$$
diye tanımlayalım. Ebeveyn düğümünün derecesi \(d\) ise, boyutu \(s\) olan planted ağaçlardan yalnızca kök derecesi \(d\)'den farklı olanlar bağlanabilir. Dolayısıyla boyutu \(s\) olan izinli çocuk tiplerinin sayısı
$$A_d(s)=T(s)-P_d(s)$$
olur. Bağlantı noktasında kontrol edilmesi gereken tek şey budur; çünkü çocuk alt ağacının içindeki bütün kenarlar zaten önceden peerless koşulunu sağlıyordur.
\(d\) ve \(n\) sabit olsun. \(P_d(n)\) tarafından sayılan bir nesne kurmak için, toplam boyutu \(n-1\) olan \(d-1\) izinli çocuk ağacından sırasız bir çoklu küme seçmemiz gerekir. Boyutu \(s\) olan çocukların sayısı \(q_s\) ise
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1$$
olmalıdır. Sabit bir \(s\) için elimizde \(A_d(s)\) farklı izomorfizm tipi vardır. Bu tiplerden tekrara izin vererek \(q_s\) tane seçmenin katsayısı
$$\binom{A_d(s)+q_s-1}{q_s}$$
olur. Böylece
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
Bunu bir üreteç fonksiyonu katsayısı olarak da yazabiliriz:
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
Uygulamalar bu çarpımı sembolik olarak açmıyor; bunun yerine katsayıyı doğrudan “seçilen çocuk sayısı” ve “kullanılan toplam boyut” durumları üzerinde dinamik programlama ile çıkarıyor.
Şimdi kökü planted bir kenar yerine gerçek bir düğümde düşünelim. Kök derecesi \(d\) ise, kökün çocuk sayısı \(d-1\) değil \(d\) olur. \(A_d(s)\) değerleri hazır olduğunda aynı çoklu küme sayacı şu biçimde çalışır:
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
burada \(V(n)\), \(n\) düğümlü peerless ağaçların kökü ayırt edilmiş sürümlerini sayar.
Bir sonraki adımda ağaç yönlü bir kenarda köklenir. Bu yönlü kenar kaldırıldığında, ağaç boyutları \(\ell\) ve \(n-\ell\) olan sıralı bir planted ağaç çiftine ayrılır. İşaretli kenar üzerindeki derece şartını geçici olarak yok sayarsak
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)$$
elde edilir. İki yarı yeniden birleştirildiğinde kökler komşu hâle gelir; bu yüzden kök dereceleri eşit olamaz. Yasak çiftler tam olarak
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell)$$
ifadesidir. Dolayısıyla yönlü-kenar-köklü peerless ağaçların sayısı
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell)$$
olur.
\(E(n)\), ayırt edilmiş ama yönsüz bir kenarda köklenmiş peerless ağaç sayısı olsun. Ağaçlar için klasik dissymmetry özdeşliği
$$U(n)=V(n)+E(n)-D(n)$$
şeklindedir. Peerless bir ağaçta işaretli bir kenarın uçlarının dereceleri her zaman farklı olduğu için, o kenarın iki yönü gerçekten iki ayrı durum verir. Bu nedenle her kenar-köklü nesne tam olarak iki yönlü-kenar-köklü nesneye karşılık gelir, yani
$$D(n)=2E(n).$$
Bunu yukarıdaki özdeşlikte yerine koyunca uygulamaların kullandığı formül çıkar:
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
Özyineleme \(V(5)=6\) ve \(D(5)=8\) verir. O hâlde
$$U(5)=6-\frac{8}{2}=2.$$
Bu iki ağaç, 4-yıldız ile derece dizisi \(3,2,1,1,1\) olan tek ağaçtır. 5 düğümlü yol grafiği dahil değildir; çünkü ortadaki kenarı iki tane derece-2 düğümü bağlar. Bu küçük örnek, yöntemin neden önce köklü nesneleri sayıp sonra işaretli kenarlardan gelen fazla sayımı düzelttiğini açıkça gösterir.
C++, Python ve Java uygulamaları planted sayıları artan \(n\) sırasıyla doldurur. Boyut \(n\) işlenirken \(s<n\) için tüm \(P_d(s)\) ve \(T(s)\) değerleri zaten bilindiğinden, \(A_d(s)=T(s)-P_d(s)\) sayıları da doğrudan elde edilir.
Her hedef kök derecesi için, seçilen çocuk sayısını ve onların toplam boyutunu tutan iki boyutlu bir DP çalıştırılır. Çocuk boyutları tek tek işlendiğinde, \(\binom{A_d(s)+q_s-1}{q_s}\) çarpanlarının tamamı hiç ağaç üretmeden aynen yeniden oluşturulmuş olur.
Planted tablo tamamlandıktan sonra aynı DP, düğüm-köklü sayılar \(V(n)\) için yeniden kullanılır. Yönlü-kenar sayıları \(D(n)\) ise yukarıdaki konvolüsyon formülüyle hesaplanır ve ardından eşit dereceli çiftler çıkarılır. Son adımda her \(n\) için \(U(n)=V(n)-D(n)/2\) uygulanır ve \(U(3)+U(4)+\cdots+U(50)\) toplanır. Bütün hesaplar tam sayı aritmetiğiyle yapılır.
\(N=50\) olsun. Saklanan \(P_d(n)\), \(T(n)\), \(V(n)\) ve \(U(n)\) tabloları toplamda \(O(N^2)\) bellek kullanır; her bir çoklu küme DP'si de buna ek olarak \(O(N^2)\) boyutlu bir çalışma tablosuna ihtiyaç duyar.
Baskın maliyet, planted ve düğüm-köklü durumlar için tekrar tekrar çalışan katsayı çıkarma DP'sidir. Tüm program için güvenli kaba üst sınır \(O(N^6)\) zamandır; yönlü-kenar düzeltmesi yalnızca \(O(N^3)\) maliyetlidir ve daha küçüktür. \(N=50\) çok küçük olduğu ve pek çok imkânsız durum baştan atlandığı için, kesin hesap tamamen pratiktir.
Sea \(U(n)\) el número de árboles no etiquetados y no enraizados con \(n\) vértices tales que cada arista une vértices de grados distintos. Esos son los peerless trees. Hay que calcular
$$\sum_{n=3}^{50} U(n).$$
La recurrencia produce, por ejemplo, \(U(3)=1\), \(U(4)=1\), \(U(5)=2\) y \(U(7)=6\), y una comprobación útil es
$$\sum_{n=3}^{10} U(n)=74.$$
La dificultad principal es que los árboles libres no etiquetados son objetos no ordenados: los hijos de un vértice no forman una secuencia, sino un multiconjunto con posibles repeticiones de tipos isomorfos. Por eso la solución cuenta clases de isomorfía mediante multiconjuntos de subárboles enraizados.
Las implementaciones primero cuentan versiones enraizadas y sólo al final recuperan los árboles libres. La observación clave es local: si un vértice de grado \(d\) se conecta con un subárbol, la raíz de ese subárbol no puede tener también grado \(d\).
Sea \(P_d(n)\) el número de árboles peerless plantados con \(n\) vértices cuya raíz tiene grado \(d\). “Plantado” significa que se considera una arista de padre distinguida por encima de la raíz. Esa arista reservada ya cuenta 1 para el grado de la raíz, así que dentro del subárbol la raíz tiene exactamente \(d-1\) hijos.
Definimos además el total de árboles plantados de tamaño \(n\) por
$$T(n)=\sum_{e\ge 1} P_e(n).$$
Si el vértice padre tiene grado \(d\), entonces entre los árboles plantados de tamaño \(s\) sólo se pueden adjuntar aquellos cuya raíz tiene grado distinto de \(d\). Por tanto, el número de tipos hijos admisibles de tamaño \(s\) es
$$A_d(s)=T(s)-P_d(s).$$
Ésa es toda la restricción en el punto de unión: cada arista interna del subárbol hijo ya era peerless antes de pegarlo, así que sólo importa la nueva arista padre-hijo.
Fijados \(d\) y \(n\), para construir un objeto contado por \(P_d(n)\) hay que elegir un multiconjunto no ordenado de \(d-1\) subárboles hijos admisibles cuya suma de tamaños sea \(n-1\). Si \(q_s\) hijos tienen tamaño \(s\), entonces
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
Para un tamaño fijo \(s\), existen \(A_d(s)\) tipos de isomorfía disponibles, y escoger \(q_s\) hijos entre ellos con repetición permitida produce el factor
$$\binom{A_d(s)+q_s-1}{q_s}.$$
Así,
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
Una forma equivalente con funciones generadoras es
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
Las implementaciones no expanden ese producto de forma simbólica; extraen el coeficiente directamente mediante programación dinámica sobre el par “número de hijos elegidos” y “tamaño total acumulado”.
Ahora enraizamos en un vértice real en vez de en una arista plantada. Si la raíz tiene grado \(d\), entonces posee \(d\) hijos, no \(d-1\). Una vez conocidos los valores \(A_d(s)\), se reutiliza el mismo mecanismo:
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
donde \(V(n)\) cuenta árboles peerless con \(n\) vértices y una raíz distinguida.
El siguiente paso es enraizar en una arista orientada. Al eliminar esa arista dirigida, el árbol se separa en un par ordenado de árboles plantados de tamaños \(\ell\) y \(n-\ell\). Si por un momento ignoramos la condición de grados sobre la arista marcada, obtenemos
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
Al volver a pegar ambas mitades, sus raíces quedan adyacentes, de modo que los grados iguales están prohibidos. Los pares malos son exactamente
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Por tanto, el número de árboles peerless enraizados en una arista dirigida es
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Sea \(E(n)\) el número de árboles peerless enraizados en una arista no dirigida. Para árboles, la identidad clásica de disimetría dice
$$U(n)=V(n)+E(n)-D(n).$$
En un árbol peerless, los extremos de una arista marcada siempre tienen grados distintos, así que las dos orientaciones de esa arista son realmente diferentes. En consecuencia, cada objeto enraizado en arista corresponde exactamente a dos objetos enraizados en arista dirigida, es decir,
$$D(n)=2E(n).$$
Sustituyendo en la identidad de disimetría se obtiene la fórmula usada por las implementaciones:
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
La recurrencia da \(V(5)=6\) y \(D(5)=8\), así que
$$U(5)=6-\frac{8}{2}=2.$$
Esos dos árboles son la estrella de 4 hojas y el árbol único con secuencia de grados \(3,2,1,1,1\). El camino de 5 vértices queda excluido porque su arista central une dos vértices de grado 2. Este caso pequeño muestra bien la idea general: primero es fácil contar los objetos enraizados, y luego una corrección final elimina el sobreconteo causado por las aristas marcadas.
Las implementaciones en C++, Python y Java rellenan los conteos plantados en orden creciente de \(n\). Cuando se procesa el tamaño \(n\), todos los valores \(P_d(s)\) y \(T(s)\) con \(s<n\) ya se conocen, así que los conteos admisibles \(A_d(s)=T(s)-P_d(s)\) se obtienen de inmediato.
Para cada grado de raíz deseado, la implementación ejecuta una DP bidimensional cuyo estado guarda cuántos hijos se han elegido y qué tamaño total aportan. Al procesar los tamaños de hijo uno a uno, se reproduce exactamente el producto de factores binomiales \(\binom{A_d(s)+q_s-1}{q_s}\) sin enumerar árboles de forma explícita.
Cuando la tabla plantada está lista, la misma DP se reutiliza para obtener \(V(n)\). Después, los conteos \(D(n)\) para aristas dirigidas salen de la convolución anterior y de la resta de los pares con el mismo grado. Finalmente se aplica \(U(n)=V(n)-D(n)/2\) para cada \(n\) y se suma \(U(3)+U(4)+\cdots+U(50)\). Toda la aritmética es aritmética exacta de enteros.
Sea \(N=50\). Las tablas almacenadas \(P_d(n)\), \(T(n)\), \(V(n)\) y \(U(n)\) requieren en total \(O(N^2)\) memoria, y cada DP individual de multiconjuntos usa además otra tabla de trabajo de tamaño \(O(N^2)\).
El coste dominante es la repetida extracción de coeficientes para los estados plantados y enraizados en vértice. Una cota superior gruesa y segura para el programa completo es \(O(N^6)\) tiempo; la corrección por aristas dirigidas sólo cuesta \(O(N^3)\) y es menor. Como \(N=50\) es pequeño y muchos estados imposibles se descartan al instante, el cálculo exacto es perfectamente práctico.
记 \(U(n)\) 为所有含 \(n\) 个顶点、无标号、无根的树中，满足每一条边两端顶点度数都不相同的那一类的数量。这就是题目中的 peerless tree。要求计算
$$\sum_{n=3}^{50} U(n).$$
由递推可以得到一些前几项校验值：\(U(3)=1\)、\(U(4)=1\)、\(U(5)=2\)、\(U(7)=6\)，并且
$$\sum_{n=3}^{10} U(n)=74.$$
真正的难点不在于度数条件本身，而在于这里数的是自由树的同构类型。一个顶点的若干子树没有先后顺序，因此不能把它们当成有序列表来拼接；正确的模型是“若干子树类型组成的多重集合”。
三份实现都先统计若干带根版本，再用树的 dissymmetry 恒等式恢复无根计数。整个推导围绕一个局部事实展开：如果某条边的一端顶点度数是 \(d\)，那么接在另一端的子树根节点度数就绝不能也是 \(d\)。
令 \(P_d(n)\) 表示大小为 \(n\)、根的度数为 \(d\) 的 planted peerless 树个数。这里的 “planted” 可以理解为：根上方额外想象出一条已经预留好的父边。因为这条保留边本身就为根的度数贡献了 1，所以在子树内部，根实际上只有 \(d-1\) 个孩子。
再定义
$$T(n)=\sum_{e\ge 1} P_e(n),$$
它表示大小为 \(n\) 的 planted 树总数，不区分根度数。
如果父节点的度数是 \(d\)，那么大小为 \(s\) 的子树里，只有根度数不等于 \(d\) 的那些类型才允许接上去。因此大小为 \(s\) 的合法孩子类型数就是
$$A_d(s)=T(s)-P_d(s).$$
这已经完整表达了连接点上的限制。子树内部的每一条边在被接上之前就已经满足 peerless 条件，所以新产生的父子边是唯一需要额外检查的地方。
固定 \(d\) 和 \(n\)。要构造一个被 \(P_d(n)\) 计数的 planted 树，需要从所有允许的孩子子树中选出一个无序多重集合，使得孩子总数为 \(d-1\)，总顶点数为 \(n-1\)。若大小为 \(s\) 的孩子用了 \(q_s\) 个，那么必须满足
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
对于固定的大小 \(s\)，一共有 \(A_d(s)\) 种可用的同构类型；允许重复地从这些类型里选出 \(q_s\) 个，其组合数正是
$$\binom{A_d(s)+q_s-1}{q_s}.$$
因此得到核心递推式
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
同一件事也可以写成生成函数的系数提取：
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
实现并不会去做符号展开，而是直接对“已经选了多少个孩子”和“这些孩子一共占了多少个顶点”这两个量做动态规划，从而把对应系数精确提出来。
接下来把根放在真实顶点上，而不是 planted 的预留父边上。如果根的度数是 \(d\)，那么这一次根真的有 \(d\) 个孩子，而不是 \(d-1\) 个。一旦 \(A_d(s)\) 已经知道，完全同样的多重集合计数器就可以用来求
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
其中 \(V(n)\) 表示大小为 \(n\) 的 peerless 树在“指定一个根顶点”之后得到的对象数。
然后考虑把根放在一条有向边上。删除这条有向边以后，整棵树会裂成一个有序对，左右两侧分别是大小为 \(\ell\) 和 \(n-\ell\) 的 planted 树。若暂时忽略被切开的那条边上的度数限制，计数就是
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
但当两半重新粘回去时，两棵 planted 树的根会重新变成相邻顶点，所以这两个根的度数不能相同。恰好需要删掉的坏情况是
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
于是，有向边根的 peerless 树个数为
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
设 \(E(n)\) 为“指定一条无向边作为根”的 peerless 树数量。对于树，经典的 dissymmetry 恒等式给出
$$U(n)=V(n)+E(n)-D(n).$$
在本题中，任何被标记的边两端度数必然不同，所以把这条边反向会得到真正不同的两个有向边根对象。因此每一个无向边根对象恰好对应两个有向边根对象，也就是
$$D(n)=2E(n).$$
代回上式便得到实现真正使用的公式
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
递推算出 \(V(5)=6\)、\(D(5)=8\)，因此
$$U(5)=6-\frac{8}{2}=2.$$
这两个无根树恰好是 4 叉星形树，以及度数序列为 \(3,2,1,1,1\) 的那棵唯一的树。5 个顶点的路径不合法，因为其中间那条边连接了两个度数都为 2 的顶点。这个小例子很好地说明了整个策略：先把容易做的带根对象算出来，再把“标记边造成的重复计数”扣回去。
C++、Python 和 Java 实现都按 \(n\) 递增的顺序填表。处理大小 \(n\) 时，所有 \(s<n\) 的 \(P_d(s)\) 与 \(T(s)\) 都已经算好，所以 \(A_d(s)=T(s)-P_d(s)\) 可以立即得到。
对每一个目标根度数，实现都会运行一个二维 DP。状态记录“已经选了多少个孩子”以及“这些孩子已经占用了多少顶点”。按孩子大小逐个推进时，就等价于把所有 \(\binom{A_d(s)+q_s-1}{q_s}\) 因子逐步乘进去，而完全不需要显式枚举树的形状。
planted 表完成后，同一套 DP 会再次用于计算点根计数 \(V(n)\)。随后再利用上面的卷积公式计算 \(D(n)\)，并减去根度数相同的配对。最后对每个 \(n\) 应用 \(U(n)=V(n)-D(n)/2\)，再把 \(U(3)+U(4)+\cdots+U(50)\) 加起来。整个过程都保持精确整数运算。
令 \(N=50\)。存储下来的 \(P_d(n)\)、\(T(n)\)、\(V(n)\)、\(U(n)\) 这些表总共需要 \(O(N^2)\) 空间，而每次多重集合 DP 还会额外用到一个 \(O(N^2)\) 的工作表。
时间上的主导部分是对 planted 状态和点根状态反复进行系数提取。对整个程序给出一个安全的粗略上界，可以写成 \(O(N^6)\) 时间；而有向边修正部分只有 \(O(N^3)\)，规模更小。由于 \(N\) 只有 50，而且大量不可能状态会被立刻跳过，所以这种精确计数在实践中完全可行。
Пусть \(U(n)\) обозначает число неразмеченных неукоренённых деревьев с \(n\) вершинами, у которых каждая грань соединяет вершины разных степеней. Именно такие деревья в задаче называются peerless trees. Требуется вычислить
$$\sum_{n=3}^{50} U(n).$$
Рекуррентная схема даёт, в частности, значения \(U(3)=1\), \(U(4)=1\), \(U(5)=2\), \(U(7)=6\), а также удобную контрольную сумму
$$\sum_{n=3}^{10} U(n)=74.$$
Главная трудность в том, что считаются свободные неразмеченные деревья. Дочерние поддеревья вершины не упорядочены, поэтому их нельзя рассматривать как последовательность; правильный объект для счёта — это мультимножество изоморфных типов корневых поддеревьев.
Во всех трёх реализациях сначала считаются укоренённые версии объектов, а уже потом из них восстанавливается число свободных деревьев. Ключевой локальный инвариант таков: если вершина на одном конце ребра имеет степень \(d\), то корень поддерева по другую сторону этого ребра не может тоже иметь степень \(d\).
Обозначим через \(P_d(n)\) число planted peerless деревьев размера \(n\), у которых корень имеет степень \(d\). Термин “planted” означает, что над корнем мысленно добавлено выделенное родительское ребро. Это зарезервированное ребро уже даёт вклад 1 в степень корня, поэтому внутри самого поддерева у корня ровно \(d-1\) детей.
Также введём общее число planted-деревьев размера \(n\):
$$T(n)=\sum_{e\ge 1} P_e(n).$$
Если родительская вершина имеет степень \(d\), то среди planted-деревьев размера \(s\) можно присоединять только те, у которых степень корня не равна \(d\). Следовательно, число допустимых детских типов размера \(s\) равно
$$A_d(s)=T(s)-P_d(s).$$
Это и есть всё ограничение в точке склейки: каждое внутреннее ребро дочернего поддерева уже было peerless, поэтому дополнительно нужно проверить только новое ребро между родителем и ребёнком.
Зафиксируем \(d\) и \(n\). Чтобы построить объект, учитываемый в \(P_d(n)\), надо выбрать неупорядоченное мультимножество из \(d-1\) допустимых дочерних деревьев суммарного размера \(n-1\). Если детей размера \(s\) выбрано \(q_s\), то должны выполняться условия
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
Для фиксированного \(s\) имеется \(A_d(s)\) доступных изоморфных типов, и число способов выбрать из них \(q_s\) элементов с повторениями равно
$$\binom{A_d(s)+q_s-1}{q_s}.$$
Отсюда получаем
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
То же самое можно записать через извлечение коэффициента:
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
Реализации не раскрывают это произведение символически. Вместо этого коэффициент вычисляется напрямую динамикой по двум параметрам: «сколько детей уже выбрано» и «какой суммарный размер они занимают».
Теперь корень ставится в настоящую вершину, а не в искусственно выделенное родительское ребро. Если степень корня равна \(d\), то у него уже \(d\) детей, а не \(d-1\). Когда значения \(A_d(s)\) известны, тот же самый счётчик мультимножеств даёт
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
где \(V(n)\) — число peerless деревьев на \(n\) вершинах с выделенной корневой вершиной.
Следующий шаг — укоренение по ориентированному ребру. Если удалить это ориентированное ребро, дерево распадается на упорядоченную пару planted-деревьев размеров \(\ell\) и \(n-\ell\). Если временно забыть про условие различия степеней на отмеченном ребре, получаем
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
Но при обратной склейке корни двух половин становятся соседями, а значит, одинаковые степени запрещены. Плохие пары в точности равны
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Следовательно, число peerless деревьев с корнем в ориентированном ребре равно
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
Пусть \(E(n)\) — число peerless деревьев с корнем в неориентированном ребре. Для деревьев классическая dissymmetry-формула имеет вид
$$U(n)=V(n)+E(n)-D(n).$$
В peerless дереве концы отмеченного ребра всегда имеют разные степени, поэтому две ориентации этого ребра действительно различны. Значит, каждому объекту с корнем в ребре соответствуют ровно два объекта с корнем в ориентированном ребре, то есть
$$D(n)=2E(n).$$
Подстановка даёт формулу, которую и реализует код:
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
Рекурсия даёт \(V(5)=6\) и \(D(5)=8\), поэтому
$$U(5)=6-\frac{8}{2}=2.$$
Эти два дерева — звезда с четырьмя листьями и единственное дерево со степенной последовательностью \(3,2,1,1,1\). Путь из 5 вершин не подходит, потому что его центральное ребро соединяет две вершины степени 2. Этот маленький пример показывает общую идею метода: сначала удобно посчитать укоренённые объекты, а потом поправить результат на переучёт, возникающий из-за отмеченных рёбер.
Реализации на C++, Python и Java заполняют таблицу planted-подсчётов в порядке возрастания \(n\). Когда обрабатывается размер \(n\), все значения \(P_d(s)\) и \(T(s)\) для \(s<n\) уже известны, поэтому величины \(A_d(s)=T(s)-P_d(s)\) доступны сразу.
Для каждой требуемой степени корня запускается двумерная DP, чьё состояние хранит число уже выбранных детей и суммарный размер этих детей. Последовательная обработка размеров дочерних поддеревьев воспроизводит произведение биномиальных множителей \(\binom{A_d(s)+q_s-1}{q_s}\), не перебирая сами деревья явно.
После завершения planted-таблицы та же DP повторно используется для вычисления \(V(n)\). Затем по формуле свёртки находится \(D(n)\), после чего вычитаются пары с одинаковой степенью корня. В финале для каждого \(n\) применяется равенство \(U(n)=V(n)-D(n)/2\), а затем складываются значения \(U(3)+U(4)+\cdots+U(50)\). Вся арифметика выполняется точно, без приближений.
Пусть \(N=50\). Таблицы \(P_d(n)\), \(T(n)\), \(V(n)\) и \(U(n)\) занимают суммарно \(O(N^2)\) памяти, и каждая отдельная DP по мультимножествам использует ещё одну рабочую таблицу размера \(O(N^2)\).
Основное время уходит на многократное извлечение коэффициентов для planted-состояний и состояний с корнем в вершине. Надёжная грубая верхняя оценка для всей программы — \(O(N^6)\) по времени; поправка через ориентированные рёбра имеет лишь \(O(N^3)\) и существенно меньше. При \(N=50\) и большом числе мгновенно отбрасываемых невозможных состояний точный расчёт вполне практичен.
لنرمز بـ \(U(n)\) إلى عدد الأشجار غير المعلَّمة وغير المجذَّرة ذات \(n\) رأسًا، والتي يكون عند كل ضلع منها طرفان بدرجتين مختلفتين. هذه هي الأشجار المسماة Peerless Trees. المطلوب هو حساب
$$\sum_{n=3}^{50} U(n).$$
تعطي العلاقة التراجعية القيم الأولية \(U(3)=1\)، و\(U(4)=1\)، و\(U(5)=2\)، و\(U(7)=6\)، كما تعطي نقطة فحص مفيدة هي
$$\sum_{n=3}^{10} U(n)=74.$$
الصعوبة الأساسية أن المطلوب عدّ أنواع تماثل لأشجار حرّة غير معلَّمة. أبناء الرأس الواحد لا يشكّلون قائمة مرتبة، بل متعدد مجموعة من أشكال فرعية قد يتكرر النوع نفسه فيها. لذلك تبني الخوارزمية العدّ عبر متعدد مجموعات من تحت الأشجار المجذَّرة بدلًا من توليد الأشجار مباشرة.
التنفيذات الثلاثة تبدأ بعدّ نسخ مجذَّرة من البنية، ثم تستعيد منها عدد الأشجار الحرّة في النهاية. المبدأ المحلي الحاسم هو: إذا كان أحد طرفي الضلع من الدرجة \(d\)، فالجذر على الطرف الآخر من ذلك الضلع لا يجوز أن تكون درجته أيضًا \(d\).
ليكن \(P_d(n)\) عدد الأشجار peerless المزروعة ذات الحجم \(n\) والتي درجة جذرها \(d\). المقصود بكونها “مزروعة” أن هناك ضلعًا أبويًا مميَّزًا نتخيله فوق الجذر. هذا الضلع المحجوز يضيف 1 أصلًا إلى درجة الجذر، ولذلك يكون عدد أبناء الجذر داخل التحت-شجرة نفسها مساويًا لـ \(d-1\).
ونعرّف أيضًا العدد الكلي للأشجار المزروعة ذات الحجم \(n\) بـ
$$T(n)=\sum_{e\ge 1} P_e(n).$$
إذا كانت درجة الرأس الأبوي هي \(d\)، فإن التحت-شجرة ذات الحجم \(s\) تكون مسموحة بالضبط عندما تكون درجة جذرها مختلفة عن \(d\). لذلك فإن عدد الأنواع المسموح بها من الحجم \(s\) هو
$$A_d(s)=T(s)-P_d(s).$$
هذا يعبّر عن الشرط كاملًا عند نقطة الوصل؛ فكل ضلع داخلي داخل التحت-شجرة الابنة كان يحقق شرط الاختلاف أصلًا، ولا يبقى إلا الضلع الجديد بين الأب والابن.
لنثبّت \(d\) و\(n\). لبناء عنصر يُحسب ضمن \(P_d(n)\)، يجب اختيار متعدد مجموعة غير مرتبة من \(d-1\) تحت أشجار مسموحة، بحيث يكون مجموع أحجامها \(n-1\). إذا كان عدد الأبناء من الحجم \(s\) يساوي \(q_s\)، فلابد من تحقق
$$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$$
ولحجم ثابت \(s\)، يوجد \(A_d(s)\) نوع تماثل متاح. وعدد طرق اختيار \(q_s\) عناصر منها مع السماح بالتكرار هو
$$\binom{A_d(s)+q_s-1}{q_s}.$$
إذًا نحصل على العلاقة الأساسية
$$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$$
ويمكن كتابة الشيء نفسه بصيغة استخراج معامل من دالة مولدة:
$$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$$
التنفيذ لا يوسّع هذا الجداء رمزيًا، بل يستخرج المعامل مباشرةً ببرمجة ديناميكية على حالتين: عدد الأبناء المختارين حتى الآن، ومجموع الأحجام التي استُخدمت.
الآن نجذّر الشجرة عند رأس فعلي بدلًا من ضلع أبوي محجوز. إذا كانت درجة الجذر \(d\)، فعدد أبنائه هذه المرة هو \(d\) وليس \(d-1\). وبعد معرفة \(A_d(s)\) يمكن استعمال نفس آلية العدّ للحصول على
$$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$$
حيث يمثّل \(V(n)\) عدد أشجار peerless ذات \(n\) رأسًا مع تمييز رأس جذري.
بعد ذلك نضع الجذر على ضلع موجَّه. حذف هذا الضلع الموجَّه يقسم الشجرة إلى زوج مرتب من أشجار مزروعة بحجمين \(\ell\) و\(n-\ell\). وإذا تجاهلنا مؤقتًا شرط اختلاف الدرجات على الضلع المعلَّم، نحصل على
$$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$$
لكن عند إعادة لصق النصفين تصبح الجذور متجاورة من جديد، ولذلك تُمنع الحالات التي تتساوى فيها درجتا الجذرين. هذه الحالات السيئة هي بالضبط
$$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
إذن عدد الأشجار peerless المجذَّرة عند ضلع موجَّه هو
$$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$$
ليكن \(E(n)\) عدد أشجار peerless المجذَّرة عند ضلع غير موجَّه. بالنسبة إلى الأشجار تعطينا هوية dissymmetry القياسية
$$U(n)=V(n)+E(n)-D(n).$$
وفي هذه المسألة كل ضلع معلَّم يصل بين درجتين مختلفتين، لذا فإن توجيهي ذلك الضلع مختلفان حقًا. ومن ثم فإن كل عنصر مجذَّر عند ضلع غير موجَّه يقابل بالضبط عنصرين مجذَّرين عند ضلع موجَّه، أي
$$D(n)=2E(n).$$
وبالتعويض نحصل على الصيغة التي تعتمدها التنفيذات:
$$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$$
تعطي العلاقة التراجعية \(V(5)=6\) و\(D(5)=8\)، ومن ثم
$$U(5)=6-\frac{8}{2}=2.$$
وهاتان الشجرتان هما النجمة ذات أربع أوراق، والشجرة الوحيدة ذات متتالية الدرجات \(3,2,1,1,1\). أما المسار ذو خمسة رؤوس فمرفوض لأن ضلعه الأوسط يصل بين رأسين درجتهما 2. يوضح هذا المثال الصغير الفكرة كاملة: من السهل أولًا عدّ النسخ المجذَّرة، ثم يأتي التصحيح النهائي ليزيل الزيادة الناتجة عن تعليم الأضلاع.
تنفّذ نسخ C++ وPython وJava تعبئةً تصاعدية بحسب \(n\). وعندما تتم معالجة الحجم \(n\)، تكون كل القيم \(P_d(s)\) و\(T(s)\) مع \(s<n\) معروفة مسبقًا، ولذلك يمكن تكوين الأعداد المسموح بها \(A_d(s)=T(s)-P_d(s)\) مباشرة.
لكل درجة جذر مطلوبة، تشغّل الخوارزمية DP ثنائية الأبعاد تخزّن في حالتها عدد الأبناء المختارين ومجموع أحجامهم. ومع المرور على أحجام الأبناء واحدًا بعد الآخر، تُعاد بالضبط عوامل \(\binom{A_d(s)+q_s-1}{q_s}\) من دون أي تعداد صريح للأشجار.
بعد اكتمال جدول planted، يُعاد استخدام الـ DP نفسه لحساب \(V(n)\). ثم يُحسب \(D(n)\) من صيغة الالتفاف السابقة، مع طرح الأزواج التي لها درجة جذر متساوية. وفي النهاية تُطبَّق العلاقة \(U(n)=V(n)-D(n)/2\) لكل \(n\)، ثم تُجمع القيم \(U(3)+U(4)+\cdots+U(50)\). وجميع العمليات الحسابية تبقى عمليات صحيحة تامة من دون تقريب.
لنفرض \(N=50\). الجداول المخزنة \(P_d(n)\) و\(T(n)\) و\(V(n)\) و\(U(n)\) تحتاج إجمالًا إلى ذاكرة من الرتبة \(O(N^2)\)، كما أن كل DP فردية لمتعدد المجموعات تستخدم جدول عمل إضافيًا من الرتبة نفسها \(O(N^2)\).
الكلفة الزمنية المهيمنة تأتي من تكرار استخراج المعاملات لحالات الأشجار المزروعة والحالات المجذَّرة عند رأس. ويمكن إعطاء حد أعلى خشن وآمن للبرنامج كله هو \(O(N^6)\) زمنًا؛ أما تصحيح الأضلاع الموجَّهة فتكلفته فقط \(O(N^3)\) وهو أصغر بكثير. وبما أن \(N=50\) صغير جدًا، ولأن عددًا كبيرًا من الحالات المستحيلة يُستبعد فورًا، فإن الحساب الدقيق عملي بالكامل.