Formule du pion

En mathématiques, la formule du pion est une relation entre coefficients binomiaux.

Elle a de nombreuses autres appellations : formule du capitaine, formule du chef, formule (du) comité-président, identité (ou formule) d'absorption, etc.

Énoncé

Soient Modèle:Mvar et Modèle:Mvar deux nombres entiers tels que $1⩽k⩽n$ ; la formule du pion s'écrit :

$k(\genfrac{}{}{0ex}{}{n}{k})=n(\genfrac{}{}{0ex}{}{n-1}{k-1})$.

Explication des appellations

Cette relation est dénommée « formule du pion » du fait de l'analogie entre sa situation dans le triangle de Pascal et le mouvement d'un pion dans le jeu d'échecs. En effet, lorsqu’un pion attaque un pion adverse, il se déplace d’une case en diagonale (par exemple depuis la case située à l’intersection de la ligne Modèle:Mvar – 1 et de la colonne Modèle:Mvar – 1 vers celle située à l’intersection de la ligne Modèle:Mvar et de la colonne Modèle:Mvar).

L'appellation « formule du capitaine » (de même « pour formule du chef » ou « formule (du) comité-président ») vient de la démonstration par dénombrement donnée ci-dessous si l'on représente Modèle:Mvar comme une équipe de Modèle:Mvar joueurs choisis parmi Modèle:Mvar et Modèle:Mvar comme le capitaine de cette équipe.

La formule du pion est appelée « identité d'absorption » dans le livre Concrete Mathematics, de par sa propriété d'absorption d'une variable nuisible dans une somme.

Démonstrations

Démonstration utilisant la formule explicite des coefficients binomiaux

Il suffit d'écrire

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}=\frac{n}{k}(\genfrac{}{}{0ex}{}{n-1}{k-1})$.

Démonstration utilisant la formule du binôme

Modèle:Article détaillé Le polynôme $P=(1+X{)}^n$ se développe en

$P=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})X^k$,

donc

$P^{\prime }=\sum _{k=1}^{n}k(\genfrac{}{}{0ex}{}{n}{k})X^{k-1}$.

Mais on a aussi

$P^{\prime }=n(1+X{)}^{n-1}=n\sum _{k=0}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{k})X^k=\sum _{k=1}^{n}n(\genfrac{}{}{0ex}{}{n-1}{k-1})X^{k-1}$,

d'où la formule par identification des coefficients.

Démonstration combinatoire

Modèle:Article détaillé Soit Modèle:Mvar un ensemble à Modèle:Mvar éléments ; on cherche à déterminer le nombre Modèle:Mvar de couples (Modèle:Mvar, Modèle:Mvar) où Modèle:Mvar est une partie de Modèle:Mvar à Modèle:Mvar éléments et Modèle:Mvar un élément de Modèle:Mvar.

• On peut commencer par choisir une partie Modèle:Mvar de Modèle:Mvar à Modèle:Mvar éléments ($(\genfrac{}{}{0ex}{}{n}{k})$ choix possibles) puis on choisit Modèle:Mvar parmi les Modèle:Mvar éléments de Modèle:Mvar (Modèle:Mvar choix possibles) donc le nombre Modèle:Mvar de choix possibles est égal à

$N=(\genfrac{}{}{0ex}{}{n}{k})k$.

• On peut commencer à choisir Modèle:Mvar parmi les Modèle:Mvar éléments de Modèle:Mvar (Modèle:Mvar choix possibles) puis on choisit Modèle:Mvar – 1 éléments parmi les Modèle:Mvar – 1 éléments de Modèle:Mvar restants ($(\genfrac{}{}{0ex}{}{n-1}{k-1})$ choix possibles), donc le nombre Modèle:Mvar de choix possibles est égal à

$N=n(\genfrac{}{}{0ex}{}{n-1}{k-1})$.

On a donc bien

$N=(\genfrac{}{}{0ex}{}{n}{k})k=n(\genfrac{}{}{0ex}{}{n-1}{k-1})$.

Plus généralement, si on dénombre de deux façons les couples (Modèle:Mvar, Modèle:Mvar) où Modèle:Mvar est une partie de Modèle:Mvar à Modèle:Mvar éléments et Modèle:Mvar partie de Modèle:Mvar à Modèle:Mvar éléments, on obtient la relation

$(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{k}{i})=(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{n-i}{k-i})$

qui redonne la formule du pion pour Modèle:Mvar = 1.

Exemples d'applications

• Écrite sous la forme $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n}{k}(\genfrac{}{}{0ex}{}{n-1}{k-1})$ elle permet un calcul récursif des coefficients binomiaux.
• Cette formule peut être utile pour éliminer un paramètre dans des calculs de sommes, comme par exemple :
  • $\sum _{k=0}^{n}k(\genfrac{}{}{0ex}{}{n}{k})=\sum _{k=1}^{n}n(\genfrac{}{}{0ex}{}{n-1}{k-1})=n\sum _{k=0}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{k})=n{2}^{n-1},$ en effectuant une translation d'indice puis utilisant la formule du binôme de Newton (ou la somme d'une ligne du triangle de Pascal),
  • plus généralement $\sum _{k=0}^{n}k(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}=np$, espérance de la loi binomiale $B(n,p)$,
  • l'itération de la formule du pion $k(k-1)(\genfrac{}{}{0ex}{}{n}{k})=n(n-1)(\genfrac{}{}{0ex}{}{n-2}{k-2})$ qui permet d'obtenir $\sum _{k=0}^n{k}^2(\genfrac{}{}{0ex}{}{n}{k})=\sum _{k=0}^n(k(k-1)+k)(\genfrac{}{}{0ex}{}{n}{k})=\cdots =n(n+1)2^{n-2},$ ainsi que les moments factoriels de la loi binomiale,
  • $\sum _{k=0}^n\frac{(\genfrac{}{}{0ex}{}{n}{k})}{k+1}=\frac{1}{n+1}\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n+1}{k+1})=\frac{2^{n+1}-1}{n+1}$.
• L'écriture de la formule : $k(\genfrac{}{}{0ex}{}{n}{k})=n(\genfrac{}{}{0ex}{}{n-1}{k-1})$ montre, par le lemme de Gauss, que lorsque Modèle:Mvar et Modèle:Mvar sont premiers entre eux, $(\genfrac{}{}{0ex}{}{n}{k})$ est un multiple de Modèle:Mvar. En particulier, lorsque Modèle:Mvar est un nombre premier Modèle:Mvar, les coefficients binomiaux non extrêmes de la ligne Modèle:Mvar du triangle de Pascal sont multiples de Modèle:Mvar. Cette dernière propriété est même caractéristique des nombres premiers (voir Coefficient_binomial, Diviseurs_et_coefficients_binomiaux).

Voir aussi

• Triangle de Pascal
• Formule d'itération de Pascal
• Q-analogue de la formule du pion