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).
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$).
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
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.
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
ou
de ces résultats.
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.
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}$.
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.
