Formule du triangle de Pascal avec exemples

Qu'est-ce que le Triangle de Pascal ?

Le triangle de Pascal est un tableau triangulaire de nombres qui suit un motif simple basé sur la ligne précédente. Il a été popularisé par le mathématicien français Blaise Pascal au XVIIe siècle. Le triangle commence par un seul « 1 » en haut, et chaque ligne suivante commence et se termine également par un « 1 ».

Au-delà de sa forme élégante, le triangle de Pascal recèle des relations mathématiques profondes. Il est étroitement lié au binôme de Newton, au dénombrement combinatoire et aux probabilités, ce qui explique sa présence dans les cours d'algèbre, de statistiques et d'informatique du monde entier.

Histoire du Triangle de Pascal

Bien que portant le nom de Blaise Pascal, le triangle lui est antérieur de plusieurs siècles. Le texte mathématique chinois « Les Neuf Chapitres sur l’art mathématique » contient l’un des plus anciens exemples connus, présentant nombre des mêmes régularités que nous utilisons aujourd’hui.

Le mathématicien persan Al-Karaji et l'érudit indien PingAla a également exploré des ensembles similaires. Pascal a formalisé les propriétés du triangle dans son traité de 1654 intitulé « Traité du triangle arithmétique », qui a donné à la structure son nom moderne en mathématiques occidentales.

Construction du Triangle de Pascal

La construction du triangle de Pascal est simple. La seule règle à retenir est que chaque ligne commence et se termine par 1, et que chaque nombre sur deux est construit à partir de la ligne précédente.

Pour toute ligne r et colonne c, la valeur est égale à la somme des nombres des colonnes c-1 et c de la ligne r-1.

Ici,

• r = 3, 4, 5, …
• n et c = 2, 3, 4, …, r-1.

Voici les étapes pour construire le triangle de Pascal :

Étape 1) Commencez par remplir les deux premières rangées.

Étape 2) Le deuxième élément de la troisième ligne est la somme du premier et du deuxième nombre de la deuxième ligne.

Étape 3) La quatrième ligne commence par « 1 ». Le deuxième chiffre est 3, qui est la somme de 1 et 2 (surligné en bleu).

L'image ci-dessous montre comment remplir la quatrième ligne :

Étape 4) La cinquième ligne comporte cinq nombres. Nous connaissons déjà le modèle de remplissage des lignes grâce aux étapes précédentes.

Formule du triangle de Pascal – Coefficient binomial

Un coefficient binomial compte le nombre de façons de choisir un sous-ensemble de k éléments parmi un ensemble de n éléments. Il est généralement noté « C(n, k) » ou « n parmi k ».

Le coefficient binomial est défini comme suit :

Le symbole « ! » désigne la factorielle d'un nombre.

n! = n.(n-1).(n-2)…3.2.1

Par exemple,

5 ! = 5.4.3.2.1

= 120

Donc, C(5, 3) ou « 5 parmi 3 » = 5! / 3!(5-3)!

= 120 / 12

= 10

Méthode 1 : Construction du triangle de Pascal à partir de la ligne précédente

La procédure décrite ici est identique à celle utilisée pour tracer le triangle manuellement. Supposons que nous souhaitions générer le triangle de Pascal jusqu'à sept lignes.

Voici les étapes à suivre :

Étape 1) Commencez la première ligne par « 1 ».

Étape 2) Pour la ligne « r », l’élément « c » sera la somme de la colonne « c-1 » et de la colonne « c » de la ligne « r-1 ».

Étape 3) Le premier et le dernier chiffre de chaque ligne seront toujours « 1 ».

En suivant ces trois étapes simples, nous pouvons construire systématiquement le triangle entier.

C++ Code du triangle de Pascal par la ligne précédente

#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
  int numbers[n][n];
  for (int row = 0; row < n; row++)
  {
    for (int col = 0; col <= row; col++)
    {
      if (col == 0 || col == row)
      {
        numbers[row][col] = 1;
      }
      else
      {
        numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
      }
      cout << numbers[row][col] << "\t";
    }
    cout << endl;
  }
}
int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printRow(n);
}

Sortie :

How many rows: 7
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

Python Code de la formule du triangle de Pascal par la ligne précédente

def printRow(n):
    numbers = [[0 for row in range(n)]
               for col in range(n)
               ]
    for row in range(len(numbers)):
        for col in range(0, row+1):
            if row == col or col == 0:
                numbers[row][col] = 1
            else:
                numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]

            print(numbers[row][col],end="\t")
        print("\n")
n = int(input("How many rows: "))
printRow(n)

Exemple de sortie du triangle de Pascal :

How many rows: 7
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

Analyse de complexité

A tableau bidimensionnel est utilisé dans cette implémentation. Étant donné que N est le nombre de lignes du triangle de Pascal, cela nécessite N² espaces unitaires. Par conséquent, la complexité spatiale est O(N²).

La fonction utilise deux boucles imbriquées, chacune s'exécutant jusqu'à « N » fois. La complexité temporelle est donc également de O(N²). SUR²), ou complexité temporelle au carré.

Méthode 2 : Construction du triangle de Pascal par calcul du coefficient binomial

On peut déduire directement les nombres du triangle de Pascal à partir des coefficients binomiaux. Le diagramme ci-dessous illustre cette relation :

Voici les étapes pour construire le triangle de Pascal en calculant le coefficient binomial :

Étape 1) La première ligne est C(0, 0). En utilisant la formule ci-dessus, C(0, 0) = 1, car 0! = 1.

