Formule D'inversion De Pascal

Formule d'inversion de Pascal

Enoncé et démonstration

Enoncé

Soit $(a_k)_{1 \le k \le n}$ et $(b_k)_{1 \le k \le n}$ deux familles de réels.

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.

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 a_p.

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.

Ce document provient de « Formule d%27inversion de Pascal ».