Pour un entier n donné, on considère un arbre T_n choisi uniformément au hasard parmi les arbres binaires à n feuilles et on étiquette chacun de ses noeud internes par un signe +/ -, choisis de manière i.i.d. avec probabilité p / (1-p). On s'intéresse à la variable aléatoire X_n associée qui compte la taille du plus grand sous-ensemble de feuilles qui induit dans T_n un sous-arbre n'a que des signes + sur ses noeuds. Le problème original vient du fait que l'arbre T_n encode en fait une permutation aléatoire et le X_n considéré compte la longueur de la plus grande sous-suite croissante de cette permutation.

On montrera que quand n est grand, X_n se comporte comme n^\alpha avec un exposant \alpha=\alpha(p) et on discutera plus précisément de la valeur de \alpha(p).

(Travail en commun avec Arka Adhikari, Jacopo Borga, Thomas Budzinski et William Da Silva)