Formula Triunghiului lui Pascal cu Exemple

Ce este triunghiul lui Pascal?

Triunghiul lui Pascal este un tablou triunghiular de numere care urmează un model simplu bazat pe rândul de deasupra. A fost popularizat de matematicianul francez Blaise Pascal în secolul al XVII-lea. Triunghiul începe cu un singur „1” în partea de sus, iar fiecare rând ulterior începe și se termină tot cu „1”.

Dincolo de forma sa elegantă, Triunghiul lui Pascal codifică relații matematice profunde. Este strâns legat de teorema binomială, numărătoarea combinatorie și probabilitatea, motiv pentru care apare în clasele de algebră, statistică și informatică din întreaga lume.

Istoria triunghiului lui Pascal

Deși numit după Blaise Pascal, triunghiul îl precede cu secole. Textul matematic chinezesc „Cele nouă capitole despre arta matematică” conține unul dintre cele mai vechi exemple cunoscute, prezentând multe dintre aceleași modele pe care le folosim și astăzi.

Matematicianul persan Al-Karaji și savantul indian PingAla a explorat și el tablouri similare. Pascal a formalizat proprietățile triunghiului în tratatul său din 1654 „Traité du triangle arithmétique”, care a dat structurii denumirea modernă în matematica occidentală.

Construcția triunghiului lui Pascal

Construirea Triunghiului lui Pascal este simplă. Singura regulă de reținut este că fiecare rând începe și se termină cu 1, iar fiecare alt număr este construit pornind de la rândul de mai sus.

Pentru orice rând r și coloană c, valoarea este egală cu suma numerelor din coloanele c-1 și c ale rândului r-1.

Aici,

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

Iată pașii pentru construirea Triunghiului lui Pascal:

Pas 1) Începeți prin a completa primele două rânduri.

Pas 2) Al doilea element al celui de-al treilea rând este suma primului și celui de-al doilea număr din al doilea rând.

Pas 3) Al patrulea rând începe cu „1”. Al doilea număr este 3, care este suma dintre 1 și 2 (evidențiat cu albastru).

Imaginea de mai jos arată cum se completează al patrulea rând:

Pas 4) Al cincilea rând este format din cinci numere. Știm deja modelul de populare a rândurilor din pașii anteriori.

Formula triunghiului lui Pascal – Coeficient binomial

Un coeficient binomial numără modalitățile de a alege un subset de k elemente dintr-o colecție de n elemente. Se scrie de obicei ca „C(n, k)” sau „n aleg k”.

Coeficientul binomial este definit ca:

Simbolul „!” indică factorialul unui număr.

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

De exemplu,

5! = 5.4.3.2.1

= 120

Deci, C(5, 3) sau „5 alege 3” = 5! / 3!(5-3)!

= 120 / 12

= 10

Metoda 1: Construirea triunghiului lui Pascal prin rândul anterior

Procedura de aici reflectă modul în care am desenat triunghiul manual. Să presupunem că vrem să generăm triunghiul lui Pascal cu până la șapte rânduri.

Pașii pentru a face acest lucru sunt următorii:

Pas 1) Începeți rândul de sus cu „1”.

Pas 2) Pentru rândul „r”, elementul „c” va fi suma dintre coloana „c-1” și coloana „c” a rândului „r-1”.

Pas 3) Primul și ultimul număr din fiecare rând vor fi întotdeauna „1”.

Urmând acești trei pași simpli, putem construi sistematic întregul triunghi.

C++ Code a triunghiului lui Pascal de rândul anterior

#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);
}

ieșire:

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 Formula Triunghiului Pascal după rândul anterior

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)

Triunghiul lui Pascal Exemplu de ieșire:

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

Analiza complexității

A matrice bidimensională este utilizat în această implementare. Având în vedere că N este numărul de rânduri din triunghiul lui Pascal, acest lucru necesită N² spații unitare. Prin urmare, complexitatea spațiului este O(N²).

Funcția folosește două bucle imbricate, fiecare rulând de până la „N” ori. Deci, complexitatea temporală este, de asemenea, PE²)sau complexitatea timpului la pătrat.

Metoda 2: Construirea triunghiului lui Pascal prin calcularea coeficientului binomial

Putem obține numerele triunghiului lui Pascal direct folosind coeficienți binomiali. Diagrama de mai jos ilustrează relația:

