Connectez-vous pour consulter le corrigé.
Dans tout le problème, on désigne par \(n\) un nombre entier naturel non nul.
On se propose dans cette partie de calculer pour tout entier \(p \geqslant 1\) la somme: \[S_{n}(p)=\sum_{k=1}^{p} k^{n}=1^{n}+2^{n}+\cdots+p^{n}\]
Soient \(\mathbb{R}[X]\) l’espace vectoriel des fonctions polynômes à coefficients réels et \(( P_{k})\) la suite de fonctions polynômes définies par \(P_{0}(x)=1\) et, si \(k \geqslant 1\), par: \[\forall x \in\mathbb{R},\ P_{k}(x)=\frac{x \left( x-1 \right) \cdots(x-k+1)}{k!}=\frac{1}{k!} \prod_{j=0}^{k-1}(x-j)\]
On considère l’application \(\Delta\) de \(\mathbb{R}[X]\) dans lui-même associant à la fonction polynôme \(P\) la fonction polynôme \(\Delta P\) définie par: \[\forall x \in\mathbb{R},\ \Delta P(x)=P(x+1)-P(x)\]
Prouver que \(\Delta\) est un endomorphisme de \(\mathbb{R}[X]\), puis déterminer son noyau.
Soient \(j, k\) des entiers naturels. On rappelle que \(\Delta^{j}=\Delta \circ \Delta \circ \ldots \circ \Delta\) (\(j\) fois), et \(\Delta^{0}\) désigne par convention l’application identité de \(\mathbb{R}[X]\).
Déterminer \(\Delta P_{k}\), puis \(\Delta^{j} P_{k}\) en distinguant les cas \(j \leqslant k\) et \(j>k\).
Prouver que \(( P_{0}, P_{1}, \ldots, P_{n} )\) est une base du sous-espace de \(\mathbb{R}[X]\) constitué des fonctions polynômes de degré inférieur ou égal à \(n\), et établir la formule suivante pour toute fonction polynôme \(P\) de degré inférieur ou égal à \(n\) :
\[\forall x \in\mathbb{R},\ P(x)=\sum_{k=0}^{n} \Delta^{k} P (0) \cdot P_{k}(x)\]
En déduire que \(\Delta\) est surjectif, puis, pour toute fonction polynôme \(P\) de degré \(n\), établir l’existence d’une unique fonction polynôme \(Q\), de degré \(n+1\), telle que: \[\forall x \in\mathbb{R},\ Q(x+1)-Q(x)=P(x) \quad \text { et } \quad Q(0)=0\]
On note \(Q_{n}\) la fonction polynôme telle que : \[\forall x \in\mathbb{R},\ Q_{n}(x+1)-Q_{n}(x)=x^{n} \quad \text{et} \quad Q_{n}(0)=0\]
Exprimer \(S_{n}(p)\) à l’aide de \(Q_{n}\) et de \(p\), et expliciter \(Q_{n}\) et \(S_{n}(p)\) pour \(n \leqslant 3\).
On établit dans cette partie quelques résultats probabilistes.
Fonction génératrice d’une variable aléatoire.
On considère un entier naturel \(p\) et une variable aléatoire \(X\) à valeurs dans l’ensemble \(\{0,1, \ldots, p\}\). On lui associe la fonction suivante, dite fonction génératrice de X : \[t \rightarrow G_{X}(t)=\sum_{k=0}^{p} \mathbb{P}(X=k) \, t^{k}\]
Déterminer la fonction génératrice de \(X\) lorsque:
\(X\) suit une loi de Bernoulli de paramètre \(\lambda\) (\(\lambda\) réel tel que \(0<\lambda<1\)).
\(X\) suit une loi binomiale de paramètres \(n\) et \(\lambda\) (\(\lambda\) réel tel que \(0<\lambda<1\)).
Fonction génératrice d’une somme de variables aléatoires indépendantes.
On considère désormais des entiers naturels \(p_{1}, p_{2}, \ldots, p_{n}\) et des variables aléatoires \(X_{1}, X_{2}, \ldots, X_{n}\) définies sur un même espace probabilisé, indépendantes et à valeurs dans \(\left\{0,1, \ldots, p_{1}\right\}\), \(\left\{0,1, \ldots, p_{2}\right\}\), \(\ldots,\left\{0,1, \ldots, p_{n}\right\}\) respectivement. On note alors: \(Y_{n}=X_{1}+X_{2}+\ldots+X_{n}\).
Établir que la fonction génératrice de \(Y_{2}=X_{1}+X_{2}\) est le produit des fonctions génératrices de \(X_{1}\) et de \(X_{2}\).
Exprimer la fonction génératrice de \(Y_{n}=X_{1}+X_{2}+\ldots+X_{n}\) à l’aide des fonctions génératrices de \(X_{1} , X_{2}, \ldots ,X_{n}\).
Retrouver le résultat obtenu en 6b à l’aide de celui de la question 6a.
Étude d’un cas particulier.
On suppose de plus que, pour tout entier \(k\) tel que \(1 \leqslant k \leqslant n\), la variable aléatoire \(X_{k}\) suit une loi uniforme sur \(\{0,1, \ldots, k-1\}\), autrement dit: \[\mathbb{P}( X_{k}=0)=\mathbb{P}( X_{k}=1)=\ldots=\mathbb{P}( X_{k}=k-1)=\frac{1}{k}\]
Calculer l’espérance et la variance des variables aléatoires \(X_{k}\) (\(1 \leqslant k \leqslant n)\), puis de la somme \(Y_{n}=X_{1}+X_{2}+\ldots+X_{n}\).
On convient de noter la fonction génératrice \(G_{n}\) de \(Y_{n}\) sous la forme suivante:
\[G_{n}(t)=\frac{1}{n!} \sum_{k=0}^{\frac{n(n-1)}{2}} c_{n, k} t^{k}\]
En exprimant \(G_{n+1}\) en fonction de \(G_{n}\), déterminer \(c_{n+1, k}\) en fonction des coefficients \(c_{n, k}\), \(c_{n, k-1}\), \(\ldots, c_{n, k-n}\).
Par convention, on posera \(c_{n, k}=0\) lorsque \(k<0\) ou lorsque \(k> \dfrac{n \left( n-1 \right)}{2}\).
Montrer que les coefficients \(c_{n, k}\) sont entiers naturels et calculer \(\displaystyle \sum_{k=0}^{\frac{n(n-1)}{2}} c_{n, k}\).
On considère un tableau s=[s[0],s[1],...,s[n-1]] dans
lequel toutes les variables sont de type entier et où les \(n\) entiers \(1,2, \ldots, n\) sont affectés dans un
ordre quelconque aux \(n\) variables
s[0],s[1],...,s[n-1].
L’objet de cette partie est l’étude de la complexité de l’algorithme de tri suivant, visant à ranger dans l’ordre croissant les éléments de ce tableau s :
for i in range(n-1):
for j in range(n-i-1):
if s[j]>s[j+1]:
s[j],s[j+1]=s[j+1],s[j]
On appellera « échange » toute exécution de l’instruction
s[j],s[j+1]=s[j+1],s[j].
Exemples de mise en œuvre de l’algorithme.
On suppose dans cette question que \(n=3\). Indiquer les valeurs contenues dans
les variables s[0],s[1],s[2] après chaque passage dans les
boucles for lorsque l’on affecte initialement à
s les six valeurs suivantes: \[(1,2,3) \ ; \ (2,3,1) \ ; \ (3,1,2) \ ; \
(1,3,2) \ ; \ (3,2,1) \ ; \ (2,1,3)\] On précisera à chaque
fois le nombre total d’échanges (on présentera les résultats obtenus
dans six tableaux distincts).
Action de l’algorithme.
Déterminer la valeur contenue dans s[n-1] à l’issue
du passage dans la boucle suivante:
for j in range(n-1):
if s[j]>s[j+1]:
s[j],s[j+1]=s[j+1],s[j]
En déduire la valeur contenue en fin d’algorithme dans
s[k-1] pour \(1 \leqslant k
\leqslant n\).
Complexité de l’algorithme.
Exprimer en fonction de \(n\) le nombre de comparaisons d’entiers \(( > )\) effectuées au cours de l’algorithme.
Exprimer en fonction de \(n\) les nombres maximal et minimal d’échanges au cours de l’algorithme. On explicitera des tableaux \(s\) pour lesquels ces maximum et minimum sont effectivement atteints.
Dans la suite, on associe au tableau \(s\) et à tout entier \(k\) tel que \(0 \leqslant k \leqslant n-1\) :
le nombre \(U_{k}(s)\) des
entiers \(i\) tels que \(0 \leqslant i<k\) et
s[i]>s[k] (avec \(U_{0}(s)=0\)).
la somme \(V_{n}(s)=U_{0}(s)+U_{1}(s)+\ldots+U_{n-1}(s)\).
On dit que \(V_{n}(s)\) est le nombre des inversions du tableau \(s\), autrement dit le nombre des couples d’entiers \(( i, k )\) tels que: \[0 \leqslant i<k \leqslant n-1 \quad \text{et} \quad \mathtt{s[i]>s[k] }\]
Nombre d’échanges.
Lorsque s[j]>s[j+1], indiquer l’effet de
l’échange des valeurs de s[j] et s[j+1] sur le
nombre des inversions du tableau
s=(s[0], s[1], …, s[n-1]).
En déduire le nombre d’échanges effectués lors du tri de
s.
On suppose dans cette question que \(n=3\). Préciser \(( U_{0}(s), U_{1}(s), U_{2}(s))\) et \(V_{3}(s)\) lorsque l’on affecte initialement à \(s=(s[0], s[1], s[2])\) les six valeurs: \[(1,2,3) \ ; \ (2,3,1) \ ; \ (3,1,2) \ ; \ (1,3,2) \ ; \ (3,2,1) \ ; \ (2,1,3)\]
Rédiger une fonction en langage Python
calculant \(U_{k}(s)\) (où \(0 \leqslant k \leqslant n-1\)) et \(V_{n}(s)\). On supposera le tableau
s stocké dans un tableau numpy.
On suppose dans la suite que les différentes façons d’affecter les
\(n\) entiers \(1,2, \ldots, n\) aux \(n\) variables
s[0],s[1],…,s[n-1] sont équiprobables, et l’on note:
\(S_{n}\) l’ensemble des
différents tableaux s ainsi obtenus.
\(\Omega_{n}\) l’ensemble des \(n\)-uplets \(\left(u_{0}, u_{1}, \ldots, u_{n-1}\right)\) d’entiers tels que \(0 \leqslant u_{k}<k+1\) pour tout entier \(k\) tel que \(0 \leqslant k \leqslant n -1\).
On considère \(U_{0}, U_{1}, \ldots, U_{n-1}\) comme des variables aléatoires sur l’ensemble \(S_{n}\).
Bijectivité de l’application \(s \mapsto (U_0(s), U_1(s)..... U_{n-1}(s))\).
Vérifier que l’application \(U\) associant à tout tableau \(s\) de \(S_{n}\) le \(n\)-uplet \(\left(U_{0}(s), U_{1}(s), \ldots, U_{n-1}(s)\right)\) prend ses valeurs dans \(\Omega_{n}\).
Soit \(s\) un tableau de \(S_{n}\) tel que \(U_{0}(s)=u_{0}\), \(U_{1}(s)=u_{1}\), \(\ldots, U_{n-1}(s)=u_{n-1}\).
Déterminer s[n-1] en fonction de \(u_{n-1}\).
Expliquer de même comment l’on peut obtenir les valeurs de
s[n-2],…,s[0] en fonction de \(u_{n-2}, \ldots, u_{0}\).
Montrer que l’application \(s \mapsto U(s)\) est une bijection de \(S_{n}\) sur \(\Omega_{n}\).
En déduire le nombre des tableaux \(s\) de \(S_{n}\) tels que \(U_{k}(s)=u_{k}\) pour tout entier \(k\) tel que \(0 \leqslant k \leqslant n-1\) et tout entier \(u_{k}\) tel que \(0 \leqslant u_{k}<k+1\).
Lois des variables aléatoires \(U_{0}, U_{1}, \ldots, U_{n-1}\).
Déterminer la probabilité \(\mathbb{P}( U_{0}=u_{0}, U_{1}=u_{1}, \ldots, U_{n-1}=u_{n-1})\) pour tout \(n\)-uplet \(\left(u_{0}, u_{1}, \ldots, u_{n-1}\right)\) appartenant à \(\Omega_{n}\).
Déterminer la probabilité \(\mathbb{P}( U_{k}=u_{k})\) pour tout entier \(k\) tel que \(0 \leqslant k \leqslant n-1\) et tout entier \(u_{k}\) tel que \(0 \leqslant u_{k}<k+1\).
En déduire la loi de \(U_{k}\) et l’indépendance des \(n\) variables aléatoires \(U_{0}, \ldots, U_{n-1}\).
En déduire en fonction de \(n\) l’espérance et la variance du nombre \(V_n\) d’échanges effectués au cours de l’algorithme, et donner des équivalents simples de ces expressions lorsque \(n\) tend vers l’infini.
Écrire une fonction en langage Python
renvoyant un vecteur dont les coefficients représentent la loi de \(V_n\), i.e. les probabilités \(\mathbb{P}(V_n=k)\) pour \(k \in V_n(E_n)\).
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.