Inversion de Pascal

On considère deux suites de réels $(a_k)$ et $(b_k)$ reliées par la relation
$\forall n\in\N, b_n=\sum_{k=0}^n \binom{n}{k}\,a_k.$ On cherche alors à exprimer les $a_n$ uniquement en fonction des $b_k$ , soit à inverser cette formule.

On définit $\varphi$ l'endomorphisme de $\mathbb{R}[X]$ tel que $\varphi(P)(X)=P(X+1)$ pour tout $P\in\mathbb{R}[X]$ . On rappelle que la base canonique de $\R[X]$ est la famille $(X^n)_{n\in\N}=(1,X,X^2,\dots)$ .

Montrer que $\varphi$ est bijectif. On pourra pour cela chercher à exhiber sa réciproque^EN.
Déterminer la matrice de $\varphi$ dans la base canonique et montrer qu’elle est triangulaire supérieure.
Déterminer l’inverse de la matrice de la question précédente.
En déduire la formule d'inversion de Pascal
$\forall n\in\N, a_n=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k} \,b_k.$
Application: On note $d_n$ le nombre de permutations de taille $n$ sans point fixe. Montrer que $n!=\sum_{k=0}^n\binom{n}{k} d_k$ puis utiliser la formule d’inversion de Pascal pour en déduire que:
$\forall n\in\N, d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.$

I solved itMark it done Add to my listKeep it in your list

I like this problem6 likes

Liked by

Solutions

Reveal solutionsAre you sure? Give it a try first.

Community accepted

Solution by Darius CHITU

Discussions4 useful votes

Soit $\phi \in \text{End}(\mathbb{R}[X])$ tel que $\phi(P)(X)=P(X-1)$ pour tout $P \in \R[X]$ . Comme $(\varphi \circ \phi)(P)(X)= P(X)$ et aussi $(\phi \circ \varphi)(P)(X) = P(X)$ pour tout $P \in \R[X]$ , on déduit que $\varphi$ est bijectif et que $\varphi^{-1} = \phi$ .
En remarquant que $\varphi(X^{j}) = (X+1)^j = \sum_{0 \leqslant i \leqslant j} C_{j}^{i} X^{i}$ pour tout $j \in \mathbb{N}$ , la matrice de l’endomorphisme $\varphi$ dans la base canonique $\mathcal{B}=(1,X,X^{2},\ldots)$ satisfait la relation suivante :
$\forall i,j \in \N: \ \left( M_{\varphi, \mathcal{B}} \right)_{i,j} = \begin{cases} C_{j}^{i} &\text{ si } i \leqslant j \\ 0 &\text{ si } i > j \end{cases},$ ce qui montre que la matrice inversible $M_{\varphi,\mathcal{B}}$ est triangulaire supérieure.
On rappelle que $M_{\varphi,\mathcal{B}}^{-1} = M_{\varphi^{-1}, \mathcal{B}}$ . Car $\varphi^{-1} (X^{j}) = (X-1)^{j} = \sum_{0 \leqslant i \leqslant j} (-1)^{j-i} C_j^{i} X^{i}$ pour tout $j \in \N$ , on peut écrire de la même manière que la matrice de $\varphi^{-1}$ dans la base canonique $\mathcal{B}$ satisfait cette relation :
$\forall i,j \in \N: \ \left( M_{\varphi,\mathcal{B}}^{{-1}} \right)_{i,j}=\left( M_{\varphi^{-1}, \mathcal{B}} \right)_{i,j} = \begin{cases} (-1)^{j-i}C_{j}^{i} &\text{ si } i \leqslant j \\ 0 &\text{ si } i > j \end{cases}.$
La relation exprimée dans l’énoncé s’écrit avec les vecteurs ligne ${v}_{a}=(a_{0},a_{1}, a_{2}, \ldots)$ et $v_{b} = (b_{0}, b_{1}, b_{2},\ldots)$ comme $v_{b} = v_{a} \cdot M_{\varphi,\mathcal{B}}$ . En multipliant à droite par l’inverse de la matrice, on a $v_{a} = v_{b} \cdot M_{\varphi,\mathcal{B}}^{-1}$ , ce qui implique évidemment la formule d’inversion de Pascal:
$\forall n \in \N: \ a_{n} = \sum_{k=0}^{n} \left( M_{\varphi,\mathcal{B}}^{{-1}} \right)_{k,n} b_{k} = \sum_{k=0}^{n} (-1)^{n-k} C_{n}^{k} b_{k}.$
On comptera le nombre de permutations de taille $n$ de deux façons. Premièrement, leur nombre est $|\mathcal{S}_{n}| =n!$ . Deuxièmement, le nombre de permutations de taille $n$ est la somme des permutations de taille $n$ avec $n-k$ points fixes, où $k \in \llbracket 0,n \rrbracket$ . Pour ce type de permutations, on choisit d’abord les positions de ces points fixes, pour lesquelles on a $C_{n}^{n-k} = C_{n}^{k}$ possibilités, et ensuite on peut permuter les $k$ positions restantes, action pour laquelle on a $d_{k}$ possibilités. Enfin, le nombre de permutations de taille $n$ est $|\mathcal{S}_n| = \sum_{0 \leqslant k \leqslant n} C_{n}^{k} d_{k}$ .
Ainsi, $n! = \sum_{0 \leqslant k \leqslant n} C_{n}^{k} d_{k}$ et, par la formule d’inversion de Pascal, on arrive à la conclusion:
$d_{n} = \sum_{k=0}^{n} (-1)^{n-k} C_{n}^{k} k! = \sum_{k=0}^{n} (-1)^{k} C_{n}^{n-k} (n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}.$

Report