Étape 2) Pour la ligne « i », il y aura un total de « i » éléments. Chaque élément est calculé comme C(n, r), où n = i-1.

Étape 3) Répétez l'étape 2 pour autant de lignes du triangle de Pascal que vous souhaitez générer.

C++ Code Triangle de Pascal par coefficient binomial

#include <iostream>
using namespace std;
int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}
int binomialCoefficient(int n, int r)
{
    int result = 1;
    if (r > n)
    {
        return -1;
    }
    result = factorial(n) / (factorial(r) * factorial(n - r));
    return result;
}
void printPascalTriangle(int row)
{
    for (int i = 0; i <= row; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            cout << binomialCoefficient(i, j) << "\t";
        }
        cout << endl;
    }
}
int main()
{
    int n;
    cout << "Enter row number: ";
    cin >> n;
    printPascalTriangle(n);
}

Sortie :

Enter row number: 9
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
1	8	28	56	70	56	28	8	1
1	9	36	84	126	126	84	36	9	1

Python Code Triangle de Pascal par coefficient binomial

def factorial(n):
    result = 1
    for i in range(1,n+1):
        result*=i
    return result
def binomialCoefficient(n,r):
    result =1
    if r>n:
        return None
    result = factorial(n) / (factorial(r) * factorial(n - r))
    return int(result)
def printPascalTriangle(row):
    for i in range(row+1):
        for j in range(i+1):
            print(binomialCoefficient(i, j), end="\t")
        print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)

Exemple de sortie du triangle de Pascal :

Enter row number: 8
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
1       8       28      56      70      56      28      8       1

Analyse de complexité

Cette implémentation utilise trois boucles : une pour calculer le coefficient binomial et deux autres pour parcourir chaque ligne et chaque colonne. Chaque boucle s'exécute jusqu'à n fois, en fonction du nombre de lignes. Par conséquent, la complexité temporelle globale est O(n²).³).

La complexité spatiale est constante car aucun résultat intermédiaire n'est stocké. Le programme calcule chaque élément à la volée et l'affiche sur une ligne, ce qui réduit la complexité spatiale à O (1).

Méthode 3 : Construire le triangle de Pascal par le coefficient binomial modifié

Dans la méthode précédente, nous utilisions la formule du coefficient binomial pour calculer chaque élément. L'approche modifiée déduit C(n, r) directement de C(n, r-1), ce qui réduit le travail d'un ordre de grandeur.

Voici les étapes pour construire le triangle de Pascal à l'aide du coefficient binomial modifié :

Étape 1) Commencez la première ligne par « 1 ».

Étape 2) Calculez C(n, r), où « n » est le numéro de ligne et « r » l’indice de colonne. Affectez cette valeur à la variable C.

Étape 3) Pour calculer le coefficient suivant, utilisez C * (n – k) / k. Attribuez cette nouvelle valeur à C.

Étape 4) Poursuivez l'étape 3 jusqu'à ce que « k » atteigne la fin de la ligne. Après chaque itération, incrémentez k de un.

C++ Code pour le triangle de Pascal par coefficient binomial modifié

#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
  for (int row = 1; row <= n; row++)
  {
    int previous_coef = 1;
    for (int col = 1; col <= row; col++)
    {
      cout << previous_coef << "\t";
      previous_coef = previous_coef * (row - col) / col;
    }
    cout << endl;
  }
}

int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printpascalTriangle(n);
}

Sortie :

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Python Code pour le triangle de Pascal par coefficient binomial modifié

def printpascalTriangle(n):
    for row in range(1, n+1):
        previous_coef = 1
        for col in range(1, row+1):
            print(previous_coef, end="\t")
            previous_coef = int(previous_coef*(row-col)/col)
        print()
n = int(input("How many rows: "))
printpascalTriangle(n)

Résultat des modèles triangulaires de Pascal :

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Analyse de complexité

L'implémentation utilise deux boucles, chacune s'exécutant au maximum « n » fois, où « n » est le nombre de lignes du triangle. La complexité temporelle est donc de O(n^n). Sur²), au carré du temps.

En ce qui concerne la complexité spatiale, nous n'avons besoin d'aucun tableau pour le stockage. Nous utilisons uniquement une variable pour conserver le coefficient binomial précédent, ce qui ne nécessite qu'un espace supplémentaire. La complexité spatiale est donc de : O (1).

Application du triangle de Pascal

Voici quelques applications pratiques du triangle de Pascal :

Expansions binomiales : Les coefficients de tout développement binomial se lisent directement dans le triangle de Pascal. Voici un exemple :

Calcul des combinaisons : Les éléments du triangle de Pascal correspondent directement aux coefficients binomiaux. Par exemple, si vous avez 6 boules et que vous voulez en choisir 3, la réponse est : ⁶C₃Vous trouverez cette valeur dans le 3ème élément de la 6ème ligne du triangle de Pascal.

Probabilité: Le triangle de Pascal est largement utilisé pour calculer les probabilités dans les lancers de pièces, les problèmes de dés et autres événements combinatoires où chaque résultat correspond à une distribution binomiale.

Faits intéressants sur le triangle de Pascal

Voici quelques faits qui vous intéresseront sur le triangle de Pascal :

• La somme de tous les éléments d'une ligne est toujours une puissance de 2.

• La somme des éléments diagonaux des lignes génère la suite de Fibonacci.

• Chaque ligne correspond aux coefficients du développement de (a+b)ⁿ.
• Si vous ne coloriez que les nombres impairs, la figure obtenue forme le triangle fractal de Sierpinski.

FAQ