Principales propriétés des coefficients binomiaux

Cet article présente l’essentiel de ce qu’il faut savoir au sujet des coefficients binomiaux.

Ces entiers, qui doivent leur nom à la formule du binôme (cf. section 6 plus bas) interviennent dans une foule de problèmes mathématiques, notamment en combinatoire et en arithmétique.

Le sujet étant vaste, nous nous limiterons à quelques unes des propriétés les plus simples et les plus fréquemment rencontrées.

1 – Préambule et notations

Pour tout entier naturel $n,$ on désigne par $\mathbb{N}_{n}$ l’ensemble des entiers $k$ vérifiant $1\leqslant k\leqslant n$ .

Noter que : $\mathbb{N}_{0}=\emptyset.$

Définition

Un ensemble E est dit fini lorsqu’il existe un entier naturel $n$ et une bijection de $\mathbb{N}_{n}$ vers $E$ . On peut montrer l’unicité d’un tel $n$ : c’est le cardinal de $E$ , noté $\text{card}\left(E\right)$ .

Intuitivement, $\text{card}\left(E\right)$ indique le nombre d’éléments de $E$ .

On peut démontrer (nous l’admettrons ici) la :

Proposition

Si $E$ est un ensemble fini de cardinal $n$ , alors toute partie $A$ de $E$ est aussi finie et $\text{card}\left(A\right)\leqslant n$ , avec égalité si, et seulement si, $A=E$ .

On sait que la composée de deux bijections est une bijection. Il en résulte aussitôt que :

Proposition

Si $E$ et $F$ sont deux ensembles, si $E$ est fini et s’il existe une bijection de $E$ vers $F$ , alors $F$ est fini et $\text{card}\left(E\right)=\text{card}\left(F\right)$ .

On note classiquement $\mathcal{P}\left(E\right)$ l’ensemble des parties d’un ensemble $E$ .
Si $E$ est fini et $k\in\mathbb{N}$ , on note $\mathcal{P}_{k}\left(E\right)$ la partie de $\mathcal{P}\left(E\right)$ constituée des parties de $E$ de cardinal $k$ .

Il est donc clair que :

$\mathcal{P}_0(E)=\{\emptyset\}$
$\mathcal{P}_{\text{card}\left(E\right)}\left(E\right)=\left\{ E\right\}$
si $k>\text{card}\left(E\right)$ , alors $\mathcal{P}_{k}\left(E\right)=\emptyset$

Nous aurons enfin à utiliser le :

Principe Additif

Si $E,F$ sont deux ensembles finis et disjoints, alors $E\cup F$ est fini et :

$\text{card}\left(E\cup F\right)=\text{card}\left(E\right)+\text{card}\left(F\right)$

Plus généralement, si $E_{1},\cdots,E_{p}$ sont des ensembles finis deux à deux disjoints, alors :

$\text{card}\left(\bigcup_{i=1}^{p}E_{i}\right)=\sum_{i=1}^{p}\text{card}\left(E_{i}\right)$

2 – Point de vue combinatoire sur les coefficients binomiaux

Définition

Soient $n$ et $k$ deux entiers naturels tels que $0\leqslant k\leqslant n$ . On note :

$\boxed{\binom{n}{k}=\text{card}\left(\mathcal{P}_{k}\left(\mathbb{N}_{n}\right)\right)}$

Le membre de gauche de cette égalité se lit « k parmi n ».

En d’autres termes, $\displaystyle{\binom{n}{k}}$ désigne le nombre de parties de $\mathbb{N}_{n}$ qui sont de cardinal $k$ .

Il est facile de voir que si $E$ est de cardinal $n$ , alors les ensembles $\mathcal{P}_{k}\left(E\right)$ et $\mathcal{P}_{k}\left(\mathbb{N}_{n}\right)$ sont équipotents (c’est-à-dire qu’il existe une bijection de l’un vers l’autre); il en résulte que :

$\displaystyle{\binom{n}{k}}$ désigne le nombre de parties de cardinal $k$ dans un ensemble de cardinal $n$

Exemple

Calculons $\displaystyle{\binom{4}{2}}$ . Pour cela, considérons un ensemble à quatre éléments, que nous noterons $E=\left\{ a,b,c,d\right\}$ et énumérons ses parties de cardinal 2 :

