Pollux (./19) :
Si tu appelles ta suite c[n] tu as la relation :
c[0] = 0
c[1] = 1
c[n] = 1/2 sum[k=0..n] C(n,k) c[k] c[n-k] pour n>1

Si tu poses c'[n] = c[n]*2^(n-1) ça te donne une relation un peu plus simple
c'[0] = 0
c'[1] = 1
c'[n] = sum[k=0..n] C(n,k) c'[k] c'[n-k] pour n>1
( http://www.research.att.com/~njas/sequences/A001813 )
C'est la version étiquetée des http://en.wikipedia.org/wiki/Catalan_number (on peut aussi faire le lien avec les nombres de Catalan directement : c'[n] = catalan[n-1]*n! puisque pour avoir une version étiquetée d'un arbre non étiqueté il suffit de rajouter une permutation quelconque des feuilles, et c[n]*2^(n-1) = c'[n] puisque pour avoir une version asymétrique d'un arbre symétrique il suffit de rajouter une information de direction à chaque noeud).

Rhââ Pollux, tout semble si simple avec toi  !
Je n’avais jamais entendu parler des nombres de Catalan jusqu’à ton post, et je ne vois pas comment j’aurais pu trouver tout seul.
Quant à ta relation c[n], j’ai dû batailler ferme sur mes arbres pour la retrouver et me convaincre que, oui, c’est bien ça …

Pollux (./19) :
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)!

J’ai aussi essayé de cette manière (tous mes arbres ont leur notation RPN équivalente), mais ça n’a vraiment rien donné.
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  ?

Ethaniel (./18) - Posté : 30-09-2008 :

Pollux (./17) :
(ah tiens en fait elle y est aussi avec 4^(n-1), et même en double http://www.research.att.com/~njas/sequences/?q=4,48,960,26880&sort=0&fmt=0&language=english&go=Search )

Ne faudrait-il pas prévenir les admins du site que la seconde suite, qui date seulement du 21 septembre dernier, fait doublon avec la première ?

En fait, ce n’est pas un doublon, il y a un décalage :
¤ A052714 = 0, 1, 4, 48, …
¤ A144828 = 1, 4, 48, …J’avais parlé de doublon le 30/09, et que vois-je en contribution sur la seconde suite datée du lendemain ?

A144828a(n)=A052714(n+1). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 01 2008]

Pollux, c’est toi, R. J. Mathar  ?

Sally (./36) :
attention à la notion de « doublon » d'ailleurs, tu vas avoir des triplons ou des quadruplons etc.

Je sais, mais #flemme# de répéter à chaque fois « (ou n-uplon) » …

Sally (./36) :
il me semble que ça réduit beaucoup plus la cardinalité que tu ne le crois

J’ai dénombré précisément, pour N=3, les équivalences des arbres ne contenant que des + et des - (idem pour ceux ne contenant que des * et des /), et on passe finalement de 48 calculs différents à 32  !
Pour N=4, je sens que ça va être beaucoup plus chaud, mais bon, j’aurai toute la soirée pour y bosser pendant que madame regarde la Star N’Ac’ (sauf si je me laisse tenter par la Trilogie martienne ).

Sally (./36) :
Ainsi rien qu'avec ce vague raisonnement simpliste je sais déjà qu'on peut éliminer au moins 1/16 des arbres.

Au temps pour mon « k tendant vers 1 », donc, puisqu’il est majoré par 15/16 pour N>2…
Y’a pas à dire, l’intuition mathématique, c’est vraiment pas la même chose que l’intuition physique  ! (ce qui ne m’empêche pas de raconter des conneries en physique aussi, mais quand même beaucoup beaucoup moins qu’en maths)