Pascal-háromszög képlete példákkal

Mi az a Pascal-háromszög?

A Pascal-háromszög egy háromszög alakú számelrendezés, amely a felette lévő sor alapján egy egyszerű mintát követ. A háromszöget a francia matematikus, Blaise Pascal tette népszerűvé a 17. században. A háromszög egyetlen „1”-gyel kezdődik felül, és minden további sor szintén „1”-gyel kezdődik és végződik.

Elegáns alakján túl a Pascal-háromszög mély matematikai összefüggéseket kódol. Szorosan kapcsolódik a binomiális tételhez, a kombinatorikus számláláshoz és a valószínűségszámításhoz, ezért jelenik meg világszerte az algebra, a statisztika és a számítástechnika tantermeiben.

Pascal háromszög története

Bár a háromszög Blaise Pascalról kapta a nevét, évszázadokkal megelőzi őt. A „Kilenc fejezet a matematika művészetéről” című kínai matematikai szöveg tartalmazza az egyik legkorábbi ismert példát, amely számos olyan mintát mutat, amelyeket ma is használunk.

Al-Karadzsi perzsa matematikus és indiai tudós Pingala is hasonló tömböket vizsgált. Pascal formalizálta a háromszög tulajdonságait 1654-es „Traité du triangle arithmétique” című értekezésében, amely a struktúrának a nyugati matematikában a modern nevét adta.

Pascal-háromszög felépítése

A Pascal-háromszög felépítése egyszerű. Az egyetlen szabály, amire emlékezni kell, hogy minden sor 1-gyel kezdődik és végződik, és minden más szám a felette lévő sorból épül fel.

Bármely r sor és c oszlop esetén az érték megegyezik az r-1 sor c-1 és c oszlopaiban lévő számok összegével.

Itt,

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

A Pascal-háromszög felépítésének lépései a következők:

Step 1) Kezdjük az első két sor kitöltésével.

Step 2) A harmadik sor második eleme a második sorban szereplő első és második szám összege.

Step 3) A negyedik sor „1”-gyel kezdődik. A második szám a 3, ami az 1 és a 2 összege (kékkel kiemelve).

Az alábbi képen látható, hogyan kell kitölteni a negyedik sort:

Step 4) Az ötödik sor öt számból áll. A sorok feltöltésének mintáját már ismerjük a korábbi lépésekből.

Pascal-háromszög képlet – Binomiális együttható

A binomiális együttható azt számolja, hogy n elemből álló halmazból hányféleképpen lehet k elemből álló részhalmazt kiválasztani. Általában „C(n, k)” vagy „n választ k” formában írják.

A binomiális együtthatót a következőképpen definiáljuk:

A „!” szimbólum egy szám faktoriálisát jelöli.

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

Például,

5! = 5.4.3.2.1

= 120

Tehát C(5, 3), vagyis „5-ből 3-at választunk” = 5! / 3!(5-3)!

= 120/12

= 10

1. módszer: Pascal-háromszög felépítése az előző sor alapján

Az eljárás itt a háromszög manuális rajzolásához hasonló. Tegyük fel, hogy legfeljebb hét soros Pascal-háromszöget szeretnénk létrehozni.

A lépések a következők:

Step 1) A legfelső sort az „1”-essel kezdje.

Step 2) Az „r” sor „c” eleme a „c-1” oszlop és az „r-1” sor „c” oszlopának összege lesz.

Step 3) Minden sorban az első és az utolsó szám mindig „1” lesz.

Ezt a három egyszerű lépést követve szisztematikusan megépíthetjük a teljes háromszöget.

C++ Code Pascal-háromszög előző sorral

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

output:

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 a Pascal-háromszög képletének előző sora

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)

Pascal-háromszög példa kimenet:

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

Komplexitás elemzése

A kétdimenziós tömb ebben a megvalósításban használjuk. Tekintettel arra, hogy N a Pascal-háromszög sorainak száma, ehhez N szükséges.² egységterek. Ezért a térbonyolultság O(N²).

A függvény két egymásba ágyazott ciklust használ, amelyek mindegyike „N” alkalommal fut. Tehát az időbonyolultság is TOVÁBB²), vagy négyzetes időbonyolultság.

2. módszer: Pascal-háromszög felépítése binomiális együttható kiszámításával

