Bonjour il me faut une fonction qui a chaque arbre associe son rang :
 
voir image : http://www.chez.com/picco/Ftp/inde [...] open=¤Taff (désolé elle voulai pas s'inclure !)
 
suggestion : on admettra qu'il y a (n parmi 2n)/n+1 arbre à n feuilles  
remarquer que pour n feuilles nous avons n-1 noeud interne  
 
 
Voila ce que me dis le sujet le probléme est que j'trouve même pas une idée d'algoritme rien ! si qq1 vois qq chose,  
 
j'dois faire ca en caml mon type Arbre = Feuille | Noeud of (Arbre*Arbre)
 
mais ca a la limite on s'enfou si qq1 a juste une idée d'algorithme moi j'vois vraiment pas sinon tanpis merci joyeu noel !

ce topic aurait sa place dans la subcat algo.
Si pour toi le rang d'un arbre est sa hauteur, alors voici l'algo récursif :

nan justement ce n'est pas sa hauteur c'est ce qui est décris dans l'image !

ok ok, je pensais que ton image n'était que des exemples d'arbres pour lesquels fallait trouver son rang.
 
Vu comme ça ça me parait rigolo comme problème...

Rigolo comme tu dis... ca la été les 3 premiers jours, la ca le devien nettement moins

Je crois avoir compris un truc...
Tout d'abord, il faut que ton arbre binaire, pour qu'il soit "légal" vérifie la propriété énoncée : pour n feuilles, on doit avoir n-1 noeuds internes.
Combien il y a-t-il d'arbres binaires à 1 feuilles vérifiant la propriété précédemment citée ? 1 seul arbre réduit à un seul noeud.
2 feuilles ? 1 seul arbre également.
3 feuilles ? 2 arbres.
4 feuilles ? 5 arbres.
etc.
Ca peut peut être te donner d'autres idées...

Autre propriété : Les arbres semblent être ordonnés de la manière suivante : On choisit les plus "gauchers" en premier.
Par exemple pour les arbres à 4 feuilles (rang 5 à 9) on voit que l'arbre de rang 5 est le plus gaucher (comme l'arbre de rang 3 pour les arbres à 3 feuilles).
 
Ensuite il faut déterminer comment on énumère les arbres.
Pour passer du rang 5 au rang 6 : L'arbre de rang 6 et le symétrique à droite du rang 5.
5 -> 7 : On déplace sur la 3ème feuille en partant de la gauche, les feuilles n°1 et n°2 de l'arbre de rang 5.
7 -> 8 : Le rang 8 est le symétrique à droite du rang 7.
7 -> 9 : On déplace sur la 4ème feuille en partant de la gauche, les feuilles n°2 et n°3 de l'arbre de rang 7. On remarque que son symétrique à droite donne le même arbre.

Il ne te reste plus qu'à formaliser tout ça mais je pense que ton exercice est résolu

euh merci tout ca c'est des constatation que j'avais pu faire a part peu être l'idée de la symétrie ca c pas con !!
si j'fais une fonction symétrie ca peu peu être aidé merci beaucoup (mais c loin d'être résolu )

moi j'vois plus un truc tout con avec une fonction récursive qui fais des opération différente selon "que l'on part a droite ou a gauche" mais j'ai rien trouvé

Il me semble qu'il serait intéressant d'exprimer le nombre d'arbres en fonction du nombre de feuille.
D'après les exemples, j'aurais tendance à conjecturer les relations suivantes :
si n impair, A(n) = 2(n-1) = 2n-2
si n pair, A(n) = 2(n-1)-1 = 2n-3
où n désigne le nombre de feuilles et A(n) le nombre d'arbre en fonction du nombre de feuilles.
Il faudrait les démontrer (par récurrence) pour être rigoureux à partir de n=2.
Evidemment faut poser A(1)=1.
A partir d'une formule de ce genre on peut déjà avoir un encadrement pour le rang d'un arbre dont on connait le nombre de feuilles.
A(1)+A(2)+...+A(n-1) < rang(arbre(n)) <= A(1)+A(2)+...+A(n-1)+A(n)
 
Connaître le rang d'un arbre à n feuilles, revient à connaitre son rang relatif dans l'ensemble des arbres qui ont également n feuilles.

Un algo naïf et certes pas très performant pour trouver le rang relatif consiterait à générer le premier arbre à n feuilles.
On déroule le mécanisme d'énumération posté précédemment en incrémentant le rang relatif et à chaque itération on le compare à l'arbre dont on veut connaître le rang.
Dès que ça "match" on connaît le rang relatif, et donc le rang global.
 
Si je résume une première version de l'algo :
1/ calculer le nombre de feuille de l'arbre binaire à traiter.
2/ calculer le rang de l'arbre le plus gaucher ayant le même nombre de feuilles que l'arbre à traiter.
3/ calculer le rang relatif de l'arbre à traiter.

ok merci alors :
1/ pour calculer A(n) la formule est donné dans mon énoncé c plus simple que ca pas de question de parité :  
A(n) = (n parmis 2n)/(n+1)
j'avais deja pensé a encadré le rang de l'arbre de cette facon, maintenant je n'ai pas bien saisie comment tu arrive au "rang global" car comparé puis démaré le "processus", ok c facile pour le plus gauché son symétrique, mais comment tu fais pour lui dire : "le plus gaucher moins la dernier feuille sur a droite" enfin j'ai même du mal a me visualisé le rang des arbres a 5 feuille, j'v les dessiner j'revien

8! / 4! * 4! = 5x6x7x8 / 2x3x4 = 5x7x8 / 4 = 5x7x2 = 70
70 / 4 +1 = 14  la formule de l'énoncé marche pas pour 4 feuille merde ! c pas possible ils ont du se gourré dans l'énoncé on est plus sur de rien la c la merde
 
bref de tte facon imagine pour un n assez grand le processus de comparation j'sais pas trop comment le codé ca devien vraiment un truc énorme ! j'v réflechir encor merci

Voici les 14 arbres à 5 feuilles :

 
Quand dans l'énoncé ils écrivent (n parmis 2n), c'est bien de C(2n, n) dont il s'agit ? Car dans ce cas on aurait pour le nombre d'arbres "légaux" à 4 feuilles : A(4)=C(8,4)/5=14
ou A(3)=5
Ca ne semble pas correspondre à ce qu'il y a sur le dessin où il semble il y avoir A(3)=2 et A(4)=5...

tu as oublier :
 
 / \
/\ /\
 /\
 
et  
 / \
/\ /\
  /\
 
ca fais 10 arbre a 5 feuille et oui la formule de l'énoncé est bien fausse (ca nous arrange pas)

bien vu. j'ai corrigé le post précédent.
 
Sinon, je pense avoir un squelette d'algo pour le rang. Le voici :
 

 
La fonction Z reste encore à déterminer mais je pense que le principal est là.
Au début j'avais Z = 2*(nb feuilles à gauche des deux feuilles supprimées+1) + rang(arbre ainsi modifié)
mais avec les arbres à 5 feuilles ça ne marche pas.
Je pense effectivement que la fonction Z est une fonction combinatoire.

Yes
Je viens de trouver les 14 arbres à 5 feuilles ! (cf un des posts au dessus)
 
La formule est correcte mais faut la lire comme suit :
Il y a C(2n, n)/n+1 arbre à n noeuds internes.
Y a plus qu'à bosser sur la fonction Z est le but est proche

wahou merci beaucoup ! j'v essayé de bien comprendre ton algo et apres j'réfléchis pour la fct z j'te dis ou j'en suis merci