Triangle de Pascal

Le triangle de Pascal, également connu sous le nom plus impressionnant de "coefficients binomiaux", est le triangle infini composé de nombres comme suit,

1
1      1
1      2      1
1      3      3      1
1      4      6      4      1
...     ...     ...     ...     ...     ...

Il est donc fabriqué en commençant chaque ligne par un 1, puis, au milieu entre deux nombres de la ligne au-dessus, la somme de ces deux nombres. 

Par exemple, les 4 ci-dessus sont placés entre un 1 et un 3 dans la ligne au-dessus  (respectivement, pour le deuxième 4, entre le 3 et le 1 de la ligne au-dessus).
Encore mieux (ça sera pratique dans la suite), on peut aussi s'imaginer les lignes complétées par des zéros à droite et à gauche jusqu'à l'infini. (Je les écris néanmoins plus discrètement en petit et gris dans le schéma ci-dessous). Ainsi la deuxième règle permet aussi de calculer les 1 qui sont au bord, car ils ont comme "parents" un 1 et un 0 dans la ligne au-dessus) :

...    o     o     o     o     1     o     o     o     o     ...

...    o     o     o     o     1     1     o     o     o     o    ...
...     o    o     o     1     2     1     o     o     o     ...
...    o     o     o     1     3     3     1     o     o     o     ...

...    o     o     o     1     4     6     4     1     o     o     o     ...

Les mathématiciens ont introduit un symbole pour ce tableau de nombres. Ils utilisent la notation  C_n^k  pour désigner les valeurs dans la ligne numéro n, en commençant avec n = 0 pour la première ligne, qui ne contient qu'un seul 1 au milieu. (Ce numéro de ligne n est donc égal au nombre qui vient juste après le premier 1. On peut voir que c'est vrai aussi pour n = 0 !)

Le deuxième indice k, écrit en haut, indique la place dans la ligne, également en commençant avec k = 0 pour numéroter la place du premier 1 de chaque ligne.
Nous avons donc nos premières formules :

Pour tout n ≥ 0 :  C_n⁰ = 1 ;   C_n¹ = n ;   C_n^k = 0  pour tout k < 0.

De plus, la "règle de construction" du triangle peut s'écrire : 

Pour tout n ≥ 0 et pour tout k :  C_n+1^k  =  C_n^{k − 1}  +  C_n^k  .

(Par exemple pour k = 0, on veut additionner  0 = C_n⁻¹  au premier  1 = C_n⁰  pour trouver le premier  1 = C_n+1⁰  de la ligne suivante.
Pour le second élément (k = 1), on a bien  1 = C_n⁰  plus  n = C_n¹  qui donnent le  n+1 = C_n+1¹  de la ligne suivante.)

Exemple 2 : pour  n = 3  et  k = 0, on a :  C₃⁰  +  C₃¹  =  1 + 3  =  4  =  C₄⁰ . 

Exemple 3 : pour  n = 3  et  k = 1, on a :  C₃¹  +  C₃²  =  3 + 3  =  6  =  C₄¹ . (Exercice : vérifier !)

Il est évident qu'il y a  n + 1  nombres non-nuls dans la ligne numéro  n   (en commençant avec un  (1)  dans la ligne 0, puis les deux  (1, 1)  dans la ligne 1, puis les trois nombres (1, 2, 1) dans la ligne 2, etc.)  On peut donc compléter nos formules pour les éléments "en fin de ligne" :

Pour tout n ≥ 0 :  C_nⁿ⁻¹ = n ;  C_nⁿ = 1 ;  C_n^k = 0  pour tout k > n.

En effet, on a plus généralement une symétrie de toute la ligne par rapport au centre, ou autrement dit, une ligne ne change pas si on la renverse ou si on la lit en commençant par la fin. (On appelle ceci un palindrome.) On peut exprimer cela par la formule :

Pour tout n ≥ 0 et tout k :  C_n^n − k  =  C_n^k  .

(Vérifier que cela marche aussi pour k < 0 et k > n !) Ce triangle a énormément d'applications !  

• Les nombres C_n^k  donnent le nombres de combinaisons, c'est-à-dire, de choix pour sélectionner k objets parmi n. (D'où la lettre C !)
   
• Ils donnent aussi les coefficients dans une expressions de la forme
  (a + b)ⁿ = (a + b)·(a + b)···(a + b),  produit de  n  facteurs  a + b.
  (Un objet comme  a + b  s'appelle un binôme (parce qu'il y a deux noms, a et b [voir premier épisode de la série "Le jeu de la dame !"], d'où le nom "coefficient binomial".)
   
  Par exemple, (a + b)² = (a + b)·(a + b) = a² + 2 ab + b² : on reconnaît  (1, 2, 1) de la ligne 2.
  Ou encore, (a + b)³ = (a + b)·(a + b)·(a + b) = a³ + 3 a² b + 3 a b² + b³ :  (1,3,3,1) de ligne 3 !
   
  Nous allons revoir ça en plus de détails dans un autre post. Regardons juste encore cette pépite :
  Pour a = b = 1, on trouve donc que (1+1)ⁿ = 2ⁿ est égal à la somme de tous les nombres  C_n^k  de la ligne n ! (Vérifiez que cela fonctionne bien pour les lignes 1, 2, 3, ... et même 0 !)

On a une formule permettant de calculer n'importe quel  C_n^k  sans dresser tout le triangle des lignes qui le précèdent. En effet, 

C_n^k  =  n! / (k! (n − k)!)  =  n / 1 · (n − 1) / 2 · (n − 2) / 3 ··· (n + 1 − k) / k .

(On a donc k produits de fractions, dont les dénominateurs vont de 1 à k, et les numérateurs descendent de n à (n + 1 − k) : inutile de calculer ce nombre, ça sera tout simplement le k-ième dans la suite décroissante.  Sur le papier on écrit ce produit de fractions  d'habitude sur un seul trait de fraction.)

Les points d'exclamation dans la première formule signifient la "factorielle" : n!  est le produit de tous les nombres de 1 jusqu'à n, soit :   n!  =  1 · 2 · 3 ··· (n − 1) · n .

Par exemple :  2!  =  1·2  =  2 ;    3!  =  1·2·3  =  6 ;   4!  =  1·2·3·4  =  24 ;   5!  =  4! · 5  =  120.

(On voit que pour passer d'une factorielle à la suivante, il suffit de multiplier par le nombre suivant.

On a donc la définition récursive :   factorielle( n ) :=  si  n > 1  alors  n · factorielle(n − 1)  sinon 1.)

Finissons pour aujourd'hui sur quelques images :
Si l'on remplace tous les nombres impairs (1, 3, 5, ...) du triangle par des 1 ou des carrés noirs (ou triangles bleus ci-dessous), et tous les nombres pairs (0, 2, 4, ...) par des 0 ou des carrées blancs (ou des triangles jaunes ci-dessous), on obtient une figure dite "fractale", le triangle de Sierpinski :

(Image: Wikipedia)

Cette figue est dite fractale, parce qu'on obtient la figure "limite" qui correspond à un triangle infini, en découpant du centre d'un triangle noir un plus petit, comme suit, puis en répétant ce procédé :

N'est-ce pas beau, les mathématiques ? ;-)