Pascalin kolmio – kaava, kuviot ja esimerkit

Mikä on Pascalin kolmio?

Pascalin kolmio on kolmion muotoinen joukko numeroita, joita seuraa tietty kuvio ja yhteys sitä edeltävään riviin. Sen keksi Blaise Pascal. Tämä kolmio alkaa yhdellä elementillä ensimmäisellä rivillä. Sen jälkeen jokainen rivi alkaa ja päättyy numeroon 1.

Pascalin kolmio

Pascalin kolmion historia

Kiinalainen kirja "The Nine Chapters on the Mathematical Art" sisältää yhden ensimmäisistä esimerkeistä Pascalin kolmiosta. Lisäksi se sisältää joitain samoja kuvioita ja ominaisuuksia, joita löytyy nykyään kolmioista.

Pascal oli yksi monista ihmisistä Euroopassa, joka tutki kolmiota. Muut matemaatikot olivat tutkineet samanlaisia ​​kolmiomaisia ​​lukujonoja ennen häntä.

Pascalin kolmion rakentaminen

Pascalin kolmion rakentaminen on yksinkertaista. Ainoa asia, joka sinun on muistettava, on, että rivi alkaa ja päättyy numeroon 1. Muiden numeroiden sääntö on seuraava:

Minkä tahansa rivin r ja sarakkeen c luku on rivin r-1 sarakkeiden c-1 ja c summa.

Täällä

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

Tässä on vaiheet Pascalin kolmion rakentamiseen:

Vaihe 1) Aloitetaan täyttämällä kaksi riviä.

Pascalin kolmion rakentaminen

Vaihe 2) Kolmannen rivin toinen elementti on toisen rivin ensimmäisen ja toisen numeron summa.

Pascalin kolmion rakentaminen

Vaihe 3) Neljäs rivi alkaa kirjaimella "1.". Toinen luku on 3, joka on 1:n ja 2:n summa (korostettu sinisellä).

Alla oleva kuva näyttää, kuinka neljäs rivi täytetään:

Pascalin kolmion rakentaminen

Vaihe 4) Viides rivi koostuu viidestä numerosta. Tiedämme jo mallin rivien täyttämiseksi aikaisemmista vaiheista.

Pascalin kolmion rakentaminen

Pascalin kolmiokaava – binomiaalinen kerroin

Binomikerroin on luku, joka ilmaisee eri menetelmiä k elementin osajoukon valitsemiseksi n elementin joukosta. Usein se kirjoitetaan "C(n,k)" tai "n valitse k".

Binomikerroin määritellään seuraavasti

Pascalin kolmiokaava – binomiaalinen kerroin

"!" tarkoittaa "tekijää".

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

Esimerkiksi

5! = 5.4.3.2.1

= 120

Sanotaan siis, että C(5,3) tai 5 valitse 3 = 5! / 3!(5-3)!

= 120/(12)

= 10

Tapa 1: Rakenna Pascalin kolmio edellisen rivin mukaan

Tämän menettelyn vaiheet ovat samat kuin Pascalin kolmiossa. Oletetaan, että haluamme luoda Pascalin kolmion, jossa on enintään seitsemän riviä.

Toimenpiteet sen suorittamiseksi ovat seuraavat:

Vaihe 1) Aloita ylin rivi numerolla 1.

Vaihe 2) Rivin "r" kohta "c" on "c-1":n ja "r-1"-rivin numeron "c" tulo.

Vaihe 3) Ensimmäinen ja viimeinen numero rivissä ovat aina "1".

Meidän on noudatettava näitä kolmea helppoa vaihetta Pascalin kolmion luomiseksi.

C++ Pascalin kolmion koodi edellisellä rivillä

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

lähtö:

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 Pascal-kolmiokaavan koodi edellisellä rivillä

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)

Pascalin kolmion esimerkkitulos:

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

Monimutkaisuusanalyysi

A kaksiulotteinen matriisi käytettiin toteutuksessa. Koska N on Pascalin kolmion rivien lukumäärä. Tämä vaatii N2 yksikkötilat. Siksi O on avaruuden kompleksisuus (N2).

Meillä on kaksi silmukkaa funktiossa, ja jokainen silmukka toimii "N" kertaa. Joten, aika monimutkaisuus on myös PÄÄLLÄ2) tai neliöity aika monimutkaisuus.

Menetelmä 2: Pascalin kolmion rakentaminen laskemalla binomiaalinen kerroin

Voimme yksinkertaisesti johtaa Pascalin kolmion luvut käyttämällä binomikerrointa. Tässä kaavio:

Pascalin kolmion rakentaminen laskemalla binomiaalinen kerroin

Tässä on vaiheet Pascalin kolmion rakentamiseksi laskemalla binomiaali:

Vaihe 1) Ylin rivi on C(0,0). Käyttämällä yllä olevaa kaavaa binomikertoimelle C(0,0) = 1. Koska 0! = 1.

