Le triangle de Pascal

Piste rouge 8 avril 2011  - Ecrit par  Roland Bacher Voir les commentaires (5)

Le triangle de Pascal
\[\begin{array}{lcccccccccccccccccccc} &&\qquad&&&&&&&&&1\\ &&&&&&&&&&1&&1\\ &&&&&&&&&1&&2&&1\\ &&&&&&&&1&&3&&3&&1\\ &&&&&&&1&&4&&6&&4&&1\\ &&&&&&1&&5&&10&&10&&5&&1\\ &&&&&1&&6&&15&&20&&15&&6&&1\\ &&&&1&&7&&21&&35&&35&&21&&7&&1\\ \end{array}\]
est un de ces êtres mathématiques ayant le don d’ubiquité.
On le retrouve partout : algèbre, analyse,
topologie, probabilités, statistiques, combinatoire, aucun domaine des maths
ne lui échappe. Il apparaît évidemment aussi en physique,
et par exemple en génétique.

Le nom de « triangle de Pascal » est trompeur : Pascal
n’était pas la première personne à s’y intéresser. Ce billet et l’article
Wikipedia sur le triangle de Pascal

(ou la version anglaise, un peu plus développée) contiennent quelques informations historiques.

Je me contenterai ici de décrire quelques propriétés
élémentaires du triangle de Pascal
et je reviendrai peut-être sur quelques-unes de ses faces
cachées dans un article ultérieur.

Les nombres qui apparaissent dans le triangle de Pascal sont les
coefficients binomiaux, notés $C_n^k$ par les francophones et
${n\choose k}$ par les anglophones.
J’utiliserai la
notation anglophone ${n\choose k}$
car elle s’est universellement imposée (sauf dans
quelques villages d’irréductibles Gaulois).

Combinaisons

Le coefficient binomial ${n\choose k}$ correspond au nombre
de possibilités de choisir $k$ objets parmi $n$ objets distincts
. Supposons par exemple
que vous voulez partir en vacances en n’emportant que trois volumes
parmi les sept dédiés aux exploits magiques de Harry Potter. Le nombre de choix possibles est alors
donné par les ${7\choose 3}=35$ façons différentes
de choisir les trois tomes.

Pour le vérifier, vous pouvez
lire le $3-i$ème nombre à la $7-$ième ligne
du triangle de Pascal
\[\begin{array}{lcccccccccccccccccccc} &&&&&&&&&&&{0\choose 0}\\ &&&&&&&&&&{1\choose 0}&&{1\choose 1}\\ &&&&&&&&&{2\choose 0}&&{2\choose 1}&&{2\choose 2}\\ &&&&&&&&{3\choose 0}&&{3\choose 1}&&{3\choose 2}&&{3\choose 3}\\ \end{array}\]
sachant qu’il faut ignorer la première ligne du triangle
et le premier élément de chaque ligne.

Vous pouvez également utiliser
la formule
\[{7\choose 3}=\frac{7!}{3!(7-3)!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)(4\cdot 3\cdot 2\cdot 1)}= \frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}=35\]
(où $n!=1\cdot 2\cdots \cdot n$ désigne la factorielle de $n$
obtenue en effectuant le produit de tous les entiers entre $1$ et $n$).

Preuve. Si vous choisissez les volumes avec un ordre,
vous avez $7$ possibilités pour le choix du premier livre,
$6$ choix possibles pour le deuxième livre et finalement $5$
choix pour le dernier. Ceci vous donne cependant une suite ordonnée
de trois éléments (distincts) parmi $7$, par exemple la suite des tomes
3, 1 et 6. Mais l’ordre de ces trois volumes choisis n’est pas important ; vous
déciderez d’un ordre de lecture une fois arrivé à destination !
Pour vous débarrasser de cet ordre, il
faut diviser le résultat obtenu par le nombre de possibilités
d’ordonner les $3$ livres choisis. Comme il y a $3$ choix possibles
pour déterminer le premier livre, ensuite $2$ choix pour le deuxième
et que le dernier livre est forcément celui qui reste, on
a $3!=3\cdot 2\cdot 1$ ordres possibles (donnés par
$(1,3,6)$, $(1,6,3)$, $(3,1,6)$, $(3,6,1)$, $(6,1,3)$ et $(6,3,1)$
pour les tomes $3,1$ et $6$).

Coloriages d’œufs de Pâques

