Pollux (./17) :
Tu peux toujours faire "redescendre" le signe moins pour qu'il s'applique uniquement aux feuilles

C’est bien ce que je dis : même s’il y a a priori 6 manières de combiner 2 nombres positifs A et B et une des 4 opérations — à savoir A+B=B+A ; A-B ; B-A ; A*B=B*A ; A/B ; B/A —, on peut en réalité se contenter de 4 combinaisons différentes pour, au final, arriver quand même à couvrir tous les résultats possibles — à savoir A+B=B+A ; A--B=B--A=abs(A-B) ; A*B=B*A ; A//B=B//A=max(A,B)/min(A,B).
D’où 4^(N-1) et non 6^(N-1).

Pollux (./17) :
La suite que tu cherches est http://www.research.att.com/~njas/sequences/A001147 à un facteur 4^(n-1) près.

Ah oui, tiens !

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters

En effet, c’est tout à fait ça !
Comment as-tu trouvé cette suite ?
Effectivement, pour les cas N=4 et N=5 (je rappelle que je m’étais arrêté là), et en comparant avec l’exemple donné sur ta page, je m’aperçois que j’avais compté quelques arbres en double, et le bon dénombrement donne maintenant la même chose que ta suite, ouf  !

Pollux (./17) :
Asymptotiquement elle est plus grande que ta suite, donc je doute que la tienne soit un majorant

En effet : jusqu’à N=5, je comptais trop de cas, mais dès N=6, j’en compte moins (900×4^5 au lieu de 945×4^5) .
Finalement, j’aurais dû aller jusqu’à N=6 avant de me lancer dans la récurrence …
Bon allez, au boulot, moi !
Même si je n’entends pas redémontrer totalement le résultat d’Andrew Walters, j’aimerais quand même voir où je me suis planté dans mon dénombrement des arbres de calcul…

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 ?