Formule d'inversion de Pascal

Soit ${\displaystyle (a_{k})_{k\in \mathbb {N} }}$ et ${\displaystyle (b_{k})_{k\in \mathbb {N} }}$ deux suites à valeurs dans un groupe abélien, par exemple (ℝ, +). Pour tout entier naturel ${\displaystyle n}$, on a

${\displaystyle \forall p\in \{0,\dots ,n\}\quad b_{p}=\sum _{k=0}^{p}{p \choose k}a_{k}}$

si et seulement si

${\displaystyle \forall p\in \{0,\dots ,n\}\quad a_{p}=(-1)^{p}\sum _{k=0}^{p}(-1)^{k}{p \choose k}b_{k}}$,

où les ${\displaystyle {p \choose k}}$ désignent les coefficients binomiaux.

Deux suites ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ et ${\displaystyle (b_{n})_{n\in \mathbb {N} }}$ sont liées par ${\displaystyle b_{p}=\sum _{k=0}^{p}{p \choose k}a_{k}}$ si et seulement si leurs séries formelles génératrices exponentielles ${\displaystyle A}$ et ${\displaystyle B}$ vérifient ${\displaystyle B(X)=\mathrm {e} ^{X}A(X)}$.

On a alors ${\displaystyle A(-X)=\mathrm {e} ^{X}B(-X)}$, c'est-à-dire (d'après cette même équivalence) ${\displaystyle (-1)^{p}a_{p}=\sum _{k=0}^{p}{p \choose k}(-1)^{k}b_{k}}$.

Pour d'autres démonstrations, voir le § « Formulation alternative » de l'article sur la transformation binomiale (qui utilise le théorème d'interpolation de Newton) et la leçon « Formule d'inversion de Pascal » sur Wikiversité.

On peut se servir de cette formule en dénombrement, en particulier pour calculer le nombre de dérangements d'un ensemble fini ou le nombre de surjections d'un ensemble fini vers un autre.

Cette section ne cite pas suffisamment ses sources (décembre 2016). 

Pour l'améliorer, ajoutez des références de qualité et vérifiables (comment faire ?) ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Une autre version de cette inversion avec ${\displaystyle T^{k}}$ au lieu de ${\displaystyle {p \choose k}}$ :

Soit un polynôme

${\displaystyle Q(T)=\sum _{k=0}^{m}c_{k}T^{k}}$

(à coefficients dans un anneau, ou même seulement un groupe abélien), on a

${\displaystyle \sum _{j=0}^{m}{(-1)^{m-j}{m \choose j}Q(X+j)}=m!\,c_{m}}$.

En effet, la m-ième différence finie de ${\displaystyle Q}$ est égale d'une part à ${\displaystyle \sum _{j=0}^{m}(-1)^{m-j}{\binom {m}{j}}Q(X+j)}$ et d'autre part à ${\displaystyle m!\,c_{m}}$.

• Portail de l’algèbre