$\left\{a,b\right\} ,\;\left\{ a,c\right\} ,\:\left\{a,d\right\} ,\:\left\{b,c\right\} ,\:\left\{b,d\right\} ,\:\left\{c,d\right\}$

Manifestement, il en existe six. Par conséquent : $\displaystyle{\binom{4}{2}=6}$ .

Cependant, cette méthode d’énumération exhaustive atteint très vite ses limites ! Si l’on voulait faire de même pour calculer $\displaystyle{\binom{20}{10}}$ , il faudrait dresser la liste complète des parties de cardinal 10 dans un ensemble de cardinal 20, ce qui est difficilement imaginable, quand on sait (cf. formule de Fermat, à la section 5) que :

$\binom{20}{10}=184\thinspace756$

Et ne parlons pas de :

$\binom{60}{30}=118\thinspace264\thinspace581\thinspace564\thinspace861\thinspace424$

Même si nous étions capables de passer en revue les parties de cardinal 30 d’un ensemble de cardinal 60, à raison d’une par seconde, sans jamais faire de pause, il ne nous faudrait pas moins de 37 milliards d’années pour en venir à bout !!

Une formule pour le calcul direct de $\displaystyle{\binom{n}{k}}$ s’avère donc nécessaire. Nous l’obtiendrons à la section 5.

3 – Formule de symétrie

Choisir $k$ éléments parmi $n$ , revient à en sélectionner $n-k$ éléments qui ne seront pas choisis.

Ces $n-k$ éléments, qui sont mis de côté, sont donc – en un sens – « choisis » eux aussi !

Il n’est donc pas surprenant qu’on ait :

Proposition

Pour tout $n\in\mathbb{N}$ et pour tout $k\in\left\{0,\cdots,n\right\}$ :

$\boxed{\binom{n}{k}=\binom{n}{n-k}}$

C’est la formule de symétrie des coefficients binomiaux.

En voici une justification rigoureuse.

Preuve (cliquer pour déplier / replier)

Soit $E$ un ensemble de cardinal $n$ . Pour chaque partie $A$ de $E$ , notons $\overline{A}$ le complémentaire de $A$ dans $E$ et considérons les applications :

$\varphi:\mathcal{P}_{k}\left(E\right)\rightarrow\mathcal{P}_{n-k}\left(E\right),\thinspace A\mapsto\overline{A}$

$\psi:\mathcal{P}_{n-k}\left(E\right)\rightarrow\mathcal{P}_{k}\left(E\right),\thinspace A\mapsto\overline{A}$

Comme le complémentaire du complémentaire d’une partie $A$ n’est autre que $A$ , il est clair que :

$\psi\circ\varphi=id_{\mathcal{P}_{k}\left(E\right)}\qquad\text{et}\qquad\varphi\circ\psi=id_{\mathcal{P}_{n-k}\left(E\right)}$

Il s’ensuit que $\varphi$ et $\psi$ sont des bijections (et que chacune est la réciproque de l’autre).

En particulier, $\mathcal{P}_{k}\left(E\right)$ et $\mathcal{P}_{n-k}\left(E\right)$ sont équipotents, d’où la formule.

4 – Formule de Pascal

Soient $n,k$ deux entiers naturels tels que $n\geqslant 1$ et $0\leqslant k\leqslant n-1$ .

Considérons un ensemble $E$ de cardinal $n+1$ ainsi qu’un élément particulier de $E$ , que nous notons $x$ .

Les parties de $E$ de cardinal $k+1$ , qui sont au nombre de $\displaystyle{\binom{n+1}{k+1}}$ , peuvent être classées en deux catégories :

celles qui ne contiennent pas $x$ ,
celles qui contiennent $x$ .

Les premières sont les parties de cardinal $k+1$ de $E-\left\{ x\right\}$ . Il en existe $\displaystyle{\binom{n}{k+1}}$ .

Les autres s’obtiennent en ajoutant $x$ à une partie de cardinal $k$ de $E-\left\{ x\right\}$ : il en existe donc autant que de parties de cardinal $k$ de $E-\left\{ x\right\}$ , c’est-à-dire $\displaystyle{\binom{n}{k}}$ .

Ce raisonnement prouve, via le principe additif, que :

Proposition

Pour tout $n\geqslant1$ et pour tout $k\in\{0,\cdots,n-1\}$ :

$\boxed{\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}}$

