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)n.

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)0 = 1

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

2 : 1 2 1      (a+b)2 = 1*a2 + 2*a*b + 1*b2

3 : 1 3 3 1    (a+b)3 = 1*a3 + 3*a²*b + 3*a*b² + 1*b3

4 : 1 4 6 4 1  (a+b)4 = 1*a4 + 4*a3*b + 6*a²*b² + 4*a*b3 + 1*b4

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)4" 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 10016.

= 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 2n.

On montre directement que le nombre de parties d'un ensemble E à n éléments est 2n 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 np.)

 

Télécharger le code source Delphi