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é d'absorption, etc.

Énoncé

Soient $n$ et $k$ deux nombres entiers tels que $1\leqslant k\leqslant n$ ; la formule du pion s'écrit :

k{n \choose k}=n{n-1 \choose {k-1}}

Explication des appellations

Cette relation est dénommée « formule du pion » [1] 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 $n$ – 1 et de la colonne $k$ – 1 vers celle située à l’intersection de la ligne $n$ et de la colonne $k$ ).

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 $A$ comme une équipe de $k$ joueurs choisis parmi $n$ et $a$ comme le capitaine de cette équipe.

La formule du pion est appelée « identité d'absorption » dans le livre Concrete Mathematics[2], 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

{n \choose k}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}={\frac {n}{k}}{n-1 \choose k-1}

Démonstration utilisant la formule du binôme

Le polynôme $P=(1+X)^{n}$ se développe en

P=\sum _{k=0}^{n}{n \choose k}X^{k}

donc

P'=\sum _{k=1}^{n}k{n \choose k}X^{k-1}

Mais on a aussi

P'=n(1+X)^{n-1}=n\sum _{k=0}^{n-1}{{n-1} \choose k}X^{k}=\sum _{k=1}^{n}n{{n-1} \choose {k-1}}X^{k-1}

d'où la formule par identification des coefficients.

Démonstration combinatoire

Soit $E$ un ensemble à $n$ éléments ; on cherche à déterminer le nombre $N$ de couples ( $A$ , $a$ ) où $A$ est une partie de $E$ à $k$ éléments et $a$ un élément de $A$ .

On peut commencer par choisir une partie $A$ de $E$ à $k$ éléments ( $\textstyle {n \choose k}$ choix possibles) puis on choisit $a$ parmi les $k$ éléments de $A$ ( $k$ choix possibles) donc le nombre $N$ de choix possibles est égal à

N={n \choose k}k

On peut commencer à choisir $a$ parmi les $n$ éléments de $E$ ( $n$ choix possibles) puis on choisit $k$ – 1 éléments parmi les $n$ – 1 éléments de $E$ restants ( $\textstyle {n-1 \choose k-1}$ choix possibles), donc le nombre $N$ de choix possibles est égal à

N=n{n-1 \choose k-1}

On a donc bien

N={n \choose k}k=n{n-1 \choose k-1}

Plus généralement, si on dénombre de deux façons les couples ( $A$ , $B$ ) où $A$ est une partie de $E$ à $k$ éléments et $B$ partie de $A$ à $i$ éléments, on obtient la relation

{n \choose k}{k \choose i}={n \choose i}{n-i \choose k-i}

qui redonne la formule du pion pour $i$ = 1.

Exemples d'applications

Écrite sous la forme ${n \choose k}={\frac {n}{k}}{n-1 \choose 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[3], comme par exemple :
- $\sum _{k=0}^{n}{k{n \choose k}}=\sum _{k=1}^{n}{n{n-1 \choose k-1}}=n\sum _{k=0}^{n-1}{n-1 \choose k}=n2^{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{n \choose 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){n \choose k}=n(n-1){n-2 \choose {k-2}}$ qui permet d'obtenir $\sum _{k=0}^{n}{k^{2}{n \choose k}}=\sum _{k=0}^{n}{(k(k-1)+k){n \choose k}}=\cdots =n(n+1)2^{n-2},$ ainsi que les moments factoriels de la loi binomiale,
- $\sum _{k=0}^{n}{\frac {\binom {n}{k}}{k+1}}={\frac {1}{n+1}}\sum _{k=0}^{n}{\binom {n+1}{k+1}}={\frac {2^{n+1}-1}{n+1}}$ .
L'écriture de la formule : $k{n \choose k}=n{n-1 \choose {k-1}}$ montre, par le lemme de Gauss, que lorsque $n$ et $k$ sont premiers entre eux, ${n \choose k}$ est un multiple de $n$ . En particulier, lorsque $n$ est un nombre premier $p$ , les coefficients binomiaux non extrêmes de la ligne $p$ du triangle de Pascal sont multiples de $p$ . Cette dernière propriété est même caractéristique des nombres premiers (voir Coefficient_binomial, Diviseurs_et_coefficients_binomiaux).

Voir aussi

Notes et références

René Adad, « Principales propriétés des coefficients binomiaux », sur Math-OS, 18 octobre 2017 (consulté le 22 novembre 2022), p. 7
Robin-Lee Graham, Donald Ervin Knuth, Oren Patashnik, Mathématiques concrètes - Fondations pour l'informatique, Thomson, 1998, p. 168
« Démonstration : Somme des k(k parmi n) », sur Devmath (consulté le 22 novembre 2022)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.