Arbre enracine et series generatrices

[julios]

Bonjour à tous!!!!

Je révise des exercices de maths et je suis bloquer sur un exercice car notre prof nous a fait un cours bidon dessus et j'arrive pas à m'en sortir. ET en plus, je suis bidon en maths!

Je vous donne un bout du sujet de l'exercice :

un arbre enracine plan, C'est soi un seul noeud(racine),soit un k uplet(.,A1,..Ak) ou k>=1 et les Ai sont des arbres enracine plans.
- representez graphiquement les arbres enracines plans a au plus 4 noeuds(racine,noeud interne,feuille),comptez les. 'an' est le nombre de tels arbres à n noeuds.
- traduire la definition recursive en une equation pour la serie generatrice : A(x) = somme avec n>=0 de an*x^n
- resolvez l'equation...

Voila, je vous demande pas de tout faire. J'aimerai connaitre la démarche a suivre.

Merci pour votre aide!!

[Sam Mar]

Je pense à un truc, je ne sais pas si ça peut t'aider :
je considère a(n,k) le nombre d'arbre à n noeuds, de profondeur k.
Si tu considères un tel arbre, tu vois qu'il possède au moins un chemin
de la racine à une feuille de longueur k+1 (si prof(racine) = 0)
Donc, tu regarde ce qu'il te reste à faire pour obtenir ton arbre :
il te reste n-k-1 noeuds à positionner qui seront à des hauteurs variant entre
1 et k -> ce sont les arbres à n-k-1 noeuds et de profondeur entre 0 et k-1:

a(n,k) = som pour i de 0 a k-1 des a(n-k-1,i)

et bien sur :
an = som pour k de 0 a k des a(n,k)

Il y a peut etre des erreurs dans les indices :mur:

[busard_des_roseaux]

Salut,

voilà une documentation succinte pour le vocabulaire.
içi

Bonjour à tous!!!!
- representez graphiquement les arbres enracines plans a au plus 4 noeuds(racine,noeud interne,feuille),comptez les. 'an' est le nombre de tels arbres à n noeuds.

Assez curieusement , pour compter des éléments d'un ensemble,
par exemple des arbres,il faut pouvoir les distinguer et donc à contrario
avoir une relation d'égalité.

Clairement, deux arbres qui n'ont pas la même profondeur ou qui n'ont pas la même largeur sont différents.

Maintenant, se pose le problème: est-ce que deux arbres isomorphes
sont considérés comme différents ou non. Il semble, comme les noeuds sont des k-uplets que les noeuds sont ordonnés et que l'on comptera des arbres
isomorphes , mais pas directement superposables comme distincts.

- traduire la definition recursive en une equation pour la serie generatrice : A(x) = somme avec n>=0 de an*x^n
- resolvez l'equation...

En partitionnant les arbres (ceux de profondeur p=n par exemple) ou avec toute autre propriété dépendant d'un entier n,
on obtient une relation de récurrence agréable, et que la suite définie ainsi par récurrence doit coincider avec les coefficients d'une fonction génératrice.

en conclusion: il faut commencer par définir l'égalité de deux arbres.

Tu peux commencer à dessiner les arbres à quatre noeuds , voir ceux qui sont isomorphes. Selon que l'on considère l'ensemble des fils d'un noeud
comme ordonné ou non ne donne pas le même nombre d'arbres.
Il fau donc être attentif à la définition qui a été donnée d'un arbre.