Iată pașii pentru construirea triunghiului lui Pascal prin calcularea coeficientului binomial:

Pas 1) Rândul de sus este C(0, 0). Folosind formula de mai sus, C(0, 0) = 1, deoarece 0! = 1.

Pas 2) Pentru rândul „i”, va exista un total de „i” elemente. Fiecare element este calculat ca C(n, r), unde n este i-1.

Pas 3) Repetați pasul 2 pentru oricâte rânduri ale triunghiului lui Pascal doriți să generați.

C++ Code Triunghiul lui Pascal prin coeficientul 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);
}

ieșire:

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 Triunghiul lui Pascal prin coeficientul 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)

Triunghiul lui Pascal Exemplu de ieșire:

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

Analiza complexității

În această implementare se utilizează trei bucle: una pentru calcularea coeficientului binomial și încă două pentru iterarea prin fiecare rând și coloană. În ceea ce privește numărul de rânduri, toate cele trei bucle se execută de până la „n” ori. Prin urmare, complexitatea totală în timp este O(n³).

Complexitatea spațiului este constantă deoarece nu stocăm niciun rezultat intermediar. Programul calculează fiecare element din mers și îl afișează într-un rând, astfel încât complexitatea spațiului se reduce la O (1).

Metoda 3: Construirea triunghiului lui Pascal prin coeficient binomial modificat

În tehnica anterioară, am folosit formula coeficientului binomial pentru a calcula fiecare element. Abordarea modificată derivă C(n, r) direct din C(n, r-1), reducând lucrul mecanic cu un ordin de mărime.

Iată pașii pentru construirea Triunghiului lui Pascal folosind coeficientul binomial modificat:

Pas 1) Începeți primul rând cu „1”.

Pas 2) Calculați C(n, r), unde „n” este numărul rândului și „r” este indicele coloanei. Atribuiți această valoare unei variabile C.

Pas 3) Pentru calcularea următorului coeficient, se folosește C * (n – k) / k. Se atribuie această nouă valoare înapoi lui C.

Pas 4) Continuați pasul 3 până când „k” ajunge la sfârșitul rândului. După fiecare iterație, incrementați k cu unu.

C++ Code pentru Triunghiul lui Pascal prin Coeficient Binomial Modificat

#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);
}

ieșire:

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

Python Code pentru Triunghiul lui Pascal prin Coeficient Binomial Modificat

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)

Ieșire modele triunghiulare a lui Pascal:

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

Analiza complexității

Implementarea folosește două bucle, fiecare rulând de maximum „n” ori, unde „n” este numărul de rânduri din triunghi. Deci, complexitatea temporală este Pe²), timp la pătrat.

În ceea ce privește complexitatea spațiului, nu avem nevoie de niciun tablou pentru stocare. Folosim o singură variabilă pentru a păstra coeficientul binomial anterior, deci avem nevoie doar de un spațiu suplimentar. Complexitatea spațiului este, prin urmare, O (1).

Aplicarea triunghiului lui Pascal

Iată câteva aplicații practice ale triunghiului lui Pascal:

Expansiuni binomiale: Coeficienții oricărei expansiuni binomiale pot fi citiți direct din triunghiul lui Pascal. Iată un exemplu:

Calcularea combinațiilor: Elementele triunghiului lui Pascal corespund direct coeficienților binomiali. De exemplu, dacă aveți 6 bile și doriți să alegeți 3, răspunsul este ⁶C₃Puteți găsi acea valoare în al treilea element al celui de-al șaselea rând al triunghiului lui Pascal.

Probabilitate: Triunghiul lui Pascal este utilizat pe scară largă pentru a calcula probabilitățile în aruncările de monede, problemele cu zarurile și alte evenimente combinatorii în care fiecare rezultat corespunde unei distribuții binomiale.

Fapte interesante despre triunghiul lui Pascal

Iată câteva fapte pe care le veți găsi interesante despre triunghiul lui Pascal:

• Suma tuturor elementelor dintr-un rând este întotdeauna o putere a lui 2.

• Sumele diagonale ale rândurilor generează șirul lui Fibonacci.

• Fiecare rând corespunde coeficienților din dezvoltarea lui (a+b)ⁿ.
• Dacă umbrați doar numerele impare, figura rezultată formează fractalul triunghiului Sierpinski.

Întrebări frecvente