Maths 2
Centrale-SupélecTSI2026
Rédigé par IA, non vérifié
Signaler une erreur# Centrale-Supélec TSI — Mathématiques 2 2026 · Corrigé brut
*Corrigé rédigé par IA (La Belle Copie), non officiel. Signalez toute erreur.*
Notations : $\binom{j}{i}=0$ si $i>j$ (convention de l'énoncé). Deux défauts de l'énoncé sont corrigés en place : en **Q31**, « la matrice introduite en Q25 » désigne la matrice de la figure 4, introduite en **Q26** ; en **Q37**, la convention cohérente est **$b_0=1$** et non $b_0=0$.
## Partie A — Matrices de Pascal
### I — Cas particulier $n=2$
### Question 1
Pour $P=a+bX+cX^2\in\mathbb R_2[X]$ :
$$u(P)=a+b(X+1)+c(X+1)^2=(a+b+c)+(b+2c)X+cX^2\in\mathbb R_2[X].$$
Pour $P,Q\in\mathbb R_2[X]$ et $\lambda,\mu\in\mathbb R$, $(\lambda P+\mu Q)(X+1)=\lambda P(X+1)+\mu Q(X+1)$, donc $u$ est linéaire. C'est un endomorphisme de $\mathbb R_2[X]$.
$u(1)=1$, $u(X)=1+X$, $u(X^2)=1+2X+X^2$. En rangeant ces coordonnées en colonnes :
$$\boxed{\operatorname{Mat}_e(u)=\begin{pmatrix}1&1&1\\0&1&2\\0&0&1\end{pmatrix}.}$$
### Question 2
Notons $A=\operatorname{Mat}_e(u)$. Elle est triangulaire, donc $\det A=1\neq0$ : $A$ est inversible.
Soit $v:P\mapsto P(X-1)$ sur $\mathbb R_2[X]$. Pour tout $P$, $u(v(P))=P((X+1)-1)=P$ et $v(u(P))=P$, donc $v=u^{-1}$ et $A^{-1}=\operatorname{Mat}_e(v)$. Comme $v(1)=1$, $v(X)=-1+X$, $v(X^2)=1-2X+X^2$ :
$$\boxed{A^{-1}=\begin{pmatrix}1&-1&1\\0&1&-2\\0&0&1\end{pmatrix}.}$$
$A$ est triangulaire : ses valeurs propres sont ses coefficients diagonaux, $\boxed{\operatorname{Sp}(A)=\{1\}}$.
Si $A$ était diagonalisable, elle serait semblable à $\operatorname{diag}(1,1,1)=I_3$, donc $A=PI_3P^{-1}=I_3$, ce qui est faux ($A_{1,2}=1$). **$A$ n'est pas diagonalisable.** (De façon équivalente : $\operatorname{rg}(A-I_3)=2$, donc $\dim\ker(A-I_3)=1<3$.)
### II — Des matrices semblables à leurs inverses
### Question 3
Pour $j\in[\![0,n]\!]$, la formule du binôme donne
$$u(X^j)=(X+1)^j=\sum_{i=0}^{j}\binom{j}{i}X^i.$$
La colonne $j$ de $U$ a donc pour coefficients $\binom{j}{i}$, nuls pour $i>j$ :
$$\boxed{\forall (i,j)\in[\![0,n]\!]^2,\quad U_{i,j}=\binom{j}{i},}$$
et **$U$ est triangulaire supérieure**, de coefficients diagonaux $\binom ii=1$. Donc $\operatorname{Sp}(U)=\{1\}$.
- Si $n=0$, $U=(1)$ est diagonale.
- Si $n\ge1$, $U$ diagonalisable de spectre $\{1\}$ serait semblable à $I_{n+1}$, donc égale à $I_{n+1}$ ; or $U_{0,1}=\binom10=1$. **Pour $n\ge1$, $U$ n'est pas diagonalisable.**
### Question 4
Pour tout $P\in\mathbb R_n[X]$, $(u\circ v)(P)=P((X-1)+1)=P$ : $\boxed{u\circ v=\mathrm{id}_{\mathbb R_n[X]}}$, et de même $v\circ u=\mathrm{id}$. Donc $u$ est bijective, d'inverse $v$, et $U$ est inversible avec $U^{-1}=\operatorname{Mat}_e(v)$. Comme
$$v(X^j)=(X-1)^j=\sum_{i=0}^{j}\binom{j}{i}(-1)^{j-i}X^i,$$
on obtient
$$\boxed{\forall (i,j)\in[\![0,n]\!]^2,\quad (U^{-1})_{i,j}=(-1)^{j-i}\binom{j}{i}.}$$
Pour $n=2$, la première ligne vaut $(1,-1,1)$, la deuxième $(0,1,-2)$, la troisième $(0,0,1)$ : c'est la matrice obtenue en Q2, **le résultat est cohérent**.
### Question 5
$D$ est diagonale de coefficients $(-1)^i$, donc $D^2$ est diagonale de coefficients $((-1)^i)^2=1$ : $D^2=I_{n+1}$. Ainsi $D$ est inversible et $\boxed{D^{-1}=D}$.
### Question 6
Multiplier à gauche par $D$ multiplie la ligne $i$ par $(-1)^i$ ; multiplier à droite multiplie la colonne $j$ par $(-1)^j$. Pour $(i,j)\in[\![0,n]\!]^2$ :
$$(DU)_{i,j}=(-1)^i\binom ji,\qquad (U^{-1}D)_{i,j}=(-1)^{j-i}\binom ji(-1)^j=(-1)^{2j-i}\binom ji=(-1)^i\binom ji.$$
Donc $\boxed{DU=U^{-1}D}$. En multipliant à gauche par $D$ et en utilisant $D^2=I_{n+1}$ : $U=DU^{-1}D$, soit
$$\boxed{U=DU^{-1}D=DU^{-1}D^{-1}.}$$
$D$ étant inversible, **$U$ est semblable à $U^{-1}$**.
### Question 7
On a $D^\top=D$ et, $U$ étant inversible, $(U^{-1})^\top=(U^\top)^{-1}=L^{-1}$ ($L$ est inversible comme transposée d'une matrice inversible). En transposant $U=DU^{-1}D$ :
$$L=U^\top=D^\top(U^{-1})^\top D^\top=\boxed{DL^{-1}D=DL^{-1}D^{-1}},$$
donc **$L$ est semblable à $L^{-1}$**. On note pour la suite : $L_{i,j}=\binom ij$ et $(L^{-1})_{i,j}=(-1)^{i-j}\binom ij$.
### III — Une matrice diagonalisable semblable à son inverse
### Question 8
Pour $n=2$, $L=\begin{pmatrix}1&0&0\\1&1&0\\1&2&1\end{pmatrix}$ et
$$\boxed{S=LU=\begin{pmatrix}1&1&1\\1&2&3\\1&3&6\end{pmatrix}.}$$
$S^\top=U^\top L^\top=LU=S$ : $S$ est symétrique réelle, donc **diagonalisable** par le théorème spectral.
En développant selon la première ligne :
$$\chi_S(X)=\det\begin{pmatrix}X-1&-1&-1\\-1&X-2&-3\\-1&-3&X-6\end{pmatrix}=(X-1)(X^2-8X+3)-(X-3)-(X+1)=(X-1)(X^2-8X+1).$$
(Contrôles : coefficient de $X^2$ égal à $-9=-\operatorname{tr}S$, et $\chi_S(0)=-1=-\det S$ car $\det S=\det L\det U=1$.)
Le trinôme $X^2-8X+1$ a pour discriminant $60$ et pour racines $4\pm\sqrt{15}$, de produit $1$. Avec $\alpha=4+\sqrt{15}>1$, l'autre racine est $\frac1\alpha=4-\sqrt{15}$ :
$$\boxed{\operatorname{Sp}(S)=\left\{1,\ \alpha,\ \tfrac1\alpha\right\},\qquad \alpha=4+\sqrt{15}>1.}$$
### Question 9
- $S^\top=(LU)^\top=U^\top L^\top=LU=S$ : $S$ est symétrique réelle, donc **diagonalisable** (théorème spectral).
- $S=LU$ est un produit de matrices inversibles : **$S$ est inversible** et $S^{-1}=U^{-1}L^{-1}$.
- De Q7, $LD=DL^{-1}D^2=DL^{-1}$. Avec $DU=U^{-1}D$ (Q6) et $D^{-1}=D$ :
$$(DU)S(DU)^{-1}=DU\,LU\,U^{-1}D=(DU)(LD)=(U^{-1}D)(DL^{-1})=U^{-1}L^{-1}=S^{-1}.$$
Donc $\boxed{S^{-1}=(DU)S(DU)^{-1}}$ avec $DU$ inversible : **$S$ est semblable à son inverse**.
### Question 10
Soit $\lambda$ une valeur propre de $S$ (réelle, $S$ étant symétrique réelle) et $X\neq0$ tel que $SX=\lambda X$.
- D'une part, $X^\top SX=\lambda X^\top X=\lambda\|X\|^2$ avec $\|X\|^2=\sum_i x_i^2>0$.
- D'autre part, $S=U^\top U$, donc $X^\top SX=(UX)^\top(UX)=\|UX\|^2$, et $UX\neq0$ car $U$ est inversible et $X\neq0$.
Donc $\lambda=\dfrac{\|UX\|^2}{\|X\|^2}$ et $\boxed{\lambda>0}$.
### Question 11
$0\notin\operatorname{Sp}(S)$ (Q10), donc $x\mapsto\frac1x$ est définie sur $\operatorname{Sp}(S)$. Si $SX=\lambda X$ avec $X\neq0$, alors $S^{-1}X=\frac1\lambda X$ : $\frac1\lambda\in\operatorname{Sp}(S^{-1})$. Or $S^{-1}$ et $S$ sont semblables (Q9), donc ont le même polynôme caractéristique et le même spectre. Ainsi $\frac1\lambda\in\operatorname{Sp}(S)$ : **$\operatorname{Sp}(S)$ est stable par $x\mapsto\frac1x$.**
### Question 12
$A$ est inversible, d'inverse $A^{-1}=\operatorname{diag}(\frac12,\frac12,2)$, et $\operatorname{Sp}(A)=\{2,\frac12\}$ est stable par $x\mapsto\frac1x$. Mais
$$\operatorname{tr}A=\tfrac92\neq3=\operatorname{tr}A^{-1},$$
et deux matrices semblables ont la même trace ($\operatorname{tr}(PAP^{-1})=\operatorname{tr}(P^{-1}PA)=\operatorname{tr}A$). **Non** : une matrice inversible dont le spectre est stable par $x\mapsto\frac1x$ n'est pas toujours semblable à son inverse.
### IV — Calcul des coefficients de $S$ à l'aide d'un dénombrement dans un graphe
### Question 13
On suppose $n\ge2$. Après l'arc $s\to(0,0)$, un chemin vers $(2,2)$ comporte deux arcs « bas » $(i,j)\to(i+1,j)$ et deux arcs « droite » $(i,j)\to(i,j+1)$, dans un ordre quelconque :
$$\Omega_{2,2}=\left\{\begin{aligned}
&s\to(0,0)\to(1,0)\to(2,0)\to(2,1)\to(2,2),\\
&s\to(0,0)\to(1,0)\to(1,1)\to(2,1)\to(2,2),\\
&s\to(0,0)\to(1,0)\to(1,1)\to(1,2)\to(2,2),\\
&s\to(0,0)\to(0,1)\to(1,1)\to(2,1)\to(2,2),\\
&s\to(0,0)\to(0,1)\to(1,1)\to(1,2)\to(2,2),\\
&s\to(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)
\end{aligned}\right\},\qquad |\Omega_{2,2}|=6=\binom42.$$
Cas général. Chaque arc autre que $s\to(0,0)$ augmente de $1$ exactement une coordonnée. Un chemin de $s$ à $(i,j)$ est donc formé de $s\to(0,0)$ suivi de $i+j$ arcs, dont $i$ « bas » et $j$ « droite ». L'application qui associe à un chemin l'ensemble des rangs (dans $[\![1,i+j]\!]$) de ses arcs « bas » est :
- injective, car cet ensemble fixe la suite des déplacements, donc celle des sommets ;
- surjective, car toute partie à $i$ éléments de $[\![1,i+j]\!]$ définit une suite de déplacements de $(0,0)$ à $(i,j)$ dont les sommets intermédiaires ont des coordonnées dans $[\![0,\max(i,j)]\!]\subset[\![0,n]\!]$, donc un chemin de $G_n$.
C'est une bijection vers les parties à $i$ éléments d'un ensemble à $i+j$ éléments :
$$\boxed{\forall(i,j)\in[\![0,n]\!]^2,\quad |\Omega_{i,j}|=\binom{i+j}{i}.}$$
### Question 14
On munit $\Omega_{i,j}$ de la probabilité uniforme. Soit $k\in[\![0,i]\!]$ ; le sommet $(k,i-k)$ est dans $[\![0,n]\!]^2$. Un chemin de $A_k$ se coupe de façon unique en un chemin de $s$ à $(k,i-k)$, suivi d'un chemin de $(k,i-k)$ à $(i,j)$, et réciproquement toute telle concaténation est dans $A_k$.
- Chemins de $s$ à $(k,i-k)$ : $\binom{k+(i-k)}{k}=\binom ik$ (Q13).
- Chemins de $(k,i-k)$ à $(i,j)$ : $i-k$ arcs « bas » et $j-(i-k)$ arcs « droite », soit $j$ arcs ; le même argument qu'en Q13 en donne $\binom{j}{i-k}$. Si $i-k>j$, il n'y en a aucun (la seconde coordonnée ne décroît pas), ce qui est conforme à $\binom j{i-k}=0$.
$$\boxed{|A_k|=\binom ik\binom j{i-k}.}$$
Système complet : le long d'un chemin de $\Omega_{i,j}$, la somme des coordonnées vaut $0$ en $(0,0)$ et augmente de $1$ à chaque arc jusqu'à $i+j\ge i$. Le chemin passe donc par un et un seul sommet de somme $i$, de la forme $(k,i-k)$ avec $k\ge0$ et $k\le i$ (la première coordonnée croît jusqu'à $i$). Chaque chemin appartient à exactement un $A_k$ : les $A_k$, $k\in[\![0,i]\!]$, sont deux à deux incompatibles et de réunion $\Omega_{i,j}$, **ils forment un système complet d'événements**. Par conséquent :
$$\binom{i+j}{i}=|\Omega_{i,j}|=\sum_{k=0}^{i}|A_k|,\qquad\boxed{\binom{i+j}{i}=\sum_{k=0}^{i}\binom ik\binom j{i-k}.}$$
### Question 15
Comme $L_{i,k}=U_{k,i}=\binom ik$ et $U_{k,j}=\binom jk$ :
$$S_{i,j}=\sum_{k=0}^{n}\binom ik\binom jk=\sum_{k=0}^{i}\binom i{i-k}\binom jk=\sum_{m=0}^{i}\binom im\binom j{i-m}$$
(termes nuls pour $k>i$, symétrie $\binom ik=\binom i{i-k}$ pour $0\le k\le i$, puis $m=i-k$). D'après Q14 :
$$\boxed{\forall (i,j)\in[\![0,n]\!]^2,\quad S_{i,j}=\binom{i+j}{i}.}$$
Pour $n=2$ on retrouve la matrice de Q8.
## Partie B — Étude d'une suite et d'une série entière
### I — Étude d'une suite
### Question 16
$a_2=1\cdot(a_1+a_0)=1$ et $a_3=2(a_2+a_1)=2$ : $\boxed{a_2=1,\ a_3=2.}$
### Question 17
```python
def liste_an(n):
"""Renvoie la liste [a_0, a_1, ..., a_n]."""
if n == 0:
return [1]
a = [1, 0]
for k in range(1, n): # ajoute a_{k+1} = k * (a_k + a_{k-1})
a.append(k * (a[k] + a[k - 1]))
return a
```
Avant l'itération d'indice $k$, `a` vaut $[a_0,\dots,a_k]$ ; après la dernière ($k=n-1$), elle vaut $[a_0,\dots,a_n]$. `liste_an(6)` renvoie `[1, 0, 1, 2, 9, 44, 265]`.
### Question 18
Soit $\mathcal P(n)$ : « $a_n\in\mathbb N$ et $a_{n+1}\in\mathbb N$ ». $\mathcal P(0)$ est vraie ($a_0=1$, $a_1=0$). Si $\mathcal P(n)$ est vraie, $a_{n+2}=(n+1)(a_{n+1}+a_n)$ est un entier naturel comme produit et somme d'entiers naturels, donc $\mathcal P(n+1)$ est vraie. Par récurrence, $\boxed{\forall n\in\mathbb N,\ a_n\in\mathbb N.}$
### Question 19
Soit $\mathcal Q(n)$ : « $a_n\le n!$ et $a_{n+1}\le(n+1)!$ ». $\mathcal Q(0)$ est vraie ($1\le1$, $0\le1$). Si $\mathcal Q(n)$ est vraie, comme $n+1>0$ :
$$a_{n+2}=(n+1)(a_{n+1}+a_n)\le(n+1)\big((n+1)!+n!\big)=(n+1)\,n!\,(n+2)=(n+2)!.$$
Par récurrence, $\boxed{\forall n\in\mathbb N,\ a_n\le n!.}$
### Question 20
Le développement $e^x=\sum_{k=0}^{+\infty}\frac{x^k}{k!}$, valable pour tout réel $x$, donne en $x=-1$ : la série $\sum\frac{(-1)^k}{k!}$ **converge** et
$$\boxed{\sum_{k=0}^{+\infty}\frac{(-1)^k}{k!}=\frac1e,}\qquad S_n\xrightarrow[n\to+\infty]{}\frac1e.$$
Pour $p\in\mathbb N$ :
$$S_{2p+2}-S_{2p}=\frac1{(2p+2)!}-\frac1{(2p+1)!}\le0,\qquad S_{2p+3}-S_{2p+1}=\frac1{(2p+2)!}-\frac1{(2p+3)!}\ge0,\qquad S_{2p}-S_{2p+1}=\frac1{(2p+1)!}\to0.$$
Les suites $(S_{2p})$ (décroissante) et $(S_{2p+1})$ (croissante) sont adjacentes ; leur limite commune est $\frac1e$, et $S_{2p+1}\le\frac1e\le S_{2p}$ pour tout $p$. Ainsi :
$$\boxed{\forall n\in\mathbb N,\quad S_n\le\frac1e\le S_{n+1}\ (n\text{ impair})\quad\text{ou}\quad S_{n+1}\le\frac1e\le S_n\ (n\text{ pair}).}$$
Dans les deux cas $\frac1e$ est compris entre $S_n$ et $S_{n+1}$, d'où $\left|\frac1e-S_n\right|\le|S_{n+1}-S_n|=\frac1{(n+1)!}$.
### Question 21
Soit $\mathcal R(n)$ : « $a_n=n!S_n$ et $a_{n+1}=(n+1)!S_{n+1}$ ». $0!S_0=1=a_0$ et $1!S_1=0=a_1$. Si $\mathcal R(n)$ est vraie, avec $n!S_n=n!S_{n+1}-\frac{(-1)^{n+1}}{n+1}$ :
$$\begin{aligned}
a_{n+2}&=(n+1)\left((n+1)!S_{n+1}+n!S_{n+1}-\frac{(-1)^{n+1}}{n+1}\right)=(n+1)\,n!\,(n+2)\,S_{n+1}+(-1)^{n+2}\\
&=(n+2)!\left(S_{n+1}+\frac{(-1)^{n+2}}{(n+2)!}\right)=(n+2)!\,S_{n+2}.
\end{aligned}$$
Par récurrence, $\boxed{\forall n\in\mathbb N,\ a_n=n!\,S_n.}$
Soit $n\in\mathbb N^*$. Par Q20, $\left|\frac{n!}e-a_n\right|=n!\left|\frac1e-S_n\right|\le\frac{1}{n+1}$.
- Si $n\ge2$ : $\frac1{n+1}\le\frac13<\frac12$.
- Si $n=1$ : $\left|\frac1e-a_1\right|=\frac1e<\frac12$ car $e>2$.
Donc $\left|\frac{n!}e-a_n\right|<\frac12$, avec $a_n\in\mathbb Z$ (Q18). Si $m\in\mathbb Z$ vérifie aussi $\left|\frac{n!}e-m\right|<\frac12$, alors $|m-a_n|<1$, donc $m=a_n$. **Pour tout $n\in\mathbb N^*$, $a_n$ est l'unique entier tel que $\left|\frac{n!}e-a_n\right|<\frac12$ : c'est l'entier le plus proche de $\frac{n!}e$.**
### Question 22
$\frac{n!}e>0$ et $\dfrac{a_n}{n!/e}=e\,S_n\xrightarrow[n\to+\infty]{}1$ (Q20, Q21), donc $\boxed{a_n\underset{n\to+\infty}{\sim}\frac{n!}e.}$
### II — Étude d'une série entière
### Question 23
Posons $c_n=\frac{a_n}{n!}=S_n$ (Q21).
- $|c_n|\le\sum_{k=0}^{n}\frac1{k!}\le e$ ; pour $0\le r<1$, $(c_nr^n)$ est bornée, donc $R\ge r$, puis $R\ge1$.
- $c_n\to\frac1e>0$, donc $c_n\ge\frac1{2e}$ pour $n$ assez grand ; pour $r>1$, $c_nr^n\ge\frac{r^n}{2e}\to+\infty$, la suite n'est pas bornée, donc $R\le r$, puis $R\le1$.
Donc $\boxed{R=1}$.
Sur $]-1,1[$, $s$ est de classe $\mathcal C^\infty$ et se dérive terme à terme :
$$s'(x)=\sum_{n=1}^{+\infty}\frac{a_n}{(n-1)!}x^{n-1}=\sum_{m=0}^{+\infty}\frac{a_{m+1}}{m!}x^m.$$
D'où, toutes les séries convergeant sur $]-1,1[$ :
$$(1-x)s'(x)=\frac{a_1}{0!}+\sum_{m=1}^{+\infty}\left(\frac{a_{m+1}}{m!}-\frac{a_m}{(m-1)!}\right)x^m.$$
Pour $m\ge1$, $a_{m+1}-m\,a_m=m\,a_{m-1}$, donc $\frac{a_{m+1}}{m!}-\frac{a_m}{(m-1)!}=\frac{m\,a_{m-1}}{m!}=\frac{a_{m-1}}{(m-1)!}$. Avec $a_1=0$ :
$$(1-x)s'(x)=\sum_{m=1}^{+\infty}\frac{a_{m-1}}{(m-1)!}x^m=x\,s(x).$$
Comme $s(0)=a_0=1$, **$s$ est solution sur $]-1,1[$ du système $(1-x)y'-xy=0$, $y(0)=1$.**
### Question 24
Sur $I=]-1,1[$, $1-x>0$ et l'équation équivaut à $y'=a(x)y$ avec $a(x)=\frac{x}{1-x}=-1+\frac1{1-x}$, continue sur $I$. Une primitive est $A(x)=-x-\ln(1-x)$, et les solutions sur $I$ sont les $x\mapsto Ke^{A(x)}=K\frac{e^{-x}}{1-x}$, $K\in\mathbb R$. La condition $y(0)=1$ impose $K=1$. Comme $s$ est solution (Q23) :
$$\boxed{\forall x\in\,]-1,1[,\quad s(x)=\frac{e^{-x}}{1-x}.}$$
### Question 25
Pour $x\in\,]-1,1[$, $f(x)=e^xs(x)=\frac1{1-x}$. Par récurrence immédiate, $f^{(p)}(x)=\frac{p!}{(1-x)^{p+1}}$, donc $f^{(p)}(0)=p!$.
Les coefficients d'une série entière de rayon $R>0$ sont liés aux dérivées de sa somme en $0$ par $c_k=\frac{s^{(k)}(0)}{k!}$. Ici $c_k=\frac{a_k}{k!}$, donc $\boxed{s^{(k)}(0)=a_k}$ pour tout $k\in\mathbb N$.
$\exp$ et $s$ sont de classe $\mathcal C^\infty$ sur $]-1,1[$ ; la formule de Leibniz donne
$$f^{(p)}(0)=\sum_{k=0}^{p}\binom pk\exp^{(p-k)}(0)\,s^{(k)}(0)=\sum_{k=0}^{p}\binom pk a_k.$$
Donc
$$\boxed{\forall p\in\mathbb N\ (\text{en particulier }\forall p\in[\![0,n]\!]),\quad p!=\sum_{k=0}^{p}\binom pk a_k.}$$
(Contrôle $p=3$ : $1+0+3\cdot1+2=6$.)
## Partie C — Permutations de $[\![1,n]\!]$
### I — Représentations d'une permutation
### Question 26
On lit le $1$ de chaque ligne $i$ en colonne $\sigma(i)$ : $\sigma(1)=1$, $\sigma(2)=4$, $\sigma(3)=3$, $\sigma(4)=2$. Le graphe $G(\sigma)$ a quatre sommets et les arcs $1\to1$, $3\to3$ (deux **boucles**), $2\to4$ et $4\to2$ (une **bi-boucle** $2\to4\to2$).
### Question 27
Sur la figure 5 : $1\to2$, $2\to4$, $4\to3$, $3\to1$ et la boucle $5\to5$. Donc $\sigma(1)=2$, $\sigma(2)=4$, $\sigma(3)=1$, $\sigma(4)=3$, $\sigma(5)=5$, et
$$\boxed{M(\sigma)=\begin{pmatrix}0&1&0&0&0\\0&0&0&1&0\\1&0&0&0&0\\0&0&1&0&0\\0&0&0&0&1\end{pmatrix}.}$$
### II — Propriétés
### Question 28
Pour $\tau\in\mathcal S_n$, $M(\tau)_{i,j}=\delta_{j,\tau(i)}$ (symbole de Kronecker). Pour $(i,j)\in[\![1,n]\!]^2$ :
$$\big(M(\sigma)M(\sigma^{-1})\big)_{i,j}=\sum_{k=1}^{n}\delta_{k,\sigma(i)}\,\delta_{j,\sigma^{-1}(k)}=\delta_{j,\sigma^{-1}(\sigma(i))}=\delta_{j,i},$$
seul le terme $k=\sigma(i)$ pouvant être non nul. Donc $M(\sigma)M(\sigma^{-1})=I_n$. Une matrice carrée qui admet un inverse à droite est inversible, d'inverse celui-ci :
$$\boxed{M(\sigma)^{-1}=M(\sigma^{-1}).}$$
### Question 29
$G(\sigma^{-1})$ a un arc $i\to j$ si et seulement si $\sigma^{-1}(i)=j$, c'est-à-dire $\sigma(j)=i$, c'est-à-dire si $G(\sigma)$ a l'arc $j\to i$ : **$G(\sigma^{-1})$ s'obtient en renversant tous les arcs de $G(\sigma)$.**
De même, $M(\sigma^{-1})_{i,j}=1\iff\sigma^{-1}(i)=j\iff\sigma(j)=i\iff M(\sigma)_{j,i}=1$ ; les coefficients valant $0$ ou $1$, **$M(\sigma^{-1})$ est la transposée de $M(\sigma)$.** Avec Q28 :
$$\boxed{M(\sigma)^{-1}=M(\sigma^{-1})=M(\sigma)^\top.}$$
### Question 30
$\sigma^2=\sigma\circ\sigma\in\mathcal S_n$ et, pour $(i,j)\in[\![1,n]\!]^2$,
$$\big(M(\sigma)^2\big)_{i,j}=\sum_{k=1}^{n}\delta_{k,\sigma(i)}\,\delta_{j,\sigma(k)}=\delta_{j,\sigma(\sigma(i))}=M(\sigma^2)_{i,j}.$$
Donc $\boxed{M(\sigma^2)=M(\sigma)^2.}$
### III — Matrices de permutation diagonalisables
### Question 31
« La matrice introduite en Q25 » est une coquille : il s'agit de la matrice $N$ de la figure 4 (Q26), seule matrice $4\times4$ compatible avec le polynôme annoncé.
$$\chi_N=\det\begin{pmatrix}X-1&0&0&0\\0&X&0&-1\\0&0&X-1&0\\0&-1&0&X\end{pmatrix}=(X-1)^2\det\begin{pmatrix}X&-1\\-1&X\end{pmatrix}=(X-1)^2(X^2-1),$$
en développant selon la première colonne puis selon la ligne de $X-1$. Donc $\boxed{\chi_N=(X-1)^3(X+1)}$.
$N-I_4$ a deux lignes nulles et deux lignes opposées $(0,-1,0,1)$ et $(0,1,0,-1)$ : $\operatorname{rg}(N-I_4)=1$, $\dim\ker(N-I_4)=3$, égal à la multiplicité de $1$. Pour $-1$, valeur propre simple, $\dim\ker(N+I_4)=1$. La somme des dimensions vaut $4$ : **$N$ est diagonalisable.** C'est cohérent avec le théorème : d'après Q26, $G(\sigma)$ ne contient que deux boucles et une bi-boucle.
### Question 32
$M=M(\sigma)$ est supposée diagonalisable dans $\mathcal M_n(\mathbb R)$ : ses valeurs propres sont réelles. Soit $\lambda$ l'une d'elles et $X\in\mathcal M_{n,1}(\mathbb R)$ non nul avec $MX=\lambda X$. Par Q29, $M^\top M=I_n$. Alors
$$\|X\|^2=X^\top M^\top MX=(MX)^\top(MX)=\lambda^2\|X\|^2,$$
et $\|X\|^2>0$, donc $\boxed{\lambda^2=1.}$
### Question 33
Il existe $P\in GL_n(\mathbb R)$ et $\Delta=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ telles que $M(\sigma)=P\Delta P^{-1}$, les $\lambda_i$ étant les valeurs propres de $M(\sigma)$ ; par Q32, $\lambda_i\in\{-1,1\}$. Soit $q\in[\![0,n]\!]$ le nombre de $\lambda_i$ égaux à $1$. En réordonnant les colonnes de $P$ (les vecteurs propres), on peut supposer $\lambda_1=\dots=\lambda_q=1$ et $\lambda_{q+1}=\dots=\lambda_n=-1$. Ainsi **$M(\sigma)$ est semblable à $\Delta_q=\operatorname{diag}(1,\dots,1,-1,\dots,-1)$** ($q$ fois $1$, $n-q$ fois $-1$).
### Question 34
$\Delta_q^2=I_n$, donc $M(\sigma)^2=P\Delta_q^2P^{-1}=I_n$. Par Q30, $M(\sigma^2)=M(\sigma)^2=I_n=M(\mathrm{id})$, et $M$ est injective, donc $\boxed{\sigma^2=\mathrm{id}.}$
Les arcs de $G(\sigma)$ sont les $i\to\sigma(i)$. Soit $i\in[\![1,n]\!]$ et $j=\sigma(i)$. Si $j=i$, l'arc est une boucle. Sinon $\sigma(j)=\sigma^2(i)=i$, donc l'arc $j\to i$ existe et $i\to j\to i$ est une bi-boucle. **$G(\sigma)$ ne contient que des boucles ou des bi-boucles.**
### Question 35
Réciproquement, supposons que $G(\sigma)$ ne contienne que des boucles et des bi-boucles. Soit $i\in[\![1,n]\!]$, $j=\sigma(i)$ : si $j=i$, $\sigma^2(i)=i$ ; sinon l'arc $i\to j$ est dans une bi-boucle, donc $\sigma(j)=i$ et $\sigma^2(i)=i$. Ainsi $\sigma^2=\mathrm{id}$ et, par Q30, $M^2=I_n$ où $M=M(\sigma)$.
Soit $x\in\mathcal M_{n,1}(\mathbb R)$. En posant $x_+=\frac{x+Mx}2$ et $x_-=\frac{x-Mx}2$, on a $x=x_++x_-$, $Mx_+=x_+$ et $Mx_-=-x_-$ (car $M^2x=x$). Donc $\mathcal M_{n,1}(\mathbb R)=E_1+E_{-1}$ avec $E_{\pm1}=\ker(M\mp I_n)$, et la somme est directe ($Mx=x=-x$ impose $x=0$). Si $E_1$ et $E_{-1}$ sont non nuls, ce sont les deux sous-espaces propres de $M$, de somme égale à l'espace : $M$ est diagonalisable. Si l'un est nul, $M=\pm I_n$ est diagonale.
(Autre preuve, explicite : $Me_j=e_{\sigma(j)}$ car $\sigma=\sigma^{-1}$. Pour chaque boucle $i$, $Me_i=e_i$ ; pour chaque bi-boucle $\{i,j\}$, $M(e_i+e_j)=e_i+e_j$ et $M(e_i-e_j)=-(e_i-e_j)$. Ces $n$ vecteurs forment une base de vecteurs propres.)
**$M(\sigma)$ est diagonalisable**, ce qui achève la preuve du théorème : $M(\sigma)$ est diagonalisable si et seulement si $G(\sigma)$ ne contient que des boucles ou des bi-boucles.
## Partie D — Graphes de permutations sans boucle
### I — Introduction
### Question 36
$G$ est une bijection de $\mathcal S_n$ sur $G(\mathcal S_n)$, donc $\boxed{|G(\mathcal S_n)|=|\mathcal S_n|=n!}$.
Une boucle de $G(\sigma)$ est un point fixe de $\sigma$ : $X_n$ compte les points fixes. Si $\sigma$ fixait exactement $n-1$ éléments, l'élément restant $i_0$ ne pourrait avoir pour image aucun des $n-1$ autres (déjà atteints, $\sigma$ injective), donc $\sigma(i_0)=i_0$ : contradiction. Toute autre valeur $j\in[\![0,n]\!]$, $j\neq n-1$, est atteinte : on fixe $j$ éléments et l'on permute circulairement les $m=n-j$ autres ($c_1\to c_2\to\dots\to c_m\to c_1$, sans point fixe si $m\ge2$ ; rien à faire si $m=0$). Donc
$$\boxed{X_n(\Omega)=[\![0,n]\!]\setminus\{n-1\}}\qquad(\text{pour }n=1 :\ \{1\}).$$
### Question 37
**Convention.** Avec $b_0=0$, la formule serait fausse pour $j=n$ : l'identité est la seule permutation à $n$ points fixes, donc $P(X_n=n)=\frac1{n!}$, alors que le membre de droite vaudrait $\frac{b_0}{n!}=0$. On adopte $\boxed{b_0=1}$ (la permutation de l'ensemble vide n'a pas de point fixe) ; c'est la seule valeur qui rend vraies les formules de Q37 et Q38.
L'univers $G(\mathcal S_n)$ est muni de la probabilité uniforme ; via $G$, cela revient à tirer $\sigma$ uniformément dans $\mathcal S_n$. Soit $j\in[\![0,n]\!]$. Une permutation à exactement $j$ points fixes est déterminée par :
- l'ensemble $F$ de ses points fixes, de cardinal $j$ : $\binom nj$ choix ;
- sa restriction au complémentaire de $F$ (stable par $\sigma$, de cardinal $n-j$), qui est une permutation sans point fixe : $b_{n-j}$ choix, ce nombre ne dépendant que du cardinal.
Réciproquement, tout tel couple définit une permutation à exactement $j$ points fixes. Donc
$$\boxed{\forall j\in[\![0,n]\!],\quad P(X_n=j)=\frac{\binom nj\,b_{n-j}}{n!}.}$$
### Question 38
Les événements $(X_n=j)$, $j\in[\![0,n]\!]$, forment un système complet (celui d'indice $n-1$ étant impossible), donc
$$1=\sum_{j=0}^{n}\frac{\binom nj\,b_{n-j}}{n!},\qquad\text{soit}\qquad n!=\sum_{j=0}^{n}\binom n{n-j}b_{n-j}=\sum_{k=0}^{n}\binom nk b_k\quad(k=n-j).$$
Les $b_k$ ne dépendent pas de $n$ ($b_k$ est le nombre de permutations sans point fixe d'un ensemble à $k$ éléments). Pour $p\in[\![1,n]\!]$, le même raisonnement dans $\mathcal S_p$ donne la relation au rang $p$ ; pour $p=0$ elle s'écrit $0!=b_0$, vraie avec $b_0=1$. Donc
$$\boxed{\forall p\in[\![0,n]\!],\quad p!=\sum_{k=0}^{p}\binom pk b_k.}$$
### Question 39
Le terme $k=p$ ayant pour coefficient $\binom pp=1$, la relation au rang $p\ge1$ s'écrit
$$b_p=p!-\sum_{k=0}^{p-1}\binom pk b_k :$$
partant de $b_0=1$, elle détermine de proche en proche $b_1,\dots,b_n$ (système triangulaire à diagonale de $1$). On obtient
$$b_1=1-1=0,\qquad b_2=2-1-2\cdot0=1,\qquad b_3=6-1-3\cdot0-3\cdot1=2 :\qquad\boxed{b_1=0,\ b_2=1,\ b_3=2.}$$
(Contrôle : sur $[\![1,3]\!]$, seuls les deux $3$-cycles sont sans point fixe.)
### II — Calcul d'une probabilité par deux méthodes
### Question 40
L'étude de la série entière de somme $s$ a fourni (Q25) $p!=\sum_{k=0}^{p}\binom pk a_k$ pour tout $p$, et Q38 donne la même relation pour les $b_k$, $p\in[\![0,n]\!]$. Montrons par récurrence forte que $a_p=b_p$ pour $p\in[\![0,n]\!]$ : en $p=0$, $a_0=b_0=1$ ; si $a_k=b_k$ pour $k<p$, la différence des deux relations au rang $p$ donne $0=\binom pp(a_p-b_p)=a_p-b_p$. Donc $b_n=a_n=n!S_n$ (Q21). Comme $B_n=(X_n=0)$ a pour cardinal $b_n$ dans un univers équiprobable de cardinal $n!$ :
$$\boxed{P(B_n)=\frac{b_n}{n!}=S_n=\sum_{k=0}^{n}\frac{(-1)^k}{k!}.}$$
### Question 41
$L$ est inversible et $(L^{-1})_{i,j}=(-1)^{i-j}\binom ij$ (Q7). Pour $i\in[\![0,n]\!]$ :
$$(L^{-1}F)_i=\sum_{j=0}^{i}(-1)^{i-j}\frac{i!}{j!\,(i-j)!}\,j!=i!\sum_{j=0}^{i}\frac{(-1)^{i-j}}{(i-j)!}=i!\sum_{m=0}^{i}\frac{(-1)^m}{m!}=i!\,S_i,$$
$$\boxed{L^{-1}F=\begin{pmatrix}0!\,S_0\\1!\,S_1\\\vdots\\n!\,S_n\end{pmatrix}.}$$
Avec $B=(b_0,\dots,b_n)^\top$, $(LB)_i=\sum_{j=0}^{i}\binom ij b_j=i!=F_i$ par Q38 : $LB=F$, donc $B=L^{-1}F$ et $b_i=i!\,S_i$ pour tout $i$. En particulier
$$\boxed{P(B_n)=\frac{b_n}{n!}=\sum_{k=0}^{n}\frac{(-1)^k}{k!},}$$
retrouvé sans utiliser la partie B.
Aide sur le corrigé
Connectez-vous pour demander une explication.