Formule d'inversion de Pascal

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Enoncé et démonstration

[modifier] Enoncé

Soit (a_k)_{1 \le k \le n} et (b_k)_{1 \le k \le n} deux familles d'éléments de \mathbb R\,.


si \forall p \in \{1,....n\}, b_p = \sum_{k=1}^p {p \choose k} a_k

alors \forall p \in \{1,....n\}, a_p = (-1)^p \sum_{k=1}^p (-1)^k {p \choose k} b_k


On peut étendre cette formule en remplaçant \mathbb R par un anneau commutatif quelconque.

[modifier] Démonstration

On démontre la formule en deux temps.

On montre d'abord le lemme : \forall k \in \{0,1,...,p-1\}, \sum_{q=k}^p (-1)^q {p \choose q}{q \choose k} = 0


Démonstration du lemme

On doit d'abord montrer que {p \choose q}{q \choose k} = {p \choose k}{p-k \choose q-k}

\begin{align} {p \choose q}{q \choose k} & = \frac{p!}{q!(p-q)!} * \frac{q!}{k!(q-k!)} \\ & = \frac{p!}{k!(p-k)!} * \frac{(p-k)!}{(p-q)!(q-k)!} \\ &= {p \choose k}{p-k \choose q-k} \\ \end{align}

on reprend maintenant l'expression de départ :

\forall k \in \{0,1,...,p-1\}, \begin{align} \sum_{q=k}^p (-1)^q {p \choose q}{q \choose k} & = \sum_{q=k}^p (-1)^q {p \choose k}{p-k \choose q-k} \\ & = {p \choose k} \sum_{q=k}^p (-1)^q {p-k \choose q-k} \\ & = {p \choose k} \sum_{i=0}^{p-k} (-1)^{i+k} {p-k \choose i} \\ \end{align}


cette quantité vaut bien 0 d'après la formule du binôme de Newton.

Ensuite on démarre avec le membre de droite de la formule, on injecte l'hypothèse, on permute des sommations avant de conclure grâce au lemme.


Démonstration de la formule

\begin{align} (-1)^p \sum_{k=1}^p (-1)^k {p \choose k} b_k = (-1)^p \sum_{k=1}^p (-1)^k {p \choose k} \sum_{i=1}^k {k \choose i} a_i \\ = (-1)^p \sum_{k=1}^p \sum_{i=1}^k (-1)^k {p \choose k} {k \choose i} a_i \\ = (-1)^p \sum_{1 \le i \le k \le p} (-1)^k {p \choose k} {k \choose i} a_i \\ = (-1)^p \sum_{i=1}^p a_i \sum_{k=i}^p (-1)^k {p \choose k} {k \choose i} \\ \end{align}

D'après le lemme, tous les termes s'annulent sauf pour i=p\,, il reste donc (-1)^p * a_p * (-1)^p * {p \choose p} {p \choose p}

Et on retrouve bien notre ap.

[modifier] 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.