De combien de manière peut-on colorier $7$ œufs en ayant $3$
couleurs à disposition ? Cette question semble de nature un peu
différente du problème considéré plus haut.
En effet, les $7$ œufs sont tous identiques, pondus par le même

coq roux,

Un pédant m’a fait remarquer que les coqs ne pondent pas d’œufs.
Qu’est-ce qu’il en saît ! De plus, ceci est un article de maths, pas
de biologie !

Remarque : Compter le nombre de façons de colorier $7$ objets distincts avec $3$ couleurs est beaucoup plus simple car on
peut choisir la couleur de chaque objet de manière indépendante ce qui donne $3^7$ possibilités.

contrairement aux $7$ volumes
de la saga Potter. D’autre part, il s’agit de constituer
$3 $ tas d’œufs selon leur couleur future.

L’astuce suivante permet cependant de rapprocher les deux problèmes.
Numérotons nos pots de couleurs de $1$ à $3=k$ et rajoutons aux $n=7$ œufs à colorier $2=k-1$ œufs supplémentaires empruntés à un voisin.
Rangeons nos $7+2=n+(k-1)$ œufs à la queue leu leu en les faisant précéder par le premier pot de peinture. Choisissons
$2=k-1$ œufs pour les retourner à notre voisin serviable. Ce choix à
créé $2=k-1$ trous que nous
bouchons par les autres pots de peinture en gardant leur ordre : le deuxième pot de peinture à la place du premier œuf rendu et ainsi de suite.
Nous colorions maintenant nos œufs dans l’ordre en utilisant également les
pots de peinture dans l’ordre : les œufs qui suivent le premier pot jusqu’au deuxième sont coloriés avec la première couleur, les œufs entre le deuxième et le troisième pot prennent la couleur numéro deux etc.
Le nombre de coloriages de nos $n=7$ œufs avec $k=3$ couleurs
est donc donné par les
\[{n+k-1\choose k-1}={7+2\choose 2}=\frac{9\cdot 8}{2\cdot 1}=36\]
façons possibles de rester en bons termes avec notre voisin en lui
rendant $2=k-1$ œufs.

Le coefficient binomial ${n+k-1\choose k-1}$ donne donc le nombre de
façons de colorier $n$ objets identiques avec $k$ couleurs. Il donne aussi
le nombre de monômes de degré total $n$ en $k$ variables $x_1,\dots,x_k$ car il s’agit
de « colorier » $n$ facteurs $x$ dans le produit $x^n=x\cdot x\cdots x$
par les $k$ indices disponibles.

Quelques identités

En toute généralité, le coefficient binomial ${n\choose k}$ est
donné par la formule
\[{n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot (n-1)\cdots (n-k+2)\cdot(n-k+1)}{k\cdot (k-1)\cdots 2\cdot 1}\ .\]
Ainsi on trouve par exemple
\[{100\choose 10}=\frac{100\cdot 99\cdot 98\cdot 97\cdot 96\cdot 95\cdot 94\cdot 93\cdot 92\cdot 91}{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}= 17310309456440\ .\]
Remarquez qu’il n’est pas complètement évident que
cette formule ne donne que des entiers si on ne connaît pas son
interprétation combinatoire .

La formule ${n\choose k}=\frac{n!}{k!(n-k)!}$ donne la meilleure
méthode connue pour calculer un coefficient binomial isolé.
Vous avez cependant probablement remarqué que chaque nombre
apparaissant dans le triangle de Pascal (sauf le tout premier)
est la somme de ses deux voisins supérieurs immédiats
(en remplaçant un voisin absent par $0$).
Ceci donne une construction rapide du triangle de Pascal à
condition que les coefficients binomiaux ${n\choose k}$
(définis par la formule ${n\choose k}=\frac{n!}{k!(n-k)!}$)
vérifient bien l’identité
\[{n\choose k}={n-1\choose k-1}+{n-1\choose k}\ .\]

Montrons cela pour $n=7,\ k=3$, le cas général n’étant
guère différent. En effet, plaçons nous devant notre
bibliothèque et observons le rayon incurvé par le poids des puissants
sortilèges de Potter. À la vue du tome $1$, votre réaction
est peut-être : « Cela fait longtemps que je ne l’ai plus relu »,
vous le prenez
et il vous reste deux livres à choisir parmi les $6$
volumes restants. Ou alors vous vous exclamez : « Non, pas celui-là,
je le connais par cœur » et vous choisissez donc vos trois
romans de vacances parmi les $6$ tomes restants. Comme les
deux cas de figure sont disjoints, vous avez bien
\[{7\choose 3}={6\choose 2}+{6\choose 3}\]
choix possibles. Numériquement, $35={7\choose 3}$
est bien la somme de $15={6\choose 2}$ et de $20={6\choose 3}$.