Cette relation (appelée formule de Pascal) permet de construire un tableau, appelé « triangle de Pascal », qui renferme les valeurs des coefficients binomiaux. La valeur de $\displaystyle{\binom{n}{k}}$ est placée à l’intersection de la ligne n et de la colonne k.

➣ Comme $\displaystyle{\binom{n}{0}=\binom{n}{n}=1}$ pour tout $n\in\mathbb{N}$ , on place au préalable des ‘1’ sur la colonne 0 et sur la diagonale.

➢ Ensuite, on utilise la formule encadrée pour « garnir » la table, ligne par ligne.

L’animation suivante montre le remplissage du triangle de Pascal, jusqu’à la ligne 8 :

5 – Formule de Fermat

Nous sommes maintenant en mesure d’établir une formule adaptée au calcul direct de $\displaystyle{\binom{n}{k}}$ .

Il s’agit de la « formule de Fermat » :

Proposition

Pour tout $n\in\mathbb{N}$ et pour tout $k\in\left\{0,\cdots,n\right\}$ :

$\boxed{\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}}$

Si la notion de factorielle vous est peu familière, je vous suggère la lecture des articles suivants :

Qu’est-ce qu’une factorielle ? Partie 1 (article de vulgarisation)
Qu’est-ce qu’une factorielle ? Partie 2 – (article de niveau supérieur)

La formule encadrée se prouve par récurrence sur $n$ . Pour $n=0$ , il est clair que :

$\binom{0}{0}=1=\frac{0!}{0!\:\left(0-0\right)!}$

Supposons ensuite que, pour un certain $n\in\mathbb{N}$ , on ait pour tout $k\in\left{ 0,\cdots,n\right}$ :

$\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}$

Alors, pour tout $k\in\mathbb{N}_{n}$ :

$\begin{eqnarray*}\binom{n+1}{k} & = & \binom{n}{k}+\binom{n}{k-1}\\& = & \frac{n!}{k!\left(n-k\right)!}+\frac{n!}{\left(k-1\right)!\left(n-k+1\right)!}\\& = & \frac{n!}{\left(k-1\right)!\left(n-k\right)!}\left[\frac{1}{k}+\frac{1}{n-k+1}\right]\\& = & \frac{n!}{\left(k-1\right)!\left(n-k\right)!}\:\frac{n+1}{k\left(n-k+1\right)}\end{eqnarray*}$

c’est-à-dire, comme souhaité :

$\binom{n+1}{k}=\frac{\left(n+1\right)!}{k!\left(n+1-k\right)!}$

Cette égalité est encore vraie pour $k=0$ et pour $k=n+1$ , et la formule de Fermat est donc établie.

Pour les calculs numériques, il est pratique d’utiliser ceci :

Version simplifiée de la formule de Fermat

Pour tout $n\in\mathbb{N}^{\star}$ et pour tout $k\in\mathbb{N}_{n}$ :

$\boxed{\binom{n}{k}=\frac{n\left(n-1\right)\cdots\left(n-k+1\right)}{k!}}$

On retiendra que le numérateur et le dénominateur de cette fraction sont chacun le produit de $k$ entiers consécutifs. Ceci peut aider à mémoriser la formule correcte.

Exemples

Exemple 1

De combien de façons peut-on choisir 6 cartes à jouer dans un paquet de 16 cartes ? Réponse :

$\binom{16}{6}=\frac{16\times15\times14\times13\times12\times11}{6\times5\times4\times3\times2\times1}=4\times14\times13\times11=8\thinspace008$

Exemple 2

Une grille de loto comporte 49 numéros.

De combien de façons le joueur peut-il en choisir 6 ?

Réponse :

$\binom{49}{6}=\frac{49\times48\times47\times46\times45\times44}{6\times5\times4\times3\times2\times1}=49\times47\times46\times3\times44=13\thinspace983\thinspace816$

Remarquons, pour conclure cette section, que la formule de Fermat exprime une propriété arithmétique intéressante en soi, à savoir qu’étant donné un entier $k\geqslant2$ , tout produit de $k$ entiers consécutifs est multiple de la factorielle de $k$ . En effet, étant donné $N\in\mathbb{N}$ :

$\left(N+1\right)\cdots\left(N+k\right)=k!\:\binom{N+k}{k}$

Pour plus de détails à ce sujet, je vous invite à lire l’article (n+1)(n+2)…(n+k) est multiple de k!

