Étant donné une constante k, trouver le plus grand arbre enraciné possible, si pour chaque chemin de la racine à la feuille, la somme de l'arité de ses nœuds est égale à k?

8

A titre d'exemple, voici tous les arbres possibles pour le cas k=3: entrez la description de l'image ici Sur chaque nœud est écrit son arité (= le nombre d'enfants).

Bien que cela devrait être résolu par la programmation dynamique, je pense qu'il y a eu un résultat combinatoire à ce sujet (soit une limite supérieure exacte ou plutôt à grain fin). Quelqu'un le sait-il?


Éditer:

La taille de l'arbre est le nombre de nœuds qu'il possède, donc le plus grand arbre serait celui avec le nombre maximal de nœuds.

Sudix
la source
3
Définissez le plus grand.
idobie le
Vous voulez probablement dire "tous les chemins de la racine à une feuille ", sinon l'arborescence à 1 sommet est la seule solution. (Il serait également préférable de dire explicitement que vous parlez d'un arbre enraciné - des arbres non racinés sont également possibles.)
j_random_hacker
@j_random_hacker Oui, vous avez tout à fait raison. Je vais corriger la question.
Sudix

Réponses:

4

Laisser B(n) être la taille du plus grand arbre, où les arités de chaque chemin, de la racine à la feuille, n.

Si la racine d'un tel arbre a de l'arité k, puis les chemins pour chacun des k les sous-arbres doivent correspondre à nk. Comme les sous-arbres doivent être optimaux, l'arbre a une taille1+kB(nk).

Une formule pour B(n) maximise simplement cette expression sur k, en utilisant les valeurs précédentes B(n1),B(n2),.

J'ai essayé de le faire à la main et j'ai trouvé (avec l'aide de @Sudix, merci) 1,2,3,5,7,11,16,23,34,. Cela semble être A239288 dans l'encyclopédie Sloanes en ligne des séquences entières. La récursivité qui y est donnée est similaire, mais pas exactement la même.

L'explication de la séquence y est: "Somme maximale de x0 + x0 * x1 + ... + x0 * x1 * ... * xk sur toutes les compositions x0 + ... + xk = n". Il s'agit en effet de la même séquence: si la séquence d'arités le long du chemin depuis la racine est x0, x1, ..., xk, celles-ci doivent être égales à n, et le nombre de nœuds est en effet la formule donnée.

Une autre remarque chez Sloane est intéressante: "Pour n> = 8 la solution devient cyclique: a (3n + k) = 3 + 3a (3n - 3 + k)". Cela semble suggérer que pour des valeurs supérieures à 24, la racine de l'arbre a toujours trois enfants.

Hendrik Jan
la source
Donc, pour le mettre dans une formule, la récursivité pour résoudre / estimer est: B(n)=1+max1knkB(nk)B(0)=1
Sudix
2
Je pense que dans votre séquence vous avez manqué une étape, j'ai: '1, 2, 3, 5, 7, 11, 16, 23, 34, 49, 70, 103, 148, 211, 310, 445, 634, 931, 1336, 1903, 2794, 4009, 5710, 8383, 12028, 17131 »; Si je n'ai pas mal calculé, il y a une entrée [OEIS] [1] pour la série-1. [1]: oeis.org/…
Sudix