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é[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Démonstration utilisant la formule explicite des coefficients binomiaux[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : Formule du binôme de Newton.

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[modifier | modifier le code]

Article détaillé : Preuve par double dénombrement.

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[modifier | modifier le code]

É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[modifier | modifier le code]

Notes et références[modifier | modifier le code]

↑ 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 et Oren Patashnik (trad. de l'anglais par Alain Denise), Mathématiques concrètes : fondations pour l'informatique [« Concrete Mathematics »], International Thomson publishing France, 26 novembre 1997, 736 p. (ISBN 9782841809813), p. 168.
↑ « Démonstration : Somme des k(k parmi n) », sur Devmath (consulté le 22 novembre 2022)

[1] René Adad, « Principales propriétés des coefficients binomiaux », sur Math-OS, 18 octobre 2017 (consulté le 22 novembre 2022), p. 7

[2] Robin-Lee Graham, Donald Ervin Knuth et Oren Patashnik (trad. de l'anglais par Alain Denise), Mathématiques concrètes : fondations pour l'informatique [« Concrete Mathematics »], International Thomson publishing France, 26 novembre 1997, 736 p. (ISBN 9782841809813), p. 168.

[3] « Démonstration : Somme des k(k parmi n) », sur Devmath (consulté le 22 novembre 2022)

[1]

[2]

[3]