6 – Formule du binôme de Newton

Au collège, on apprend l’identité remarquable $\left(a+b\right)^{2}=a^2+2ab+b^2$ .

La formule du binôme en donne une version généralisée, avec un exposant quelconque :

Proposition

Pour tout $(a,b)\in\mathbb{C}^2$ et pour tout $n\in\mathbb{N}$ :

$\boxed{\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}}$

Exemple

Si $n=6$ et $k=2$ , le terme $a^{2}b^{4}$ sera obtenu en choisissant deux facteurs parmi les six.

Dans ces deux-là, on sélectionnera le terme $a$ , tandis que dans les quatre autres, on sélectionnera le terme $b$ .

Enumérons les possibilités (les deux facteurs sélectionnés sont représentés en rouge) :

(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)

… etc …

(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)

Bref : il existe $\display{\binom{6}{2}}=15$ possibilités.

Ainsi, dans l’expression développée de $\left(a+b\right)^{6}$ , le terme $a^{2}b^{6}$ est affecté d’un coefficient $15$ .

Commençons par en donner une preuve combinatoire.

En développant « brutalement » l’expression $\left(a+b\right)^{n}$ , on obtient $2^{n}$ termes, qui sont tous de la forme $a^{k}b^{n-k}$ pour un certain $k\in\left\{ 0,\cdots,n\right\}$ .

Pour une valeur donnée de $k$ , combien de fois le terme $a^{k}b^{n-k}$ apparaît-il ? C’est simple : il suffit de voir que, pour obtenir ce terme, on doit sélectionner la lettre $a$ dans $k$ facteurs et la lettre $b$ dans les $n-k$ autres, ce qui peut se faire de $\displaystyle{\binom{n}{k}}$ façons.

Pour chaque $k\in\left\{ 0,\cdots,n\right\}$ , le terme $a^{k}b^{n-k}$ apparaît donc $\displaystyle{\binom{n}{k}}$ fois dans le développement de $\left(a+b\right)^{n}$ . La formule du binôme en résulte.

On peut aussi envisager une …

Preuve par récurrence (cliquer pour déplier / replier)

Etant donnés $a,b\in\mathbb{C}$ , on considère l’assertion :

$\left(\mathcal{A}_{n}\right)\::\qquad\qquad\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$

$\left(\mathcal{A}_{0}\right)$ est vraie, puisque :

$\left(a+b\right)^{0}=1=\binom{0}{0}\,a^{0}\,b^{0-0}$

Supposons $\left(\mathcal{A}{n}\right)$ vraie pour un certain $n\in\mathbb{N}$ . Alors :

$\begin{eqnarray*}\left(a+b\right)^{n+1} & = &\left(a+b\right)\left(a+b\right)^{n}\\& = & \left(a+b\right)\sum_{k=0}^{n}\,\binom{n}{k}a^{k}b^{n-k}\\& = & \sum_{k=0}^{n}\,\binom{n}{k}a^{k+1}b^{n-k}\,+\,\sum_{k=0}^{n}\,\binom{n}{k}a^{k}b^{n+1-k}\end{eqnarray*}$

Si l’on effectue dans la première somme le changement d’indice $j=k+1$ , il vient :

(1) $\begin{eqnarray*}\left(a+b\right)^{n+1} & = & \sum_{j=1}^{n+1}\,\binom{n}{j-1}a^{j}b^{n+1-j}+\sum_{j=0}^{n}\,\binom{n}{j}a^{j}b^{n+1-j}\\& = & a^{n+1}+b^{n+1}+\sum_{j=1}^{n}\,\left[\binom{n}{j-1}+\binom{n}{j}\right]a^{j}b^{n+1-j}\\& = & a^{n+1}+b^{n+1}+\sum_{j=1}^{n}\binom{n+1}{j}a^{j}b^{n+1-j}\\& = & \sum_{j=0}^{n+1}\,\binom{n+1}{j}a^{j}b^{n+1-j} \end{eqnarray*}$

L’avant-dernière égalité résulte de la formule de Pascal. La dernière s’obtient en ré-insérant les termes $a^{n+1}$ et $b^{n+1}$ dans le $\Sigma$ (ils correspondent respectivement à $j=n+1$ et à $j=0$ ).

L’assertion $\left(\mathcal{A}_{n+1}\right)$ est donc établie, ce qui achève la démonstration.