Vous avez peut-être remarqué la jolie symétrie
gauche-droite
du triangle de Pascal qui se traduit par l’identité
\[{n\choose k}={n\choose n-k}\ .\]
Cette égalité est facile
à comprendre : choisir 3 tomes à emporter parmi les 7
est la même chose que sélectionner les $4=7-3$ volumes qui
continueront de prendre la poussière à la maison.

En contemplant le triangle de Pascal suffisamment longtemps,
vous avez peut-être remarqué
qu’on semble avoir \[{n\choose k}=\frac{n}{k}{n-1\choose k-1}\]
pour $k\geq 1$.

Ceci aussi s’explique très simplement :
En effet, $3{7\choose 3}$ compte le nombre de possibilités
de choisir vos trois tomes en décidant également
du tome que vous aller entamer durant le vol vers votre île de rêve.
Or ceci revient à choisir le livre à ouvrir durant
le voyage ($7$ possibilités) et à compléter ce livre par
le choix des deux tomes à lire sur place (${6\choose 2}$
possibilités car il faut choisir ces deux tomes parmi les $6$
volumes restants). On a donc bien $3{7\choose 3}=7{6\choose 2}$.

Finalement vous avez peut-être également vu
que la somme de tous les termes sur une même ligne du triangle
vaut $1,2,4,8,16,\dots$.

La raison en est simple : la somme
\[{7\choose 0}+ {7\choose 1}+{7\choose 2}+{7\choose 3}+{7\choose 4}+{7\choose 5} +{7\choose 6}+{7\choose 7}\]
compte le nombre de possibilités que vous
avez de choisir un nombre arbitraire de tomes parmi vos 7 volumes
magiques. Vous êtes alors libre de considérer chaque
volume isolément et de décider à chaque fois s’il vous
accompage dans vos bagages ou s’il reste à la maison.
Cela fait donc bien
$2\cdot 2\cdots 2=2^7$ choix possibles. En d’autres termes,
$2^7$ est le nombre de sous-ensembles d’un ensemble à $7$
éléments.

Les quelques preuves données jusqu’à présent étaient
d’un genre assez particulier qu’on qualifie de bijective :
Pour montrer une identité $A=B$ entre deux entiers
naturel, on exhibe un ensemble fini dont on compte les
éléments de deux façons différentes.
Si la première manière de compter donne $A$ et la
deuxième donne $B$, alors on a bien l’égalité
$A=B$. Une telle preuve est particulièment
instructive car elle « explique » l’identité
en question ce qui n’est pas forcément le cas d’une
preuve qui utilise un calcul algébrique.
On peut bien sûr également donner des

preuves algébriques

\[\begin{array}{rcl} {n-1\choose k-1}+{n-1\choose k}&=& \frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}\\ &=&\frac{(n-1)!\left(k+(n-k)\right)}{k!(n-k)!}= \frac{n!}{k!(n-k)!}\\ &=&{n\choose k} \end{array}\]
et
\[\begin{array}{rcl} \frac{n}{k}{n-1\choose k-1}&=& \frac{n}{k}\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n!}{k!(n-k)!} ={n\choose k} \end{array}\]

ou

par récurrence

Pour montrer qu’on a $\sum_{k=0}^n{n\choose k}=2^n$, on peut procéder
par récurrence : la formule est évidemment vraie pour $n=0$
et on a
\[\begin{array}{rcl} \sum_{k=0}^{n+1}{n+1\choose k}&=&{n+1\choose 0}+ \sum_{k=1}^n\left({n\choose k-1}+{n\choose k}\right)+ {n+1\choose n+1}\\ &=&{n\choose 0}+\left(\sum_{k=1}^n{n\choose k}\right)+ \left(\sum_{k=0}^{n-1}{n\choose k}\right)+{n\choose n}\\ &=&\left(\sum_{k=0}^n{n\choose k}\right)+ \left(\sum_{k=0}^n{n\choose k}\right)\\ &=&2\cdot 2^n=2^{n+1} \end{array}\]

