Le triangle de Pascal

Le triangle de Pascal est le tableau des coefficients qui sont utilisés pour le développement de certaines expressions comme (a+b)² ou (a+b)ⁿ.

Cela s'appelle la "formule du binôme de Newton". Les coefficients s'appellent les "coefficients binomiaux" ou "coefficients du binôme".

Ce triangle est le suivant :

0 : 1 (a+b)⁰ = 1

1 : 1 1 (a+b)¹ = 1*a + 1*b

2 : 1 2 1 (a+b)² = 1*a² + 2*a*b + 1*b²

3 : 1 3 3 1 (a+b)³ = 1*a³ + 3*a²*b + 3*a*b² + 1*b³

4 : 1 4 6 4 1 (a+b)⁴ = 1*a⁴ + 4*a³*b + 6*a²*b² + 4*a*b³ + 1*b⁴

On obtient chaque coefficient en additionnant le nombre qui lui est situé au-dessus ainsi que celui qui lui est situé au-dessus à gauche.

Exemples :

- on obtient le 6 en faisant 3+3

- on obtient le 4 qui est après le 6 en faisant 3+1.

Le numéro qui est en tête de chaque ligne de ce triangle est la puissance à laquelle "a+b" est élevé;ainsi pour la puissance 4,"(a+b)⁴" admet les coefficients 1, 4, 6, 4, 1 qu'on voit dans l'expression développée.

Etudions l'algorithme nécessaire à l'affichage de ce triangle :

- on remarque que la diagonale est toujours à 1 ---> point d'appui

- on remarque que la première colonne est toujours à 1 ---> point d'appui

- pour tout autre élément qui se trouve à la ligne y et colonne x, on

affiche la somme de :

- l'élément de coordonnées y-1,x

- l'élément de coordonnées y-1,x-1

function comb(x, y: integer): integer;
begin
 if (x = 1) or //--- point d'appui : la première colonne
 (y = x) //--- point d'appui : la diagonale
 then comb := 1
 else
 comb := comb(x, y - 1) + comb(x - 1, y - 1); //--- appel récursif
end;

On voit ici la définition récursive, car tout élément du tableau est défini par deux autres éléments qui sont inconnus, chacun étant défini par deux autres et ainsi de suite, excepté la diagonale et la première colonne; c'est grâce à ces deux indices qu'on va déterminer tout le tableau.

Voici le programme qui affiche le triangle de Pascal :

procedure tform1.button1Click(sender: tobject);
var ligne, colonne: integer;
 
 function comb(x, y: integer): integer;
 begin
 if (x = 1) or (y = x) then
 comb := 1
 else
 comb := comb(x, y - 1) + comb(x - 1, y - 1);
 end;
begin
 for ligne := 1 to 15 do
 for colonne := 1 to ligne do
 canvas.textOut(colonne * 30, ligne * 30, inttostr(comb(colonne, ligne)));
end;
 

Et maintenant, un peu de maths :

Formule du triangle de Pascal

Démonstration combinatoire

Soit E un ensemble à n éléments et a un élément de E.

Notons :

A l’ensemble des parties de E à p éléments (p n),

B l’ensemble des parties à p éléments de E contenant a,

C l’ensemble des parties à p éléments de E ne contenant pas a.

Le cardinal de A est .

Comme B est l’ensemble des parties à p-1 éléments de auxquelles on a ajouté a, le cardinal de B est égal à celui de l’ensemble des parties à p-1 éléments de . D’où Card(A)= .

Comme C est l’ensemble des parties à p éléments de , Card(C)= .

A étant la réunion disjointe de B et C, on a Card(A)=Card(B)+Card(C), d’où le résultat.

Démonstration directe

Formule du binôme de Newton

Démonstration combinatoire

Le coefficient du terme est égal au nombre de façons de choisir simultanément p paires de parenthèses contenant a parmi les n, soit , d’où le résultat (c’est aussi le nombre de façons de choisir simultanément n-p paires de parenthèses contenant b parmi les n, soit . Or …).

Démonstration par récurrence

La formule se vérifie aisément pour n=0.

Supposons qu’elle est vraie pour n fixé et montrons qu’alors

, d'après la formule de Pascal, d'où le résultat.

La formule étant vraie pour n=0 et l'étant pour n+1 sous l'hypothèse qu'elle l'est pour n fixé, est donc vraie pour tout entier naturel n en vertu de l'axiome de récurrence.

Une application amusante

Calculons 1001⁶.

= 1+6x1000+15x1000000+20x1000000000+15x1000000000000+6x1000000000000000+1000000000000000000

Nous laissons au lecteur le soin de faire l'addition !

Un résultat remarquable

Démonstration 1

Le résultat est immédiat en faisant a=b=1 dans la formule du binôme !

Démonstration 2 (combinatoire)

La somme de tous les pour n fixé (la somme de tous les coefficients binomiaux d'une ligne du triangle de Pascal) est égale au nombre de façons de choisir simultanément entre 0 et n éléments d'un ensemble à n éléments, c'est à dire exactement au nombre de parties de cet ensemble, soit 2ⁿ.

On montre directement que le nombre de parties d'un ensemble E à n éléments est 2ⁿ en remarquant qu'on peut associer à chaque partie P de E l'application f de E sur {0,1} ainsi définie :

f(x)=0 si x n'est pas un élément de P

f(x)=1 si x est un élément de P.

Comme Card(E)=n et Card({0,1})=2, on a le résultat, puisque le nombre d'applications d'un ensemble de cardinal p dans un ensemble de cardinal n est n^p.)

Télécharger le code source Delphi