7 – Formule du pion

Proposition

L’égalité :

$\boxed{k\binom{n}{k}=n\binom{n-1}{k-1}}$

est valable pour tout couple $\left(n,k\right)$ d’entiers naturels tels que $1\leqslant k\leqslant n$ .

On l’appelle parfois « formule du pion ».

Cette appellation est sans doute due à une vague analogie avec le jeu d’échec : lorsqu’un pion attaque un pion adverse, il se déplace d’une case en diagonale (disons depuis la case située à l’intersection de la ligne $n$ et de la colonne $k$ vers celle située à l’intersection de la ligne $n-1$ et de la colonne $k-1$ ), comme l’indique le schéma ci-dessous :

Cette formule peut être établie de deux manières : par un calcul ou bien par un raisonnement combinatoire.

Preuve 1 – par calcul (cliquer pour déplier / replier)

Avec la formule de Fermat, on voit facilement que :

$\begin{eqnarray*}k\binom{n}{k} & = & k\:\frac{n!}{k!\left(n-k\right)}\\& = & \frac{n\left(n-1\right)!}{\left(k-1\right)!\left[\left(n-1\right)-\left(k-1\right)\right]!}\\& = & n\binom{n-1}{k-1}\end{eqnarray*}$

Mais le point de vue combinatoire est clairement plus instructif …

Preuve 2 – combinatoire (cliquer pour déplier / replier)

Etant donné un ensemble $E$ de cardinal $n$ et un entier $k$ tel que $1\leqslant k\leqslant n$ , on va dénombrer les couples $\left(X,a\right)$ tels que :

$X\in\mathcal{P}_{k}\left(E\right)\qquad\text{et}\qquad a\in X$

Pour cela, on peut choisir d’abord $X$ de $\displaystyle{\binom{n}{k}}$ façons, puis choisir $a\in X$ de $k$ façons : au total, on trouve $\displaystyle{k\binom{n}{k}}$ couples.

Une autre méthode consiste à choisir d’abord $a\in E$ de $n$ façons, puis à « l’entourer » de $k-1$ éléments choisis dans $E-\left\{a\right\}$ , et ce de $\displaystyle{\binom{n-1}{k-1}}$ façons : au total, on trouve $\displaystyle{n\binom{n-1}{k-1}}$ couples.

La formule du pion en résulte.

Vous en trouverez un exemple d’utilisation dans la vidéo Calcul de sommes – 01.

L’illustration ci-dessous permet de visualiser les deux manières de compter :

8 – Formule de Vandermonde

Considérons un ensemble $E$ de cardinal $2n$ . Le nombre de parties de $E$ qui sont de cardinal $n$ est, par définition $\displaystyle{q_{n}=\binom{2n}{n}}$ . Mais on peut raisonner autrement.

On commence par fixer deux parties complémentaires et de même cardinal $n$ (autrement dit : on place une « cloison » dans $E$ ). Se donner une partie de $E$ de cardinal $n$ revient alors à choisir, pour un certain $k\in\left\{ 0,\cdots,n\right\}$ , $k$ éléments d’un côté de la cloison et $n-k$ éléments de l’autre. La figure ci-dessous montre l’une des $\displaystyle{\binom{56}{12}}$ manières de choisir 12 objets parmi 56 :

Pour $k$ donné, le nombre de ces double-choix est $\displaystyle{\binom{n}{k}\binom{n}{n-k}}$ , c’est-à-dire $\displaystyle{\binom{n}{k}^{2}}$ .

Ces possibilités s’excluent mutuellement, ce qui autorise l’usage du principe additif mentionné à la section 1. En ajoutant, il vient :

$q_{n}=\sum_{k=0}^{n}\binom{n}{k}^{2}$

Par conséquent :

$\forall n\in\mathbb{N},\thinspace\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}$

On peut aisément généraliser : pour dénombrer les parties d’un ensemble $F$ de cardinal $a+b$ qui sont de cardinal $n$ (avec $0\leqslant n\leqslant a+b$ ). On cloisonne $F$ en deux parties de cardinaux respectifs $a$ et $b$ puis, en raisonnant comme ci-dessus, on parvient la « formule de Vandermonde » :

