Finden Sie bei gegebener Konstante k den größtmöglichen Wurzelbaum, wenn für jeden Pfad von der Wurzel zum Blatt die Summe der Arität seiner Knoten gleich k?

Als Beispiel sind hier alle möglichen Bäume für den Fall $k=3$ : Auf jeden Knoten ist seine Arität (= die Anzahl der Kinder) geschrieben.

Während dies durch dynamische Programmierung lösbar sein sollte, gab es meines Erachtens ein kombinatorisches Ergebnis (entweder eine exakte oder eine ziemlich feinkörnige Obergrenze). Weiß es jemand?

Bearbeiten:

Die Größe des Baums entspricht der Anzahl der Knoten, sodass der größte Baum der mit der maximalen Anzahl von Knoten ist.

$B(n)$$n$

$k$$k$$n-k$$1+k\cdot B(n-k)$

$B(n)$$k$$B(n-1), B(n-2),\dots$

$1,2,3,5,7,11,16,23,34,\dots$

Die Erklärung der Sequenz dort lautet: "Maximale Summe von x0 + x0 * x1 + ... + x0 * x1 * ... * xk über alle Kompositionen x0 + ... + xk = n". Das ist in der Tat dieselbe Folge: Wenn die Folge von Aritäten entlang des Pfades von der Wurzel x0, x1, ..., xk ist, sollten diese zu n summieren, und die Anzahl der Knoten ist tatsächlich die gegebene Formel.

Eine weitere Bemerkung bei Sloane ist interessant: "Für n> = 8 wird die Lösung zyklisch: a (3n + k) = 3 + 3a (3n - 3 + k)". Dies scheint darauf hinzudeuten, dass bei Werten größer als 24 die Wurzel des Baumes immer drei Kinder hat.