de ces résultats.

Probabilités

Pascal aimait les paris
et il n’est donc pas étonnant que son triangle
ait des relations étroites avec les probabilités car
en posant $x=y=\frac{1}{2}$, le théorème binomial
(ou l’interprétation combinatoire) montre que $\frac{1}{2^n}{n\choose k}$
donne la probabilité qu’un jeu de pile ou face équitable itéré
$n$ fois produise $k$ fois pile.

En faisant tendre le nombre d’itérations $n$ vers l’infini on
remarque une chose curieuse : le comportement du jeu, convenablement
renormalisé, tend vers une gaussienne,
voir l’article La courbe en cloche de Jean-Pierre Kahane. Ce phénomène est connu
sous le nom de théorème de la limite centrale. En particulier
un ivrogne sous l’emprise d’une cuite parfaite (une cuite est parfaite
si elle réinitialise complètement la mémoire sans provoquer
l’arrêt total des fonctions vitales)
qui fait aléatoirement des pas vers la gauche et vers la droite
depuis son bar préféré se trouve en moyenne à distance environ
$\sqrt{n}$ (ou plus précisément $\sqrt{n/(2\pi)}$)
de sa barmane préférée après $n$ titubations.

Formule du binôme

Le lecteur a probablement déjà rencontré
l’identité remarquable
\[(x+y)^2=x^2+2xy+y^2\ .\]
Cette identité (ainsi que sa sœur $(x-y)^2=x^2-2xy+y^2$) est
étroitement liée au triangle de Pascal car on a :
\[\begin{array}{rcl} (x+y)^0&=&1\\ (x+y)^1&=&x+y\\ (x+y)^2&=&x^2+2xy+y^2\\ (x+y)^3&=&x^3+3x^2y+3xy^2+y^3 \end{array}\]
et plus généralement
\[(x+y)^n={n\choose 0}x^n+{n\choose 1} x^{n-1}y+ {n\choose 2}x^{n-2}y^2+\dots+{n\choose n-1}xy^{n-1}+{n\choose n}y^n\]

Cette dernière identité est parfois appelé le théorème binomial.
Sa preuve n’est pas difficile :
un monôme de la forme $x^{n-k}y^k$ apparaissant dans
le produit $(x+y)^n$ correspond à un choix de $k$ facteurs
$y$ parmi les $n$ facteurs possibles. Le nombre de tels
monômes est donc donné par le coefficient binomial ${n\choose k}$.

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Xavier Caruso, subshift, Yoann et chuy.

Partager cet article

Pour citer cet article :

Roland Bacher — «Le triangle de Pascal» — Images des Mathématiques, CNRS, 2011

Commentaire sur l'article

  • Le triangle de Pascal

    le 9 avril 2011 à 17:06, par nicok

    Bonjour,
    Il y a une petite erreur de notation, sans importance puisque la notation est introduite dans le bon sens, sur la seconde image du triangle de Pascal : dans les coefficients binomiaux, les nombres qui devraient être en bas sont en haut et inversement, comme dans la notation française.
    Sinon je trouve l’article très clair, chapeau !
    J’ai aussi écrit un article sur la combinatoire et le triangle de Pascal sur mon blog, qui pourrait peut-être intéresser certains lecteurs :
    http://mathsla.blogspot.com/2011/04/combinatoire.html

    Répondre à ce message
    • Le triangle de Pascal

      le 11 avril 2011 à 07:51, par Roland Bacher

      En effet. Merci de l’avoir signalé.

      Répondre à ce message
    • Le triangle de Pascal

      le 11 avril 2011 à 11:57, par Roland Bacher

      L’erreur est maintenant corrigée. Merci de l’avoir signalé.

      Répondre à ce message
  • Le triangle de Pascal

    le 14 décembre 2011 à 10:11, par Cidrolin

    Bonjour,

    Dans la formule du binôme, il faut corriger

    le x^(n-1) en x^(n-2)

    (x+y)^n=n\choose 0x^n+n\choose 1 x^n-1y+
    n\choose 2x^n-1y^2+\dots+n\choose n-1xy^n-1+n\choose ny^n

    Répondre à ce message
    • Le triangle de Pascal

      le 19 mars 2012 à 12:10, par Roland Bacher

      Merci beaucoup. C’est maintenant corrigé.

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM