Pascalin kolmion kaava esimerkkeineen

Mikä on Pascalin kolmio?

Pascalin kolmio on kolmionmuotoinen numerotaulukko, joka noudattaa yksinkertaista kaavaa yläpuolella olevan rivin perusteella. Ranskalainen matemaatikko Blaise Pascal teki sen tunnetuksi 17-luvulla. Kolmio alkaa yhdellä numerolla "1" yläreunassa, ja jokainen seuraava rivi alkaa ja päättyy myös numeroon "1".

Elegantin muotonsa lisäksi Pascalin kolmio sisältää syviä matemaattisia yhteyksiä. Se on läheisesti sidoksissa binomilauseeseen, kombinatoriseen laskentaan ja todennäköisyyslaskentaan, minkä vuoksi sitä käytetään algebran, tilastotieteen ja tietojenkäsittelytieteen luokkahuoneissa maailmanlaajuisesti.

Pascalin kolmion historia

Vaikka kolmio on nimetty Blaise Pascalin mukaan, se on vuosisatoja vanhempi kuin hän. Kiinalainen matemaattinen teksti ”Yhdeksän lukua matemaattisesta taiteesta” sisältää yhden varhaisimmista tunnetuista esimerkeistä, ja se esittää monia samoja kuvioita, joita käytämme tänäkin päivänä.

Persialainen matemaatikko Al-Karaji ja intialainen oppinut Pingala tutki myös samankaltaisia ​​taulukoita. Pascal formalisoi kolmion ominaisuudet vuonna 1654 kirjoittamassaan tutkielmassa ”Traité du triangle arithmétique”, joka antoi rakenteelle sen nykyisen nimen länsimaisessa matematiikassa.

Pascalin kolmion rakentaminen

Pascalin kolmion muodostaminen on suoraviivaista. Ainoa muistettava sääntö on, että jokainen rivi alkaa ja päättyy lukuun 1, ja kaikki muut luvut muodostetaan sitä ylemmästä rivistä.

Minkä tahansa rivin r ja sarakkeen c arvo on yhtä suuri kuin rivin r-1 sarakkeiden c-1 ja c lukujen summa.

Täällä

• r = 3, 4, 5, …
• n ja c = 2, 3, 4, …, r⁻¹.

Tässä ovat vaiheet Pascalin kolmion rakentamiseksi:

Vaihe 1) Aloita täyttämällä kaksi ensimmäistä riviä.

Vaihe 2) Kolmannen rivin toinen alkio on toisen rivin ensimmäisen ja toisen luvun summa.

Vaihe 3) Neljäs rivi alkaa numerolla ”1”. Toinen luku on 3, joka on lukujen 1 ja 2 summa (korostettu sinisellä).

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

Vaihe 4) Viides rivi koostuu viidestä numerosta. Tiedämme jo rivien täyttämiskaavan aiemmista vaiheista.

Pascalin kolmiokaava – binomiaalinen kerroin

Binomikerroin laskee, kuinka monella tavalla n alkion joukosta voidaan valita k alkion osajoukko. Se kirjoitetaan yleensä muodossa ”C(n, k)” tai ”n valitsee k”.

Binomikerroin määritellään seuraavasti:

Symboli ”!” tarkoittaa luvun kertomaa.

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

Esimerkiksi

5! = 5.4.3.2.1

= 120

Joten C(5, 3) eli ”5 valitsee 3” = 5! / 3! (5 - 3)!

= 120/12

= 10

Menetelmä 1: Pascalin kolmion rakentaminen edellisen rivin avulla

Tässä menetelmässä piirsimme kolmion manuaalisesti. Oletetaan, että haluamme luoda Pascalin kolmion, jossa on enintään seitsemän riviä.

Toimi seuraavasti:

Vaihe 1) Aloita ylin rivi numerolla "1".

Vaihe 2) Rivillä ”r” elementti ”c” on rivin ”r-1” sarakkeen ”c-1” ja sarakkeen ”c” summa.

Vaihe 3) Kunkin rivin ensimmäinen ja viimeinen numero on aina "1".

Näitä kolmea yksinkertaista vaihetta noudattamalla voimme systemaattisesti rakentaa koko kolmion.

C++ Code Pascalin kolmion edellisen rivin kohdalla

#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 Code Pascal-kolmion kaavan edellisen rivin mukaan

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äytetään tässä toteutuksessa. Koska N on Pascalin kolmion rivien lukumäärä, tämä vaatii N:n² yksikköavaruudet. Siksi avaruuskompleksisuus on O(N²).

Funktio käyttää kahta sisäkkäistä silmukkaa, joita kumpaakin suoritetaan jopa N kertaa. Joten aikavaativuus on myös PÄÄLLIJ)tai neliöity aikakompleksisuus.

