Ethaniel (./37) :Pollux (./19) :J’ai aussi essayé de cette manière (tous mes arbres ont leur notation RPN équivalente), mais ça n’a vraiment rien donné.
Ou bien tu peux trouver l'expression de c' directement en notant tes arbres en RPN : si tu rajoutes à tes n nombres n-1 opérateurs distincts o1..on-1 (donc au total tu as un alphabet A à 2n-1 éléments), tu peux faire correspondre à chaque arbre son expression RPN, qui est une permutation de A. Mais si tu prends une permutation quelconque de A, ça ne correspond pas toujours à une expression RPN... Heureusement il existe une unique permutation circulaire de ta permutation qui correspond à une vraie expression RPN : si tu notes p[k] la profondeur de la pile (éventuellement négative) avant le k-ème symbole, tu prends le plus grand k tel que p[k] soit minimale et en faisant une rotation de k éléments tu obtiens une expression RPN (et c'est le seul k vérifiant cette propriété). Ca te donne une relation d'équivalence entre permutations de A, et chaque classe d'équivalence a 2n-1 éléments. Donc il y a (2n-1)!/(2n-1) = (2n-2)! arbres utilisant o1..on-1. Puisqu'on veut un seul opérateur, il faut diviser par le nombre de permutations de o1..on-1 : ça donne bien c'[n] = (2n-2)!/(n-1)!
Et je comprends pourquoi : dans ton explication, j’ai décroché dès la mention de p[k], donc dès le début, en fait.
Tu pourrais développer un peu si tu as le temps, STP?
?Par exemple tu pars de la suite de symboles "+ 2 / 1 5 2 racine_n-ème", qui n'est pas une expression RPN valide.
Tu fais comme si elle était valide (par exemple en supposant qu'il y a déjà plein de trucs sur la pile), et tu l'exécutes en boucle. Et tu regardes la hauteur de la pile p[k] à chaque symbole k :
Qu'est-ce qui se serait passé si on avait eu une expression RPN valide ? On part du point p[0] = 0, et on aurait eu p[1] = 1 et p[k] >= 1 pour tout k>0 (ce qui n'est pas du tout le cas ici). Si l'expression a N symboles, toujours en supposant l'expression valide on a p[N] = 1. Ca veut dire qu'on peut tracer la droite y = 1/N * x et elle sera toujours en-dessous du graphe en zig-zags. Mieux, ce sera la plus haute droite qui reste en-dessous du graphe en zig-zag, et elle touche le zig-zag précisément à l'endroit où commence l'expression RPN (k multiple de N). Et là on se rend compte que cette caractérisation ne change pas si on prend un autre point de départ, puisque c'est simplement une propriété de la courbe ! On regarde ce que ça donne avec notre chaîne de départ :
Les petites étoiles donnent le point de départ de l'expression RPN, donc en faisant une permutation circulaire ça donne l'expression "1 5 2 racine_n-ème + 2 /" qui décrit le nombre d'or
Pollux, c’est toi, R. J. Mathar?
?Peut-être qu'il lit yN ?