$\boxed{\forall\left(a,b\right)\in\mathbb{N}^{2},\:\forall n\in\left{ 0,\cdots,a+b\right} ,\thinspace\sum_{k=\max\left{ 0,n-b\right} }^{\min\left{ a,n\right} }\binom{a}{k}\binom{b}{n-k}=\binom{a+b}{n}}$

Si l’on convient que $\displaystyle{\binom{j}{i}=0}$ dès que $i<0$ ou $i>j$ , cette formule s’écrit plus simplement :

Proposition

Pour tout $\left(a,b\right)\in\mathbb{N}^{2}$ et pour tout $n\in\left\{ 0,\cdots,a+b\right\}$ :

$\boxed{\sum_{k=0}^{n}\binom{a}{k}\binom{b}{n-k}=\binom{a+b}{n}}$

En voici une illustration « concrète ». Etant donné un jeu de 32 cartes, on peut compter le nombre de « mains » (une main est un ensemble de 5 cartes extraites du jeu) : il en existe évidemment $\displaystyle{\binom{32}{5}}$ . Si l’on note $N_{k}$ le nombre de mains comportant exactement $k$ rois (pour $0\leqslant k\leqslant4$ ), on voit que :

$N_{0}=\binom{28}{5}\qquad N_{1}=\binom{4}{1}\binom{28}{4}\qquad N_{2}=\binom{4}{2}\binom{28}{3}$

$N_{3}=\binom{4}{3}\binom{28}{2}\qquad N_{4}=\binom{28}{1}$

Par exemple, $N_{2}$ se calcule en considérant que, pour former une main comportant exactement deux rois, il faut choisir deux cartes parmi les quatre rois ainsi que trois cartes parmi les 28 qui restent (celles qui ne sont pas des rois). En notant $\mathcal{M}$ l’ensemble des mains et $\mathcal{R}_{k}$ celui des mains comportant exactement $k$ rois, il est alors clair que :

$\mathcal{R}_{0}\cup\mathcal{R}_{1}\cup\mathcal{R}_{2}\cup\mathcal{R}_{3}\cup\mathcal{R}_{4}=\mathcal{M}\qquad\text{(union disjointe)}$

d’où, en passant aux cardinaux :

$N_{0}+N_{1}+N_{2}+N_{3}+N_{4}=\binom{32}{5}$

ce qui correspond à la formule de Vandermonde pour $a=4$ , $b=28$ et $n=5$ .

9 – Somme d’une colonne dans le triangle de Pascal

Reprenons le triangle de Pascal et examinons ce qui se passe lorsqu’on ajoute les termes d’une colonne, depuis le terme diagonal (qui vaut 1) jusqu’à une certaine profondeur.

Après quelques essais, on conjecture qu’une telle somme est égale au coefficient binomial situé « en-dessous, à droite » de la colonne considérée. Plus formellement :

Proposition

Pour tout $p\in\mathbb{N}$ et pour tout $n\geqslant p$ :

$\boxed{\sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}}$

Cette relation est prouvable grâce à une sommation télescopique (pour savoir ce qu’est une “sommation télescopique”, voir l’article : Manipulation de sommes à l’aide du symbole ∑)

$\begin{eqnarray*}\sum_{k=p}^{n}\binom{k}{p} & = & 1+\sum_{k=p+1}^{n}\binom{k}{p}\\\\& = & 1+\sum_{k=p+1}^{n}\left[\binom{k+1}{p+1}-\binom{k}{p+1}\right]\\\\& = & 1+\binom{n+1}{p+1}-\binom{p+1}{p+1}\\\\& = & \binom{n+1}{p+1}\end{eqnarray*}$

Là encore, il est intéressant d’interpréter le résultat de manière combinatoire.

Détail de la preuve combinatoire (cliquer pour déplier / replier)

Notons $S_{q,m}$ l’ensemble des applications strictement croissantes de $\mathbb{N}_{q}$ vers $\mathbb{N}_{m}$ , pour $1\leqslant q\leqslant m$ . Une telle application est parfaitement déterminée par la donnée d’une partie de $\mathbb{N}_{m}$ de cardinal $q$ : en effet, connaissant les éléments atteints, le plus petit d’entre-eux sera l’image de 1, celui immédiatement supérieur sera l’image de 2, etc … Il s’ensuit que :

$\text{card}\left(S_{q,m}\right)=\binom{m}{q}$

