Matrice de Pascal et inversion binomiale

Résolution.

1. Considérons l'application $\phi : \mathbb{R}_n[X] \to \mathbb{R}_n[X]$ définie par $\phi(P) = P(X+1)$. C'est clairement un endomorphisme par linéarité de la dérivation et de l'évaluation. Cherchons sa matrice dans la base canonique $\mathcal{B} = (1, X, X^2, \dots, X^n)$. D'après la formule du binôme de Newton :
   $$\phi(X^j) = (X+1)^j = \sum_{i=0}^j \binom{j}{i} X^i$$
   Les coordonnées de $\phi(X^j)$ dans $\mathcal{B}$ sont exactement les coefficients $\binom{j}{i}$ pour $0 \leqslant i \leqslant j$. Ainsi, on a bien :
   $$\boxed{\text{Mat}_{\mathcal{B}}(\phi) = M}$$

2. La matrice $M$ est triangulaire supérieure. Ses coefficients diagonaux sont $m_{i,i} = \binom{i}{i} = 1$. Le spectre de $M$ est réduit au singleton $\{1\}$. Si $M$ était diagonalizable, elle serait semblable à la matrice identité $I_{n+1}$. Or, une matrice semblable à $I_{n+1}$ est égale à $I_{n+1}$. Comme $M \neq I_{n+1}$ (car $m_{0,1} = \binom{1}{0} = 1 \neq 0$ dès que $n \geqslant 1$), on en déduit :
   $$\boxed{M \text{ n'est pas diagonalizable pour } n \geqslant 1}$$

3. Soit $N = M - I_{n+1}$. Elle représente l'endomorphisme $\Delta = \phi - \text{id}$, tel que $\Delta(P) = P(X+1) - P(X)$. Si $\deg(P) = d \geqslant 1$, alors $\deg(\Delta(P)) = d-1$. En effet, le terme en $X^d$ s'annule :
   $$(X+1)^d - X^d = (X^d + dX^{d-1} + \dots) - X^d = dX^{d-1} + \dots$$
   Si $P$ est constant et non nul, $\Delta(P) = 0$. Par récurrence, $\Delta^k(P)$ est de degré $\deg(P) - k$ (avec la convention $\deg(0) = -\infty$). On en déduit que $\Delta^n(X^n)$ est un polynôme de degré 0 (une constante non nulle), donc $\Delta^n \neq 0$. En revanche, $\Delta^{n+1}(P) = 0$ pour tout $P \in \mathbb{R}_n[X]$. L'ordre de nilpotence de $N$ est donc :
   $$\boxed{k = n+1}$$

4. L'endomorphisme $\phi$ est bijectif. Son application réciproque est $\phi^{-1}(P) = P(X-1)$. En effet, $\phi(\phi^{-1}(P)) = P((X-1)+1) = P(X)$. La matrice $M^{-1}$ est donc la matrice de $\phi^{-1}$ dans la base $\mathcal{B}$. En utilisant à nouveau le binôme de Newton :
   $$\phi^{-1}(X^j) = (X-1)^j = \sum_{i=0}^j \binom{j}{i} (-1)^{j-i} X^i$$
   On en déduit que le coefficient $(i,j)$ de $M^{-1}$ est :
   $$\boxed{(M^{-1})_{i,j} = \begin{cases} (-1)^{j-i} \binom{j}{i} & \text{si } i \leqslant j$$
   0 & \text{sinon} \end{cases}}

5. Soient $A = (a_0, \dots, a_n)^T$ et $B = (b_0, \dots, b_n)^T$ les vecteurs colonnes associés aux suites. La relation $b_p = \sum_{j=0}^p \binom{p}{j} a_j$ se traduit matriciellement par $B = M^T A$. Puisque $M$ est inversible, $M^T$ l'est aussi et $(M^T)^{-1} = (M^{-1})^T$. L'égalité est donc équivalente à $A = (M^{-1})^T B$. En explicitant les coefficients de $(M^{-1})^T$, on obtient :
   $$a_p = \sum_{j=0}^n ((M^{-1})^T)_{p,j} b_j = \sum_{j=0}^p (M^{-1})_{j,p} b_j$$
   D'après la question précédente, $(M^{-1})_{j,p} = (-1)^{p-j} \binom{p}{j}$, d'où :
   $$\boxed{a_p = \sum_{j=0}^p (-1)^{p-j} \binom{p}{j} b_j}$$

6. Soit $\mathcal{F}$ l'ensemble des applications de $E = \llbracket 1, n \rrbracket$ vers $F = \llbracket 1, k \rrbracket$. On a $|\mathcal{F}| = k^n$. On peut partitionner $\mathcal{F}$ selon l'image $J = f(E) \subseteq F$.
   $$k^n = \sum_{J \subseteq F} |\{ f : E \to J, f \text{ surjective} \}|$$
   Si $|J| = j$, il y a $S_{n,j}$ surjections de $E$ vers $J$. Comme il y a $\binom{k}{j}$ sous-ensembles $J$ de taille $j$ dans $F$, on a :
   $$k^n = \sum_{j=0}^k \binom{k}{j} S_{n,j}$$
   C'est exactement la forme $b_k = \sum_{j=0}^k \binom{k}{j} a_j$ avec $b_k = k^n$ et $a_j = S_{n,j}$. Par la formule d'inversion démontrée en question 5, on conclut :
   $$\boxed{S_{n,k} = \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n}$$