Maths Cachan-Rennes

Bonjour,

J'ai eu un oral de dénombrement et de probabilités assez familier.

On se place dans l'ensemble S_n des permutations de 1, ... n.

Question 1
Déterminer le nombre de cycles de longueur k dans S_n.

Question 2
On considère le polynôme P_n = X(X+1)...(X+n-1), dont on note c_n,k les coefficients.
Calculer c_n,n ; c_n,0 ; c_n,1 ; c_n,n-1.
Trouver une relation de récurrence entre c_n+1,k et les c_n,j.

Question 3
On note P_n,k le nombre de permutations de S_n possédant exactement k cycles dans leur décomposition en cycles disjoints.
Trouver une relation de récurrence entre les P_n,k. Qu'en déduire ?

Question 4
On munit S_n de la loi uniforme, et on note N la variable aléatoire qui à une permutation associe le nombre de cycles dans sa décomposition en cycles disjoints. Calculer l'espérance de N, et en donner un équivalent pour n tendant vers l'infini.

(Alors, oui, on a déjà tout fait en cours... Merci M. Francinou !)

Pour la troisième question, l'examinateur m'a demandé de préciser ma stratégie de dénombrement. On fixe une permutation de S_n+1 à k cycles, et, par disjonction de cas en fonction de l'image de n+1, on se ramène, de manière bijective, à la construction de permutations de S_n.
Pour la dernière question, N est bornée, donc admet une espérance et la formule de transfert s'applique. On peut alors relier cette somme à P_n'(1), qui fait apparaître n! multipliée par la somme harmonique. On obtient alors un équivalent de l'espérance : ln(n).

Mathieu Rasson