Triangle de Pascal, mots et chemins

6.1 Le triangle de Pascal

On range les nombres $\binom{n}{k}$ dans un tableau : la ligne $n$ contient $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Chaque ligne commence et finit par $1$. Grâce à la relation de Pascal, chaque autre nombre est la somme du nombre situé juste au-dessus et de son voisin de gauche.

Par exemple, $\binom73 = \binom62 + \binom63 = 15 + 20 = 35$. Chaque ligne se lit de la même façon dans les deux sens : c'est la symétrie $\binom{n}{n-k} = \binom{n}{k}$.

6.2 Un peu d'histoire

Ce tableau porte le nom de Blaise Pascal, qui lui consacre un traité au XVIIe siècle. Mais des propriétés arithmétiques de ce triangle étaient déjà présentes dans les travaux combinatoires des mathématiques indiennes et chinoises, bien avant lui. La combinatoire est aussi un sujet favori des récréations mathématiques depuis l'Antiquité, et l'est encore chez des arithméticiens du XIXe siècle comme Lucas, Delannoy et Laisant. Aujourd'hui, les « mathématiques discrètes » se développent beaucoup, portées notamment par l'informatique et l'intelligence artificielle.

6.3 Représentation par des mots

Propriété. Le nombre de mots de longueur $n$, écrits avec les lettres $0$ et $1$, qui contiennent exactement $k$ fois la lettre $1$, est $\binom{n}{k}$.

Pourquoi. Un tel mot est connu dès qu'on sait où sont ses $k$ lettres $1$ : c'est une partie à $k$ éléments de l'ensemble des positions $\{1\,;2\,;\ldots\,;n\}$.

Exemple 19. Les mots de longueur $5$ avec exactement deux $1$ sont $11000$, $10100$, $10010$, $10001$, $01100$, $01010$, $01001$, $00110$, $00101$ et $00011$ : il y en a $\dbinom52 = 10$.

De même, dans une succession de $n$ épreuves à deux issues, il y a $\binom{n}{k}$ issues comportant exactement $k$ succès : il suffit de choisir les rangs des succès. Dans l'arbre, ce sont les chemins qui passent exactement $k$ fois par une branche $S$. Pour $n = 3$ et $k = 2$ : $SS\overline{S}$, $S\overline{S}S$ et $\overline{S}SS$, soit $\binom32 = 3$ issues. Le chapitre 11 s'en servira.

6.4 Représentation par des chemins sur un quadrillage

Exemple 20. Dans un quartier dont les rues forment un quadrillage, on va du point $A$ au point $B$, situé $4$ rues plus à droite et $3$ rues plus haut, en allant toujours vers la droite ($D$) ou vers le haut ($H$). Un trajet est un mot de $7$ lettres, avec $4$ lettres $D$ et $3$ lettres $H$, par exemple $DHDDHHD$. Il est connu dès qu'on choisit les $3$ positions des $H$ parmi les $7$ : il y a $\dbinom73 = 35$ trajets.

6.5 Somme des nombres d'une ligne

Propriété (programme). Pour tout entier $n \geq 0$ : $\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.$

Le symbole $\displaystyle\sum_{k=0}^{n}$ (« somme pour $k$ allant de $0$ à $n$ ») est une écriture courte de cette somme de $n + 1$ termes.

Démonstration par dénombrement (programme). Soit $E$ un ensemble à $n$ éléments. Chaque partie de $E$ a un nombre d'éléments $k$ compris entre $0$ et $n$.

1. Pour chaque $k$, il y a $\binom{n}{k}$ parties à $k$ éléments.
2. Ces $n + 1$ groupes de parties sont deux à deux disjoints (une partie n'a qu'un seul nombre d'éléments), et ensemble ils contiennent toutes les parties de $E$.
3. Par le principe additif, le nombre de parties de $E$ est $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}$.
4. Or ce nombre vaut $2^n$ (leçon 2). D'où l'égalité.

Exemple 21. Ligne $4$ : $1 + 4 + 6 + 4 + 1 = 16 = 2^4$. Ligne $7$ : $1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 128 = 2^7$.

Conséquence. Un ensemble à $n$ éléments a $2^n - 1$ parties non vides. Par exemple, avec $6$ ingrédients, on compose $2^6 - 1 = 63$ pizzas avec au moins un ingrédient.