Vaihe 2) Rivillä "i" on yhteensä "i"-elementtejä. Jokainen kohde lasketaan C(n,r), jossa n on i-1.

Vaihe 3) Toista vaihe 2 Pascalin kolmion rivien lukumäärälle.

C++ Koodaa Pascalin kolmio binomiaalisella kertoimella

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

lähtö:

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 Koodaa Pascalin kolmio binomiaalisella kertoimella

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)

Pascalin kolmion esimerkkitulos:

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

Monimutkaisuusanalyysi

Toteutuksessa käytettiin kolmea silmukkaa. Yksi silmukka on binomikertoimen laskemiseen ja kaksi muuta on tarkoitettu lukujen luomiseen kaikille riveille. Mitä tulee rivien määrään, meillä on kolme silmukkaa, jotka suoritetaan "n" kertaa. Näin ollen kokonaisaika monimutkaisuus on 0 (n3).

Tilan monimutkaisuus on nyt jatkuvaa, koska emme säilytä mitään tietoja tallennustilassa. Ohjelma laskee elementin ja tulostaa sen riville. Avaruuden monimutkaisuus pienenee sitten arvoon 0(1).

Menetelmä 3: Pascalin kolmion rakentaminen modifioidulla binomikertoimella

Edellisessä tekniikassa olemme jo nähneet kuinka käyttää binomikerrointa Pascalin kolmion jokaisen elementin laskemiseen. Tämä lähestymistapa määrittää C(n,r):n arvosta C. (n, r-1). Se yksinkertaistaa asioita yhdellä tilauksella.

Tässä on vaiheet Pascalin kolmion rakentamiseksi modifioidulla binomikertoimella:

Vaihe 1) Aloita ensimmäinen rivi numerolla 1

Vaihe 2) Laske C(n,r), jossa "n" on rivin numero ja "r" on sarake tai elementti. Anna arvo muuttujassa C.

Vaihe 3) Laskettaessa C(n,k) se on C*(nk)/k. Määritä nyt tämä arvo C:lle.

Vaihe 4) Jatka vaihetta 3, kunnes "k" saavuttaa rivin lopun. Kasvata K:n arvoa jokaisen iteraation jälkeen yhdellä.

C++ Pascalin kolmion koodi modifioidulla binomiaalisella kertoimella

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

lähtö:

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

Python Pascalin kolmion koodi modifioidulla binomiaalisella kertoimella

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)

Pascalin kolmiomallien lähtö:

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

Monimutkaisuusanalyysi

Toteutuksessa on kaksi silmukkaa. Jokainen silmukka kulkee enintään "n" ajan, jossa "n" tarkoittaa pascal-kolmion rivien määrää. Aika monimutkaisuus on siis Päällä2), neliöity aika.

Mitä tulee tilan monimutkaisuuteen, emme tarvinneet mitään taulukkoa tallennettavaksi. Käytimme vain yhtä muuttujaa säilyttääksemme edellisen binomikertoimen. Joten tarvitsimme vain yhden lisätilan. Tilan monimutkaisuus muuttui O (1).

Pascalin kolmion soveltaminen

Tässä on joitain Pascalin kolmion sovelluksia:

Binomilaajennukset: Voimme määrittää binomilaajennusten kertoimen Pascalin kolmiosta. Tässä on esimerkki:

(x + y)0 1
(x + y)1 1.x + 1.y
(x + y)2 1x2 + 2xy + 1y2
(x + y)3 1x3 + 3x2ja + 3xy2 + 1y3
(x + y)4 1x4 + 4x3ja + 6x2y2 + 4xy3 + 1y4

Yhdistelmien laskeminen: Olemme nähneet, että Pascalin kolmion elementit vastaavat binomiaalikertoimia. Jos sinulla on esimerkiksi 6 palloa ja sinua on pyydetty valitsemaan 3 palloa, niin se on 6C3. Tai voit löytää numeron Pascalin kolmion 3. rivin 6. elementistä.

Mielenkiintoisia faktoja Pascalin kolmiosta

Tässä on joitain mielenkiintoisia faktoja Pascalin kolmiosta:

  • Kaikkien rivin elementtien summa on aina 2:n potenssi.

Faktaa Pascalin kolmiosta

  • Rivien elementtien diagonaalinen summa muodostaa Fibonacci-sekvenssin.

Faktaa Pascalin kolmiosta

Yhteenveto

  • Pascalin kolmio antaa kertoimet binomilaajennuksille.
  • Jokainen Pascalin kolmion rivi alkaa ja päättyy numeroon 1. Väliarvot ovat edellisen rivin kahden elementin summa.
  • Kaikkien Pascalin kolmion elementtien diagonaalinen lisääminen antaa sinulle Fibonacci-sekvenssi.
  • Pascalin kolmio voidaan generoida myös binomiaalisilla kertoimilla.