Par exemple *tous* les arbres qui ne contiennent que des + sont équivalents entre eux — il me semble que ça réduit beaucoup plus la cardinalité que tu ne le crois :
si par exemple (ceci n'est pas un raisonnement rigoureux, c'est pour donner une idée) tu regardes uniquement les deux premiers opérateurs (ie la racine de l'arbre et son fils qui n'est pas une feuille, ou son fils gauche si les deux sont des nœuds — j'oublie la commutativité de la racine, donc en fait tous les arbres sont comptés deux fois, mais bon ça change rien), dans un arbre sur huit ces deux opérateurs vont être deux fois + ou deux fois ×. À chaque fois que ça se produit, ça signifie qu'on peut pivoter et obtenir un autre arbre différent mais équivalent. Donc cet arbre peut être éliminé si on compte l'autre ; par contre c'est possible que l'autre soit encore dans mes 1/8 et dans ce cas il ne faut pas éliminer les deux, mais au total sur mes 1/8 je suis sûr de pouvoir en éliminer au moins la moitié¹. Ainsi rien qu'avec ce vague raisonnement simpliste je sais déjà qu'on peut éliminer au moins 1/16 des arbres.
¹Dit autrement, le vrai calcul est que dans chaque classe d'équivalence on peut éliminer tous les représentants sauf un. Dire qu'un arbre est équivalent à un autre arbre différent revient à dire qu'il appartient à une classe d'équivalence de cardinal au moins 2. Ensuite, d'une part le nombre de classes de cardinal au moins 2 est au maximum la moitié du nombre de leurs représentants, et d'autre part on peut éliminer au moins un représentant de chaque classe, donc le nombre d'arbres éliminables est bien minoré par la moitié du nombre d'arbres qui possèdent un équivalent différent. Ce dernier nombre étant au moins un huitième du total comme on le voit en regardant juste les deux premiers opérateurs (ça ne vaut donc que pour N > 2
)