Inversion de Pascal et dénombrement

On considère l'espace vectoriel $E = \mathbb{R}_n[X]$ muni de sa base canonique $\mathcal{B} = (1, X, \dots, X^n)$ .

On définit la matrice $M \in \mathrm{M}_{n+1}(\mathbb{R})$ par ses coefficients $m_{i,j} = \binom{j}{i}$ pour $0 \leqslant i, j \leqslant n$ (avec la convention $\binom{j}{i} = 0$ si $i > j$ ). Justifier que $M$ est inversible et déterminer l'expression des coefficients de son inverse $M^{-1}$ .
Soient $(a_p)_{p \in \mathbb{N}}$ et $(b_p)_{p \in \mathbb{N}}$ deux suites réelles. On suppose que pour tout entier $n \in \mathbb{N}$ , on a la relation : $b_n = \sum_{j=0}^n \binom{n}{j} a_j$ En utilisant un argument matriciel, démontrer que pour tout $n \in \mathbb{N}$ : $a_n = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} b_j$
Soit $n, k \in \mathbb{N}^*$ . On note $S_{n,k}$ le nombre de surjections d'un ensemble à $n$ éléments vers un ensemble à $k$ éléments. Par des considérations de dénombrement, établir une relation entre $k^n$ et les valeurs $S_{n,j}$ pour $1 \leqslant j \leqslant k$ . En déduire une expression explicite de $S_{n,k}$ sous forme de somme.

1.

Pour la question 1, interpréter $M$ comme la matrice d'un endomorphisme de translation $P(X) \mapsto P(X+1)$ . L'inverse correspondra alors à une translation inverse.

2.

Pour la question 2, remarquer que la relation définit un système triangulaire. Identifier la matrice du système à partir de la question précédente (ou sa transposée).

3.

Pour la question 3, dénombrer l'ensemble de toutes les applications de $\llbracket 1, n \rrbracket$ dans $\llbracket 1, k \rrbracket$ en les classant selon le cardinal de leur image. Utiliser ensuite la formule d'inversion établie à la question 2.

Idées clés

•

Interprétation d'une matrice comme représentation d'un opérateur polynomial.

•

Lien entre inversion de matrices et formules d'inversion de suites.

•

Partition de l'ensemble des applications par la taille de l'image.

Résolution.

Considérons l'endomorphisme $f$ de $E = \mathbb{R}_n[X]$ défini par : $\forall P \in E, f(P) = P(X+1)$ Calculons l'image de la base canonique par $f$ . Pour tout $j \in \{0, \dots, n\}$ , on a par la formule du binôme de Newton : $f(X^j) = (X+1)^j = \sum_{i=0}^j \binom{j}{i} X^i$ La matrice de $f$ dans la base $\mathcal{B} = (1, X, \dots, X^n)$ est donc exactement la matrice $M$ donnée par l'énoncé, puisque le coefficient à la ligne $i$ et la colonne $j$ est le coefficient de $X^i$ dans $f(X^j)$ . L'application $f$ est clairement un automorphisme car elle admet pour application réciproque $g : P(X) \mapsto P(X-1)$ . En effet : $f \circ g (P) = g(P)(X+1) = P((X+1)-1) = P(X)$ La matrice $M$ est donc inversible et $M^{-1}$ est la matrice de $g$ dans la base $\mathcal{B}$ . Calculons $g(X^j)$ : $g(X^j) = (X-1)^j = \sum_{i=0}^j \binom{j}{i} (-1)^{j-i} X^i$ Par identification, les coefficients $m'_{i,j}$ de $M^{-1}$ sont : $\boxed{ m'_{i,j} = (-1)^{j-i} \binom{j}{i} }$
Soit $n \in \mathbb{N}$ fixé. Considérons les vecteurs colonnes $A = (a_0, \dots, a_n)^T$ and $B = (b_0, \dots, b_n)^T$ . La relation $b_i = \sum_{j=0}^i \binom{i}{j} a_j$ s'écrit matriciellement $B = L A$ où $L$ est la matrice triangulaire inférieure définie par $L_{i,j} = \binom{i}{j}$ . On remarque que $L$ est la transposée de la matrice $M$ étudiée à la question précédente ( $L = M^T$ ). L'inversibilité de $M$ entraîne celle de $L$ , et on a $A = L^{-1} B = (M^T)^{-1} B = (M^{-1})^T B$ . Le coefficient de la ligne $n$ de $A$ est donc : $a_n = \sum_{j=0}^n (L^{-1})_{n,j} b_j = \sum_{j=0}^n (M^{-1})_{j,n} b_j$ En utilisant l'expression trouvée en 1 : $\boxed{ a_n = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} b_j }$
Soit $E$ $E$ un ensemble à $n$ $n$ éléments et $F$ $F$ un ensemble à $k$ $k$ éléments. Le nombre total d'applications de $E$ $E$ vers $F$ $F$ est $k^n$ $k^{n}$ . Toute application $f : E \to F$ $f : E \to F$ possède une image $f(E) \subseteq F$ $f (E) \subseteq F$ de cardinal $j \in \{1, \dots, k\}$ $j \in {1, \dots, k}$ . On peut donc partitionner l'ensemble des applications selon le cardinal de leur image :
- On choisit une partie $J \subseteq F$ de cardinal $j$ : il y a $\binom{k}{j}$ choix.
- On compte le nombre de surjections de $E$ vers $J$ : il y a $S_{n,j}$ telles surjections.
On en déduit la relation :
$k^n = \sum_{j=1}^k \binom{k}{j} S_{n,j}$
Cette formule est identique à celle de la question 2 (en posant $b_k = k^n$ $b_{k} = k^{n}$ , $a_j = S_{n,j}$ $a_{j} = S_{n, j}$ et en remarquant que $S_{n,0}=0$ $S_{n, 0} = 0$ pour $n \geqslant 1$ $n ⩾ 1$ ). Par application immédiate de la formule d'inversion :
$\boxed{ S_{n,k} = \sum_{j=1}^k (-1)^{k-j} \binom{k}{j} j^n }$

Attention à l'ordre des indices dans la matrice. La matrice $M$ de l'opérateur de translation est classiquement triangulaire supérieure, alors que la relation sur les suites fait apparaître une matrice triangulaire inférieure. Le passage par la transposée est essentiel.