Maintenant, changeons de point de vue… Pour $f\in S_{q,m}$ , le maximum de $f$ – c’est-à-dire le plus grand des nombres $f\left(1\right),\cdots,f\left(q\right)$ – est un entier $M$ compris (au sens large) entre $q$ et $m$ . Etant donné un tel entier $M$ , il existe $\displaystyle{\binom{M-1}{q-1}}$ éléments de $S_{q,m}$ dont le maximum est M. En effet, se donner un application strictement croissante de $\mathbb{N}_{q}$ vers $\mathbb{N}_{m}$ ayant $M$ pour maximum, équivaut à se donner une application strictement croissante de $\mathbb{N}_{q-1}$ vers $\mathbb{N}_{M-1}$ .En appliquant le principe additif, on voit ainsi que :

$\text{card}\left(S_{q,m}\right)=\sum_{M=q}^{m}\binom{M-1}{q-1}$

d’où l’égalité :

$\sum_{M=q}^{m}\binom{M-1}{q-1}=\binom{m}{q}$

Pour retrouver la formule encadrée plus haut, il suffit de remplacer $\left(q,m\right)$ par $\left(p+1,n+1\right)$ et d’effectuer le changement d’indice défini par $k=M-1$ .

10 – Coefficients binomiaux et nombres de Fibonacci

Reprenons le triangle de Pascal et ajoutons cette fois les termes d’une diagonale ascendante, comme indiqué sur la figure ci-dessous :

On voit apparaître une suite, qui commence par : 1, 1, 2, 3, 5, 8, 13, 21, 55, 89, 144, …

Vous aurez probablement reconnu les premiers termes de la célèbre suite de Fibonacci. Rappelons que cette suite est définie par :

$F_{0}=0\qquad F_{1}=1\qquad\forall n\in\mathbb{N}^{\star},\thinspace F_{n+1}=F_{n}+F_{n-1}$

Cette observation nous amène formuler la :

Proposition

Pour tout $n\in\mathbb{N}$ :

$\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}=F_{n+1}$

Preuve par récurrence (cliquer pour déplier / replier)

L’égalité se vérifie sans peine pour $n\in\left\{ 0,1\right\}$ . Supposons-la vraie pour aux rangs $n-1$ et $n$ , pour un certain entier $n\geqslant1$ et montrons qu’alors :

$\sum_{k=0}^{\left\lfloor \frac{n+1}{2}\right\rfloor }\binom{n+1-k}{k}=F_{n+2}$

Pour cela, distinguons deux cas, selon la parité de $n+1$ .

➣ Si $n+1$ est pair, on voit en posant $n+1=2p+2$ et en invoquant pour commencer la formule de Pascal, que :

$\begin{eqnarray*}\sum_{k=0}^{p+1}\binom{2p+2-k}{k} & = & \binom{2p+2}{0}+\sum_{k=1}^{p}\left[\binom{2p+1-k}{k}+\binom{2p+1-k}{k-1}\right]+\binom{p+1}{p+1}\\\\& = & \left[1+\sum_{k=1}^{p}\binom{2p+1-k}{k}\right]+\left[1+\sum_{j=0}^{p-1}\binom{2p-j}{j}\right]\end{eqnarray*}$

On a séparé le $\Sigma$ de l’avant-dernière ligne en deux, puis posé $j=k-1$ dans le second morceau. Ainsi :

$\begin{eqnarray*}\sum_{k=0}^{p+1}\binom{2p+2-k}{k} & = & \sum_{k=0}^{p}\binom{2p+1-k}{k}+\sum_{k=0}^{p}\binom{2p-k}{k}\\\\& = & \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}+\sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor }\binom{n-1-k}{k}\\\\& = & F_{n+1}+F_{n}\qquad\text{(hypothèse de récurrence)}\\\\& = & F_{n+2}\end{eqnarray*}$

➣ Si $n+1$ est impair, on pose cette fois $n+1=2p+1$ et le calcul est similaire :

$\begin{eqnarray*}\sum_{k=0}^{p}\binom{2p+1-k}{k} & = & 1+\sum_{k=1}^{p}\left[\binom{2p-k}{k}+\binom{2p-k}{k-1}\right]\\\\& = & \left[1+\sum_{k=1}^{p}\binom{2p-k}{k}\right]+\sum_{j=0}^{p-1}\binom{2p-1-j}{j}\\\\& = & \sum_{k=0}^{p}\binom{2p-k}{k}+\sum_{k=0}^{p-1}\binom{2p-1-k}{k}\\\\& = & \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}+\sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor }\binom{n-1-k}{k}\\\\& = & F_{n+1}+F_{n}\\\\& = & F_{n+2}\end{eqnarray*}$

