Formule d'inversion de Pascal

Formule d'inversion de Pascal

Sommaire

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

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.

Voir aussi

Coefficient binomial


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Formule d'inversion de Pascal de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Formule D'inversion De Pascal — Sommaire 1 Enoncé et démonstration 1.1 Enoncé 1.2 Démonstration 2 Applications classiques // …   Wikipédia en Français

  • Formule d'inversion de pascal — Sommaire 1 Enoncé et démonstration 1.1 Enoncé 1.2 Démonstration 2 Applications classiques // …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Coefficient binomial — En mathématiques, les coefficients binomiaux, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de sous ensembles différents à k éléments que l on peut former à partir d un ensemble contenant n… …   Wikipédia en Français

  • Liste d'équations et formules — Ceci est une Liste des équations et formules par ordre alphabétique. Cette liste contient les équations, les formules, les relations et autres identités, égalités ou inégalités. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X …   Wikipédia en Français

  • Liste Des Théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

  • Liste des theoremes — Liste des théorèmes Liste des théorèmes par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le… …   Wikipédia en Français

  • Liste des théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

  • que — 1. que [ kə ] conj. • Xe; lat. médiév. que, forme affaiblie de qui, simplification de quia, employé en bas lat. au sens de quod « le fait que; que » 1 ♦ Introd. une complétive (à l indic. ou au subj. suivant le v. de la principale, ou la nuance à …   Encyclopédie Universelle

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”