title: Formule d'inversion de Pascal
text: # Formule d'inversion de Pascal
  
  La formule d'inversion de Pascal est une formule qui traduit l'involutivité de la transformation binomiale.
  
  ## Énoncé
  
  Soit $(a_{k})_{k\in \mathbb {N} }$ et $(b_{k})_{k\in \mathbb {N} }$ deux suites à valeurs dans un groupe abélien, par exemple (ℝ, +). Pour tout entier naturel $n$, on a
  
  $\forall p\in \{0,\dots ,n\}\quad b_{p}=\sum _{k=0}^{p}{p \choose k}a_{k}$
  
  si et seulement si
  
  $\forall p\in \{0,\dots ,n\}\quad a_{p}=(-1)^{p}\sum _{k=0}^{p}(-1)^{k}{p \choose k}b_{k}$
  
  où les ${p \choose k}$ désignent les coefficients binomiaux.
  
  ## Démonstration
  
  Deux suites $(a_{n})_{n\in \mathbb {N} }$ et $(b_{n})_{n\in \mathbb {N} }$ sont liées par $b_{p}=\sum _{k=0}^{p}{p \choose k}a_{k}$ si et seulement si leurs séries formelles génératrices exponentielles $A$ et $B$ vérifient $B(X)=\mathrm {e} ^{X}A(X)$.
  
      ${\begin{aligned}B(X)&=\sum _{p\in \mathbb {N} }{\frac {X^{p}}{p!}}b_{p}\\&=\sum _{p\in \mathbb {N} }{\frac {X^{p}}{p!}}\sum _{k=0}^{p}{p \choose k}a_{k}\\&=\sum _{p\in \mathbb {N} }X^{p}\sum _{k=0}^{p}{\frac {a_{k}}{k!(p-k)!}}\\&=\sum _{j,k\in \mathbb {N} }X^{j+k}{\frac {a_{k}}{k!j!}}\\&=\sum _{j\in \mathbb {N} }{\frac {X^{j}}{j!}}\sum _{k\in \mathbb {N} }{\frac {X^{k}}{k!}}a_{k}\\&=\mathrm {e} ^{X}A(X).\end{aligned}}$
  
  On a alors $A(-X)=\mathrm {e} ^{X}B(-X)$, c'est-à-dire (d'après cette même équivalence) $(-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é.
  
  ## Applications classiques
  
  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.
  
  ### Nombre de dérangements d'un ensemble fini
  
  Notons $N_{n}$ le nombre de dérangements — c'est-à-dire de permutations sans point fixe — d'un ensemble à n éléments. La formule d'inversion de Pascal donne :
  
      $N_{n}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$.
  
  (Voir les détails sur Wikiversité.)
  
  ### Nombre de surjections d'un ensemble fini vers un autre
  
  Notons $S_{p,n}$ le nombre de surjections d'un ensemble à $p$ éléments sur un ensemble à $n$ éléments. La formule d'inversion de Pascal donne :
  
      $S_{p,n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{p}$.
  
  (Voir les détails sur Wikiversité.)
  
  ## Version polynomiale
  
  Une autre version de cette inversion avec $T^{k}$ au lieu de ${p \choose k}$ :
  
  Soit un polynôme
  
  $Q(T)=\sum _{k=0}^{m}c_{k}T^{k}$
  
  (à coefficients dans un anneau, ou même seulement un groupe abélien), on a
  
  $\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 $Q$ est égale d'une part à $\sum _{j=0}^{m}(-1)^{m-j}{\binom {m}{j}}Q(X+j)$ et d'autre part à $m!\,c_{m}$.
  
  