Pascals triangel – formel, mönster och exempel
Sarah Chen
Vad är Pascals triangel?
Pascals triangel är en triangulär samling av tal följt av ett visst mönster och anslutning till raden före den. Den uppfanns av Blaise Pascal. Denna triangel börjar med ett element i den första raden. Därefter börjar och slutar varje rad med "1".
Pascals triangelhistoria
Den kinesiska boken "The Nine Chapters on the Mathematical Art" innehåller ett av de första exemplen på Pascals triangel. Dessutom innehåller den några av samma mönster och kvaliteter som finns i trianglar idag.
Pascal var en av flera personer i Europa som studerade triangeln. Andra matematiker hade undersökt liknande triangulära siffror före honom.
Konstruktion av Pascals triangel
Att konstruera Pascals triangel är enkelt. Det enda du behöver komma ihåg är att raden börjar och slutar med 1. Regeln för resten av siffrorna är följande:
För varje rad r och kolumn c kommer talet att vara summan av kolumnerna c-1 och c från rad r-1.
Här,
- r = 3,4,5….
- n och c = 2,3,4,...r-1.
Här är stegen för att bygga Pascals triangel:
Steg 1) Låt oss börja med att fylla två rader.
Steg 2) Det andra elementet för den tredje raden är summan av de första och andra talen i den andra raden.
Steg 3) Den fjärde raden börjar med "1". Det andra talet är 3, vilket är summan av 1 och 2 (markerat i blått).
Bilden nedan visar hur man fyller den fjärde raden:
Steg 4) Den femte raden kommer att bestå av fem nummer. Vi känner redan till mönstret för att fylla raderna från de tidigare stegen.
Pascals triangelformel – binomial koefficient
En binomial koefficient är ett tal som uttrycker olika metoder för att välja en delmängd av k element från en samling av n element. Ofta skrivs det som "C(n,k)" eller "n välj k."
Binomialkoefficienten definieras som
Den "!" betecknar "faktoriell".
n! = n.(n-1). (n-2)...3.2.1
Till exempel,
5! = 5.4.3.2.1
= 120
Så låt oss säga C(5,3) eller 5 välj 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metod 1: Bygg Pascals triangel efter föregående rad
Stegen i denna procedur är desamma som i Pascals triangel. Låt oss säga att vi vill skapa Pascals triangel upp till sju rader.
Stegen för att uppnå det är följande:
Steg 1) Starta den översta raden med "1".
Steg 2) För raden "r" kommer "c" att vara produkten av "c-1" och "c" numret på "r-1" raden.
Steg 3) De första och sista siffrorna i raden är alltid "1".
Vi måste följa dessa tre enkla steg för att skapa Pascals triangel.
C++ Code av Pascals triangel vid föregående rad
#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);
}
Produktion:
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 av Pascal-triangelformeln av föregående rad
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)
Pascals triangelexempelutgång:
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
Komplexitetsanalys
A tvådimensionell array användes vid implementeringen. Givet att N är antalet rader i Pascals triangel. Detta kommer att kräva N2 enhetsutrymmen. Därför kommer O att vara rymdkomplexiteten (N2).
Vi har två loopar i funktionen, och varje loop körs "N" gånger. Så, tidskomplexiteten är också PÅ2) eller kvadratisk tidskomplexitet.
Metod 2: Bygg Pascals triangel genom att beräkna binomialkoefficient
Vi kan helt enkelt härleda talen för pascals triangel med hjälp av den binomiala koefficienten. Här är diagrammet:
Här är stegen för att bygga Pascals triangel genom att beräkna binomialen:
Steg 1) Den översta raden kommer att vara C(0,0). Med formeln ovan för binomialkoefficienten, C(0,0) = 1. Eftersom 0! = 1.
Steg 2) För rad "i" kommer det att finnas totalt "i"-element. Varje post kommer att beräknas C(n,r) där n kommer att vara i-1.
Steg 3) Upprepa steg 2 för det antal rader du vill ha för pascals triangel.
C++ Code Pascals triangel med binomialkoefficient
#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);
}
Produktion:
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 Pascals triangel med binomialkoefficient
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)
Pascals triangelexempelutgång:
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
Komplexitetsanalys
Tre loopar användes i implementeringen. En loop är för att beräkna binomialkoefficienten, och de andra två är för att skapa tal för alla rader. När det gäller antalet rader har vi tre loopar som kör "n" gånger. Följaktligen kommer den totala tidskomplexiteten att vara 0(n3).
Rymdkomplexiteten är nu konstant eftersom vi inte lagrar några data. Programmet beräknar elementet och det skrivs ut i rad. Utrymmeskomplexiteten minskar sedan till 0(1).
Metod 3: Bygg Pascals triangel med modifierad binomialkoefficient
I den tidigare tekniken har vi redan sett hur man använder en binomial koefficient för att beräkna varje element i Pascals triangel. Detta tillvägagångssätt kommer att bestämma C(n,r) från C. (n, r-1). Det kommer att förenkla saker med en beställning.
Här är stegen för att bygga Pascals triangel med modifierad binomialkoefficient:
Steg 1) Initiera den första raden med "1"
Steg 2) Beräkna C(n,r), där "n" är radnumret och "r" är kolumnen eller elementet. Tilldela värdet i en variabel C.
Steg 3) För att beräkna C(n,k) blir det C*(nk)/k. Tilldela nu detta värde till C.
Steg 4) Fortsätt steg 3 tills "k" når slutet av raden. Efter varje iteration, öka värdet på K med ett.
C++ Code för Pascals triangel med modifierad binomialkoefficient
#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);
}
Produktion:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python kod för Pascals triangel med modifierad binomialkoefficient
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)
Utdata för Pascals triangelmönster:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Komplexitetsanalys
Implementeringen har två loopar. Varje slinga löper högst "n" tid, där "n" betyder antalet rader i pascaltriangeln. Så, tidskomplexiteten är På2), kvadratisk tid.
När det gäller utrymmeskomplexitet behövde vi ingen array att lagra. Vi använde bara en variabel för att behålla den tidigare binomialkoefficienten. Så vi behövde bara ett extra utrymme. Rymdkomplexiteten blev O (1).
Tillämpning av Pascals triangel
Här är några tillämpningar av Pascals triangel:
Binomiala expansioner: Vi kan bestämma koefficienten för de binomiala expansionerna från Pascals triangel. Här är ett exempel:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2och + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3och + 6x2y2 + 4xy3 + 1y4 |
Beräkna kombinationer: Vi har sett element i Pascals triangel är ekvivalenta med binomialkoefficienter. Till exempel, om du har 6 bollar och har blivit ombedd att välja 3 bollar så blir det 6C3. Eller så kan du hitta numret i det 3:e elementet i den 6:e raden från Pascals triangel.
Intressanta fakta om Pascals triangel
Här är några fakta du kommer att hitta intressant om Pascals triangel:
- Summan av alla element i en rad är alltid potensen av 2.
- Diagonal summan av elementen i raderna genererar Fibonacci-sekvensen.
Sammanfattning
- Pascals triangel ger koefficienterna för de binomiala expansionerna.
- Varje rad i pascals triangel börjar och slutar med "1". De mellanliggande värdena är summan av två element i föregående rad.
- Diagonal tillägg av alla element i pascals triangel kommer att ge dig Fibonacci-sekvens.
- Pascals triangel kan också genereras med binomialkoefficienter.