La proposition est établie.

Preuve combinatoire (cliquer pour déplier / replier)

Imaginons un petite grenouille, confortablement installée au pied d’un escalier. Elle doit le gravir, mais en respectant une consigne : elle ne peut effectuer que des sauts dirigés vers le haut de l’escalier et ne franchit qu’une marche ou deux à chaque saut.

De combien de façons la grenouille peut-elle gravir l’escalier ? Notons $u_{n}$ la réponse, qui dépend bien sûr du nombre $n$ de marches …

On calcule facilement $u_{n}$ « à la main » pour les petites valeurs de $n$ :

Ces quelques observations suggèrent la formule générale :

$\boxed{\forall n\in\mathbb{N}^{\star},\,u_{n}=F_{n+1}}\qquad\left(\spadesuit\right)$

Celle-ci se prouve à l’aide d’une récurrence d’ordre 2.

Manifestement : $u_{1}=1=F_{2}$ , $u_{2}=2=F_{3}$ . Supposons (hypothèse de récurrence) que $u_{n-1}=F_{n}$ et $u_{n}=F_{n+1}$ .

Etant donné un escalier de $n+1$ marches (avec $n\geqslant2$ ), il existe $u_{n-1}$ manières de le gravir en terminant par un saut de deux marches, et il en existe $u_{n}$ autres se terminant par le franchissement d’une seule marche. Au total : $u_{n+1}=u_{n-1}+u_{n}=F_{n}+F_{n+1}=F_{n+2}$ , comme souhaité.

Changeons maintenant de point de vue pour le calcul de $u_n$ . Etant donné un entier naturel $k$ , considérons le nombre de façons de gravir un escalier de $n$ marches, en effectuant exactement $k$ sauts de deux marches (ce qui impose $2k\leqslant n$ ).
Le nombre total de sauts effectués est alors : $k+\left(n-2k\right)=n-k$ . Une telle façon de gravir l’escalier s’identifie à un mot de $n-k$ lettres, chaque lettre pouvant être ‘1’ ou ‘2’ et le mot comportant un total de $k$ lettres ‘2’ : il existe $\displaystyle{\binom{n-k}{k}}$ tels mots. Le nombre de façons de gravir l’escalier est donc :

$\boxed{\forall n\in\mathbb{N}^{\star},\,u_{n}=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\,\binom{n-k}{k}}\qquad\left(\clubsuit\right)$

En confrontant $(\spadesuit)$ et $(\clubsuit)$ , nous retrouvons le fait que :

$\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\,\binom{n-k}{k}=F_{n+1}$

J’espère que cet article vous sera utile !

Vous pouvez commencer à chercher des exercices relatifs aux coefficients binomiaux. Je vous ai préparé des énoncés ici.

Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Cet article a 2 commentaires

Joseph Cesana 7 Août 2018 Répondre

Dans l’argument plus rigoureux de la symetrie des coefficients binomiaux, n’a t’on pas /A -> A lorsqu’on ecrit l’application
P(n-k) (E) -> P(k) (E)?
1. René Adad 8 Août 2018 Répondre
  
  Bonjour Joseph,
  Le formalisme adopté dans l’article est le bon. D’une manière générale, lorsqu’on définit une application u de manière explicite, on spécifie son ensemble de départ E et son ensemble d’arrivée F ainsi que le “mécanisme” par lequel on associe, à chaque élément de E, son image par u. Un élément générique de E est généralement désigné par une lettre (x, y, …), à la rigueur par un couple ou plus généralement un n-uplet si E est un produit cartésien de deux ou plusieurs ensembles, mais JAMAIS par une expression plus complexe.
  
  Par exemple, il est ILLICITE de définir $f:\mathbb{R}\to\mathbb{R},\,x+3\mapsto 5x$ .
  
  Dans l’exemple qui nous intéresse, on définit psi en disant qu’à chaque partie de E de cardinal n-k, on associe son complémentaire dans E. Cela dit, il est certain que si une partie de E de cardinal n-k se présente sous la forme du complémentaire d’un certain B, alors son image par psi est B.