Pascal-háromszög – képlet, minták és példák
Sarah Chen
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ö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.
Step 2) A harmadik sor második eleme a második sor első és második számának összege.
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:
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 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
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:
Í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.
- A sorok elemeinek átlós összege generálja a Fibonacci sorozatot.
Ö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ó.