Triangle de Pascal – Formule, modèles et exemples
Sarah Chen
Qu'est-ce que le Triangle de Pascal ?
Le Triangle de Pascal est un tableau triangulaire de nombres suivi d'un motif particulier et d'une connexion à la ligne qui le précède. Il a été inventé par Blaise Pascal. Ce triangle commence par un élément de la première ligne. Après cela, chaque ligne commence et se termine par « 1 ».
Histoire du Triangle de Pascal
Le livre chinois « Les neuf chapitres sur l'art mathématique » contient l'un des premiers exemples du Triangle de Pascal. De plus, il contient certains des mêmes motifs et qualités que l’on retrouve dans les triangles d’aujourd’hui.
Pascal était l'une des nombreuses personnes en Europe qui ont étudié le triangle. Avant lui, d’autres mathématiciens avaient examiné des tableaux triangulaires similaires de nombres.
Construction du Triangle de Pascal
Construire le triangle de Pascal est simple. La seule chose dont vous devez vous rappeler est que la ligne commence et se termine par 1. La règle pour le reste des nombres est la suivante :
Pour toute ligne r et colonne c, le nombre sera la somme 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) Commençons par remplir deux lignes.
Étape 2) Le deuxième élément de la troisième ligne est la somme des premier et deuxième nombres de la deuxième ligne.
Étape 3) La quatrième rangée commencera par « 1 ». Le deuxième nombre 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 rangée sera composée de cinq nombres. Nous connaissons déjà le modèle de remplissage des lignes lors des étapes précédentes.
Formule du triangle de Pascal – Coefficient binomial
Un coefficient binomial est un nombre qui exprime différentes méthodes pour sélectionner un sous-ensemble de k éléments parmi une collection de n éléments. Fréquemment, il s’écrit « C(n,k) » ou « n choisissez k ».
Le coefficient binomial est défini comme
Le "!" désigne le « factoriel ».
n! = n.(n-1). (n-2)…3.2.1
Par exemple,
5 ! = 5.4.3.2.1
= 120
Alors disons que C(5,3) ou 5 choisissent 3 = 5 ! / 3!(5-3)!
= 120/(12)
= 10
Méthode 1 : Construire le triangle de Pascal selon la ligne précédente
Les étapes de cette procédure sont les mêmes que celles du triangle de Pascal. Disons que nous voulons créer le triangle de Pascal comportant jusqu'à sept lignes.
Les étapes pour y parvenir sont les suivantes :
Étape 1) Commencez la ligne la plus haute par « 1 ».
Étape 2) Pour la ligne « r », l'élément « c » sera le produit de « c-1 » et « c » le numéro de la ligne « r-1 ».
Étape 3) Le premier et le dernier nombre d’une rangée seront toujours « 1 ».
Nous devons respecter ces trois étapes simples pour créer le triangle de Pascal.
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 a été utilisé dans la mise en œuvre. Étant donné que N est le nombre de lignes du triangle de Pascal. Cela nécessitera N2 espaces unitaires. Par conséquent, O sera la complexité spatiale (N2).
Nous avons deux boucles dans la fonction, et chaque boucle s'exécute « N » fois. Ainsi, la complexité temporelle est également SUR2) ou complexité temporelle au carré.
Méthode 2 : Construire le triangle de Pascal en calculant le coefficient binomial
Nous pouvons simplement déduire les nombres du triangle de Pascal en utilisant le coefficient binomial. Voici le schéma :
Voici les étapes pour construire le Triangle de Pascal en calculant le Binôme :
Étape 1) La ligne la plus haute sera C(0,0). En utilisant la formule ci-dessus pour le coefficient binomial, C(0,0) = 1. Parce que 0 ! = 1.
Étape 2) Pour la ligne « i », il y aura un total d'éléments « i ». Chaque élément sera calculé C(n,r) où n sera i-1.
Étape 3) Répétez l'étape 2 pour le nombre de lignes souhaitées pour le triangle de Pascal.
C++ Triangle de Code 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 Triangle de Code 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é
Trois boucles ont été utilisées dans la mise en œuvre. Une boucle sert à calculer le coefficient binomial et les deux autres servent à créer des nombres pour toutes les lignes. Concernant le nombre de lignes, nous avons trois boucles qui s'exécutent « n » fois. Par conséquent, la complexité temporelle globale sera 0(n3).
La complexité spatiale est désormais constante car nous ne conservons aucune donnée en stockage. Le programme calcule l'élément et il est imprimé dans une ligne. La complexité spatiale diminue alors jusqu'à 0(1).
Méthode 3 : Construire le triangle de Pascal par le coefficient binomial modifié
Dans la technique précédente, nous avons déjà vu comment utiliser un coefficient binomial pour calculer chaque élément du triangle de Pascal. Cette approche déterminera C(n,r) à partir de C. (n, r-1). Cela simplifiera les choses d'une seule commande.
Voici les étapes à suivre pour construire le triangle de Pascal par coefficient binomial modifié :
Étape 1) Commencez la première ligne avec « 1 »
Étape 2) Calculez C(n,r), où « n » est le numéro de ligne et « r » est la colonne ou l'élément. Attribuez la valeur dans une variable C.
Étape 3) Pour calculer C(n,k), ce sera C*(nk)/k. Maintenant, attribuez cette valeur à C.
Étape 4) Continuez l'étape 3 jusqu'à ce que « k » atteigne la fin de la rangée. Après chaque itération, incrémentez la valeur de 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 comporte deux boucles. Chaque boucle s'exécute au maximum pendant « n », où « n » désigne le nombre de lignes du triangle pascal. La complexité temporelle est donc Sur2), au carré du temps.
Concernant la complexité de l'espace, nous n'avions besoin d'aucun tableau à stocker. Nous avons simplement utilisé une variable pour conserver le coefficient binomial précédent. Nous avions donc juste besoin d’un espace supplémentaire. La complexité de l'espace est devenue O (1).
Application du triangle de Pascal
Voici quelques applications du Triangle de Pascal :
Expansions binomiales : Nous pouvons déterminer le coefficient des développements binomiaux à partir du triangle de Pascal. Voici un exemple :
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2et + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3et + 6x2y2 + 4xy3 + 1y4 |
Calcul des combinaisons : Nous avons vu que les éléments du triangle de Pascal sont équivalents aux coefficients binomiaux. Par exemple, si vous avez 6 balles et qu'on vous demande d'en choisir 3, ce sera 6C3. Ou bien, vous pouvez trouver le nombre dans le 3ème élément de la 6ème rangée du triangle de Pascal.
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 la puissance 2.
- La somme diagonale des éléments des lignes génère la séquence de Fibonacci.
Résumé
- Le triangle de Pascal donne les coefficients des développements binomiaux.
- Chaque rangée du triangle de Pascal commence et se termine par « 1 ». Les valeurs intermédiaires sont la somme de deux éléments de la ligne précédente.
- L'addition diagonale de tous les éléments du triangle de Pascal vous donnera le Séquence de Fibonacci.
- Le triangle de Pascal peut également être généré avec des coefficients binomiaux.
