Pascal-háromszög – képlet, minták és példák

Mi az a Pascal-háromszög?

A Pascal-háromszög egy háromszög alakú számtömb, amelyet egy adott minta követ, és az előtte lévő sorhoz kapcsolódik. Blaise Pascal találta fel. Ez a háromszög az első sor egy elemével kezdődik. Ezt követően minden sor „1”-el kezdődik és végződik.

Pascal háromszöge

Pascal háromszög története

A „Kilenc fejezet a matematikai művészetről” című kínai könyv tartalmazza a Pascal-háromszög egyik első példáját. Ezenkívül ugyanazokat a mintákat és tulajdonságokat tartalmazza, amelyek ma a háromszögekben találhatók.

Pascal egyike volt azoknak Európában, akik tanulmányozták a háromszöget. Más matematikusok is megvizsgálták előtte hasonló háromszög alakú számtömböket.

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

A Pascal-háromszög megalkotása egyszerű. Az egyetlen dolog, amit emlékezned kell, hogy a sor 1-gyel kezdődik és végződik. A többi szám szabálya a következő:

Bármely r sor és c oszlop esetén a szám az r-1 sor c-1 és c oszlopának összege lesz.

Itt,

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

Íme a lépések a Pascal-háromszög létrehozásához:

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

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

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

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

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

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

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

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

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

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

A binomiális együttható olyan szám, amely különböző módszereket fejez ki egy k elemből álló részhalmaz kiválasztására n elemből álló gyűjteményből. Gyakran úgy írják, hogy „C(n,k)” vagy „n válasszuk k”.

A binomiális együtthatót a következőképpen határozzuk meg

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

A "!" a „tényezőt” jelöli.

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

Például,

5! = 5.4.3.2.1

= 120

Tehát mondjuk C(5,3) vagy 5 válassza ki a 3 = 5-öt! / 3!(5-3)!

= 120/(12)

= 10

1. módszer: Pascal háromszögének felépítése az előző sorból

Az eljárás lépései ugyanazok, mint a Pascal-háromszögben. Tegyük fel, hogy Pascal háromszögét akarjuk létrehozni legfeljebb hét sorból.

Ennek lépései a következők:

Step 1) Kezdje a legfelső sort „1”-el.

Step 2) Az „r” sorban a „c” tétel „c-1” és „c” az „r-1” sor számának szorzata lesz.

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

Ezt a három egyszerű lépést be kell tartanunk a Pascal-háromszög létrehozásához.

C++ Pascal-háromszög kódja az előző sor szerint

#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 Pascal háromszög képlet kódja az előző sor szerint

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 a megvalósítás során használták. Tekintettel arra, hogy N a Pascal-háromszög sorainak száma. Ehhez szükség lesz N2 egységterek. Ezért O lesz a tér összetettsége (N2).

A függvényben két ciklus van, és mindegyik ciklus „N”-ig fut. Tehát az idő bonyolultsága is TOVÁBB2) 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

Egyszerűen levezethetjük a Pascal-háromszög számait a binomiális együttható segítségével. Íme a diagram:

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

Íme a lépések a Pascal-háromszög felépítéséhez a binomiális kiszámításával:

Step 1) A legfelső sor C(0,0) lesz. A fenti képletet használva a binomiális együtthatóhoz C(0,0) = 1. Mert 0! = 1.

Step 2) Az „i” sorban összesen „i” elem lesz. Minden elem kiszámítása C(n,r) lesz, ahol n értéke i-1.

Step 3) Ismételje meg a 2. lépést a Pascal-háromszöghez kívánt sorok számához.

C++ Kódolja a Pascal-háromszöget 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 Kódolja a Pascal-háromszöget 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

A megvalósítás során három hurkot használtak. Az egyik ciklus a binomiális együttható kiszámítására szolgál, a másik kettő pedig az összes sorhoz tartozó számok létrehozására. A sorok számát illetően három ciklusunk van, amelyek „n”-szer hajtódnak végre. Következésképpen a teljes időbonyolultság 0 (n3).

A tér összetettsége most állandó, mert nem tárolunk semmilyen adatot a tárhelyen. A program kiszámítja az elemet, és sorban kinyomtatja. A tér összetettsége ezután 0-ra (1) csökken.

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

Az előző technikában már láttuk, hogyan lehet binomiális együtthatót használni a Pascal-háromszög egyes elemeinek kiszámításához. Ez a megközelítés meghatározza a C(n,r)-t a C-ből (n,r-1). Egy rendeléssel leegyszerűsíti a dolgokat.

Íme, a Pascal-háromszög módosított binomiális együtthatóval történő felépítésének lépései:

Step 1) Kezdje az első sort „1”-el

Step 2) Számítsa ki C(n,r), ahol „n” a sor száma, „r” pedig az oszlop vagy az elem. Adja hozzá az értéket egy C változóban.

Step 3) A C(n,k) kiszámításához C*(nk)/k lesz. Most rendelje hozzá ezt az értéket C-hez.

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

C++ Pascal-háromszög kódja 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 Pascal-háromszög kódja 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 hurokból áll. Minden ciklus legfeljebb „n” ideig fut, ahol az „n” a pascal háromszög sorainak számát jelenti. Tehát az idő bonyolultsága Tovább2), négyzetes idő.

Ami a tér összetettségét illeti, nem volt szükségünk semmilyen tömbre a tároláshoz. Csak egy változót használtunk, hogy megtartsuk az előző binomiális együtthatót. Tehát csak egy plusz helyre volt szükségünk. A tér összetettsége lett O (1).

Pascal-háromszög alkalmazása

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

Binomiális bővítések: A Pascal-háromszögből meg tudjuk határozni a binomiális bővítések együtthatóját. Íme egy példa:

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

Kombinációk számítása: Láttuk, hogy a Pascal-háromszög elemei ekvivalensek a binomiális együtthatókkal. Például, ha van 6 labdája, és megkérik, hogy válasszon 3 labdát, akkor az lesz 6C3. Vagy megtalálhatja a számot a Pascal-háromszög 3. sorának 6. elemében.

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

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

  • A sorban lévő összes elem összege mindig 2 hatványa.

Tények Pascal háromszögéről

  • A sorok elemeinek átlós összege generálja a Fibonacci sorozatot.

Tények Pascal háromszögéről

Összegzésként

  • A Pascal-háromszög megadja a binomiális kiterjesztések együtthatóit.
  • A Pascal-háromszög minden sora 1-gyel kezdődik és végződik. A köztes értékek az előző sor két elemének összege.
  • A Pascal-háromszög összes elemének átlós összeadása megadja a Fibonacci szekvencia.
  • A Pascal-háromszög binomiális együtthatókkal is előállítható.