Menetelmä 2: Pascalin kolmion rakentaminen laskemalla binomikerroin

Voimme johtaa Pascalin kolmion luvut suoraan binomikertoimien avulla. Alla oleva kaavio havainnollistaa suhdetta:

Tässä ovat vaiheet Pascalin kolmion rakentamiseksi laskemalla binomikerroin:

Vaihe 1) Ylin rivi on C(0, 0). Yllä olevan kaavan avulla C(0, 0) = 1, koska 0! = 1.

Vaihe 2) Rivillä ”i” on yhteensä ”i” elementtiä. Jokainen elementti lasketaan muodossa C(n, r), jossa n on i-1.

Vaihe 3) Toista vaihe 2 niin monelle Pascalin kolmion riville kuin haluat luoda.

C++ Code Pascalin kolmio binomikertoimen avulla

#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 Code Pascalin kolmio binomikertoimen avulla

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

Tässä toteutuksessa käytetään kolmea silmukkaa: yksi binomikertoimen laskemiseen ja kaksi muuta jokaisen rivin ja sarakkeen läpikäymiseen. Rivien lukumäärän suhteen kaikki kolme silmukkaa suoritetaan jopa ”n” kertaa. Näin ollen kokonaisaikakompleksisuus on O(n³).

Tilakompleksisuus on vakio, koska emme tallenna mitään välituloksia. Ohjelma laskee jokaisen elementin lennossa ja tulostaa sen rivin sisällä, joten tilakompleksisuus pienenee muotoon O (1).

Menetelmä 3: Pascalin kolmion rakentaminen modifioidulla binomikertoimella

Edellisessä tekniikassa käytimme binomikertoimen kaavaa jokaisen elementin laskemiseen. Muokattu lähestymistapa johtaa C(n, r):n suoraan C(n, r-1):stä, mikä vähentää työtä yhdellä kertaluokalla.

Tässä ovat vaiheet Pascalin kolmion rakentamiseksi muokatun binomikertoimen avulla:

Vaihe 1) Aloita ensimmäinen rivi numerolla "1".

Vaihe 2) Laske C(n, r), jossa ”n” on rivinumero ja ”r” on sarakeindeksi. Anna tämä arvo muuttujalle C.

Vaihe 3) Seuraavan kertoimen laskemiseen käytä kaavaa C * (n – k) / k. Anna tämä uusi arvo takaisin C:lle.

Vaihe 4) Jatka vaihetta 3, kunnes ”k” saavuttaa rivin lopun. Jokaisen iteraation jälkeen lisää k:n arvoa yhdellä.

C++ Code Pascalin kolmiolle muokatulla binomikertoimella

#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 Code Pascalin kolmiolle muokatulla binomikertoimella

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 käytetään kahta silmukkaa, joita kumpaakin suoritetaan enintään ”n” kertaa, missä ”n” on kolmion rivien lukumäärä. Aikavaativuus on siis Päällä²), neliöity aika.

Tilakompleksisuuden osalta emme tarvitse tallennukseen taulukkoa. Käytämme vain yhtä muuttujaa säilyttääksemme edellisen binomikertoimen, joten tarvitsemme vain yhden ylimääräisen tilan. Tilakompleksisuus on siis O (1).

Pascalin kolmion soveltaminen

Tässä on joitakin Pascalin kolmion käytännön sovelluksia:

Binomilaajennukset: Minkä tahansa binomimallisen laajennuksen kertoimet voidaan lukea suoraan Pascalin kolmiosta. Tässä on esimerkki:

Yhdistelmien laskeminen: Pascalin kolmion alkiot vastaavat suoraan binomikertoimia. Esimerkiksi, jos sinulla on 6 palloa ja haluat valita 3, vastaus on ⁶C₃Löydät kyseisen arvon Pascalin kolmion kuudennen rivin kolmannesta elementistä.

Todennäköisyys: Pascalin kolmiota käytetään laajalti todennäköisyyksien laskemiseen kolikonheitoissa, noppaongelmissa ja muissa kombinatorisissa tapahtumissa, joissa jokainen tulos vastaa binomijakaumaa.

Mielenkiintoisia faktoja Pascalin kolmiosta

Tässä on joitain mielenkiintoisia faktoja Pascalin kolmiosta:

• Minkä tahansa rivin kaikkien alkioiden summa on aina kahden potenssi.

• Rivien diagonaalisummat muodostavat Fibonaccin jonon.

• Jokainen rivi vastaa kertoimia (a+b)-laajennuksessaⁿ.
• Jos varjostat vain parittomat luvut, tuloksena oleva luku muodostaa Sierpinskin kolmion fraktaalin.

UKK