A Pascal-háromszög számait közvetlenül levezethetjük binomiális együtthatók segítségével. Az alábbi ábra szemlélteti az összefüggést:

A Pascal-háromszög felépítésének lépései a binomiális együttható kiszámításával:

Step 1) A legfelső sor a C(0, 0). A fenti képlet alapján C(0, 0) = 1, mert 0! = 1.

Step 2) Az „i” sorban összesen „i” elem lesz. Minden elem C(n, r) képlettel számítható ki, ahol n az i-1.

Step 3) Ismételd meg a 2. lépést annyi Pascal-háromszög sorral, ahányat szeretnél generálni.

C++ Code Pascal-háromszög binomiális együtthatóval

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

output:

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 Pascal-háromszög binomiális együtthatóval

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)

Pascal-háromszög példa kimenet:

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

Komplexitás elemzése

Ebben a megvalósításban három ciklust használunk: egyet a binomiális együttható kiszámításához, kettőt pedig minden sor és oszlop végigfutásához. A sorok számát tekintve mindhárom ciklus „n”-szer fut le. Következésképpen az összesített időbonyolultság O(n³).

A térbeli komplexitás állandó, mivel nem tárolunk semmilyen köztes eredményt. A program menet közben kiszámítja az egyes elemeket, és egy soron belül kiírja azokat, így a térbeli komplexitás erre csökken: O (1).

3. módszer: Pascal-háromszög felépítése módosított binomiális együtthatóval

Az előző technikában a binomiális együttható képletét használtuk az egyes elemek kiszámításához. A módosított megközelítés a C(n, r)-t közvetlenül a C(n, r-1)-ből származtatja, így a munka egy nagyságrenddel csökken.

A módosított binomiális együtthatóval a Pascal-háromszög felépítésének lépései a következők:

Step 1) Az első sort „1”-gyel kezdd.

Step 2) Számítsd ki a C(n, r) értékét, ahol „n” a sorszám, „r” pedig az oszlopindex. Rendeld ezt az értéket egy C változóhoz.

Step 3) A következő együttható kiszámításához használd a C * (n – k) / k képletet. Rendeld vissza ezt az új értéket C-hez.

Step 4) Folytasd a 3. lépést, amíg a „k” el nem éri a sor végét. Minden iteráció után növeld k értékét eggyel.

C++ Code Pascal-háromszögre módosított binomiális együtthatóval

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

output:

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

Python Code Pascal-háromszögre módosított binomiális együtthatóval

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)

Pascal-háromszög minták kimenete:

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

Komplexitás elemzése

A megvalósítás két ciklust használ, amelyek mindegyike maximum „n” alkalommal fut, ahol „n” a háromszögben lévő sorok száma. Tehát az időbonyolultság: Tovább²), négyzetes idő.

A térbeli bonyolultságot tekintve nincs szükségünk tömbre a tároláshoz. Csak egy változót használunk az előző binomiális együttható megtartásához, tehát csak egy plusz helyre van szükségünk. A térbeli bonyolultság tehát: O (1).

Pascal-háromszög alkalmazása

Íme a Pascal-háromszög néhány gyakorlati alkalmazása:

Binomiális bővítések: Bármely binomiális kiterjesztés együtthatói közvetlenül leolvashatók Pascal-háromszögből. Íme egy példa:

Kombinációk számítása: A Pascal-háromszög elemei közvetlenül megfeleltethetők a binomiális együtthatóknak. Például, ha 6 golyód van és 3-at szeretnél választani, a válasz: ⁶C₃Ezt az értéket a Pascal-háromszög 6. sorának 3. elemében találod.

Valószínűség: A Pascal-háromszöget széles körben használják valószínűségek kiszámítására érmefeldobásokban, kockafeladatokban és más kombinatorikus eseményekben, ahol minden kimenetel egy binomiális eloszlásnak felel meg.

Érdekes tények Pascal háromszögéről

Íme néhány érdekes tény a Pascal-háromszögről:

• Bármely sorban az összes elem összege mindig a 2 hatványa.

• A sorok átlóösszegei generálják a Fibonacci-sorozatot.

• Minden sor az (a+b) kiterjesztésben szereplő együtthatóknak felel megⁿ.
• Ha csak a páratlan számokat satírozzuk be, a kapott ábra a Sierpinski-háromszög fraktálját alkotja.

GYIK