(Oral X Mp/Mpi)
On choisit uniformément une permutation {\sigma\in\mathfrak S_n}. Soit {X_n} la longueur maximale d’une sous-suite strictement croissante de {\sigma(1),\ldots,\sigma(n)}.
| Question a) Montrer que, pour {1\leqslant k\leqslant n}, {\mathbb P(X_n\geqslant k)\leqslant\binom nk/k!}. |
| Question b) Montrer qu’il existe {C>0} tel que {\mathbb P(X_n\geqslant C\sqrt n)\to0}. |